ds assignments stacks and queues

 Q1) application of stacks:

1. Expression Evaluation 

2. Expression Conversion i. Infix to Postfix ii. Infix to Prefix iii. Postfix to Infix iv. Prefix to Infix 

3. Backtracking 

application of queues:

1) When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.
2) When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.

Q2) Sparsh matrix:

A sparse matrix is a matrix in which many or most of the elements have a value of zero. This is in contrast to a dense matrix, where many or most of the elements have a non-zero value.

a sparse matrix, substantial memory requirement reductions can be realized by storing only the non-zero entries. Depending on the number and distribution of the non-zero entries, different data structures can be used and yield huge savings in memory when compared to the basic approach.

algorithm:

1. Initialize

l=1

T=0

2. Scan each row

Repeat thru step 9 while l<=M

3. Obtain row indices and starting positions of next rows

J=AROW[l]

K=BROW[l]

CROW[l]=T+1

AMAX=BMAX=0

If l<M

then Repeat for P=l+1, l+2, ......M while AMAX=0

If AROW[P]/=0

then AMAX=AROW[P]

Repeat for P=l+1, l+2,.......M while BMAX=0

If BROW[P]/=0

then BMAX=BROW[P]

If AMAX=0

then AMAX=R+1

If BMAX=0

then BMAX=S+1

4. Scan columns of this row

Repeat thru step 7 while J/=0 and K/=0

5. Elements in same column?

If ACOL[J]=BCOL[K]

then SUM=A[J]+B[K]

COLUMN=ACOL[J]

J=J+1

K=K+1

else If ACOL[J]<BCOL[K]

then SUM=A[J]

COLUMN=ACOL[J]

J=J+1

else SUM=B[K]

COLUMN=BCOL[K]

K=K+1

6. Add new elements to sum of matrices

If SUM/=0

then T=T+1

C[T]=SUM

CCOL[T]=COLUMN

7. End of either row?

If J=AMAX

then J=0

If K=BMAX

then K=0

8. Add remaining elements of a row

If J=0 and K/=0

then repeat while K<BMAX

T=T+1

C[T]=B[K]

CCOL[T]=BCOL[K]

K=K+1

else if K=0 and J/=0

then repeat while J<AMAX

T=T+1

C[T]=A[J]

CCOL[T]=ACOL[J]

J=J+1

9. Adjust index to matrix C and increment row index

If T<CROW[l]

then CROW[l]=0

l=l+1

10. Finished

Exit

Q3) Stacks:

1. Stack is an ordered list of similar data type.
2. Stack is a LIFO(Last in First out) structure or we can say FILO(First in Last out).
3. push() function is used to insert new elements into the Stack and pop() function is used to remove an element from the stack. Both insertion and removal are allowed at only one end of Stack called Top.
4. Stack is said to be in Overflow state when it is completely full, when int postion = int size -1.
5.  and is said to be in Underflow, when int postion = -1 state if it is completely empty.

Q4) Hanoi structure:

Let there are 3 positions 

1) source

2) destination

3) Auxilliary

respectively in a row.

procedure;

Step 1 − Move n-1 disks from source to auxilliary
Step 2 − Move nth disk from source to destination
Step 3 − Move n-1 disks from auxilliary to destination

Q5) Conditions for full stacks and queue

1) If stack is full, 

when all the dynamic memory in heap get exhausted by continuously adding data in stack, and neglect the further coming value and show NULL value.

2) If queue is full, check

rear == SIZE-1 && front == 0 or rear == front-1

Q6) priority queue:

A priority queue is a special type of queue in which each element is associated with a priority and is served according to its priority. If elements with the same priority occur, they are served according to their order in the queue. Generally, the value of the element itself is considered for assigning the priority.

The list is so created so that the highest priority element is always at the

 head of the list. The list is arranged in descending order of elements based on

 their priority. This allow us to remove the highest priority element in O(1) 

time. To insert an element we must traverse the list and find the proper 

position to insert the node so that the overall order of the priority queue is 

maintained. This makes the push() operation takes O(N) time. The pop() and 

peek() operations are performed in constant time.

 

Q7) Algorithms  for the following cases:

1) insert in stack :

begin procedure push: stack, data

   if stack is full
      return null
   endif
   
   top ← top + 1
   stack[top] ← data

end procedure

2) POP() in stack

 

begin procedure pop: stack

   if stack is empty
      return null
   endif
   
   data ← stack[top]
   top ← top - 1
   return data

end procedure

3)peek() in stack

int peek() {
   return stack[top];
}

4)enqueue in queue:

procedure enqueue(data)      
   
   if queue is full
      return overflow
   endif
   
   rear ← rear + 1
   queue[rear] ← data
   return true
   
end procedure

5) DEQUEUE()  in queue:

procedure dequeue
   
   if queue is empty
      return underflow
   end if

   data = queue[front]
   front ← front + 1
   return true

end procedure