Question 3

(a)Explain following:
(i) DQUEUE, (ii) Priority Queue, (iii) Circular Queue.

(i) DQUEUE: It is a double-ended queue. Items can be inserted and deleted from either
ends. More versatile data structure than stack or queue. E.g. policy-based application
(e.g. low priority go to the end, high go to the front)

(ii) Priority Queue: More specialized data structure. Similar to Queue, having front and
rear. Items are removed from the front. Items are ordered by key value so that the item
with the lowest key (or highest) is always at the front. Items are inserted in proper
position to maintain the order.

(iii) Circular Queue: When a new item is inserted at the rear, the pointer to rear moves
upwards. Similarly, when an item is deleted from the queue the front arrow moves
downwards. After a few insert and delete operations the rear might reach the end of the
queue and no more items can be inserted although the items from the front of the queue
have been deleted and there is space in the queue. To solve this problem, queues
implement wrapping around. Such queues are called Circular Queues. Both the front
and the rear pointers wrap around to the beginning of the array.
     
            

(b) Write the implementation procedure of basic primitive operations of the stack using: (i) Linear array, (ii) Linked List.

 • Implementation Procedure of the Stack Using Linear Array:
Procedure PUSH(S, TOP, X) :- This procedure inserts an element X to the top of a
stack. Stack is represented by a vector S containing N elements. TOP is a pointer to the
top element in the stack.

Step-1: [Check for Stack Overflow]
If TOP  N
then Write(‘STACK OVERFLOW’)
Return

Step-2: [Increment TOP]
TOP 
 TOP + 1

Step-3: [Insert an element]
S[TOP] 
 X

Step-4: [Finished]
Return

Function POP(S, TOP) :- This function deletes and returns the top element of a stack.
Stack is represented by a vector S. TOP is a pointer to the top element in the stack. X is
a temporary variable.

Step-1: [Check for Stack Underflow]
If TOP = 0
then Write(‘STACK UNDERFLOW’)
Return(0) (0 denotes empty stack)

Step-2: [Delete top element of stack]
X 
 S[TOP]

Step-3: [Decrement TOP]
TOP 
 TOP – 1

Step-4: [Return top element of stack]
Return(X)

(C) Consider the following arithmetic expression P, written in postfix notation. Translate it in infix notation and evaluate. P: 12, 7, 3, -, /, 2, 1, 5, +, *, +

P: 12, 7, 3, -, /, 2, 1, 5, +, *, +
12, (7 – 3), /, 2, 1, 5, +, *, +
(12 / (7 – 3)), 2, 1, 5, +, *, +
(12 / (7 – 3)), 2, (1 + 5), *, +
(12 / (7 – 3)), (2 * (1 + 5)), +
(12 / (7 – 3)) + (2 * (1 + 5))
= (12 / 4) + (2 * (1 + 5))
= 3 + (2 * (1 + 5))
= 3 + (2 * 6)
= 3 + 12
= 15
            

(b) Write the implementation procedure of basic primitive operations of the queue using: (i) Linear array, (ii) Linked List.

Implementation Procedure of the Queue Using Linear Array:
Procedure QINSERT(Q, F, R, N, Y) :- Given F and R, pointers to the front and rear
elements of a queue, respectively. Queue is represented by a vector Q consisting of N
elements, and an element Y. This procedure inserts Y at the rear of the queue. Initially,
F and R set to zero.

Step-1: [Check for Queue Overflow]
If R≥ N
then Write(‘OVERFLOW’)
Return
Step-2: [Increment rear pointer]
R← R + 1
Step-3: [Insert an element]
Q(R)← Y
Step-4: [Is front pointer properly set?]
If F = 0
then F← 1
Return
Function QDELETE(Q, F, R) :- Given F and R, pointers to the front and rear elements
of a queue, respectively. Queue is represented by a vector Q. This function deletes and
returns the last element of the queue. Y is a temporary variable.
Step-1: [Check for Queue Underflow]
If F = 0
then Write(‘UNDERFLOW’)
Return(0) (0 denotes an empty queue)
Step-2: [Delete an element]
Y←Q[F]
Step-3: [Is queue empty?]
If F = R
then F←R←0
else F←F + 1
Step-4: [Return an element]
Return(Y)
            

            

(C) Discuss advantages and disadvantages of linked list over array.

Advantages of Linked List over Array:::

1 . Access :Random / Sequential
Stack elements can be randomly Accessed using Subscript Variable
e.g a[0],a[1],a[3] can be randomly accessed
While In Linked List We have to Traverse Through the Linked List for Accessing
Element. So O(n) Time required for Accessing Element .
Generally In linked List Elements are accessed Sequentially.

2 . Memory Structure :
Stack is stored in contiguous Memory Locations , i.e Suppose first element is
Stored at 2000 then Second Integer element will be stored at 2002 .
But It is not necessary to store next element at the Consecutive memory
Location .
Element is stored at any available Location , but the Pointer to that memory
location is stored in Previous Node.

3 . Insertion / Deletion
As the Array elements are stored in Consecutive memory Locations , so While
Inserting elements ,we have to create space for Insertion.
So More time required for Creating space and Inserting Element
Similarly We have to Delete the Element from given Location and then Shift All
successive elements up by 1 position.
In Linked List we have to Just Change the Pointer address field (Pointer),So
Insertion and Deletion Operations are quite easy to implement.

4 . Memory Allocation :
Memory Should be allocated at Compile-Time in Stack . i.e at the time when
Programmer is Writing Program.
In Linked list memory can be allocated at Run-Time , i.e After executing
Program.
Stack uses Static Memory Allocation and Linked List Uses Dynamic Memory
Allocation.
Dynamic Memory allocation functions - malloc,calloc,delete etc...