Stacks and queues are dynamic sets in which the element removed from the set by the DELETE operation is prespecified.
In a stack, the element deleted from the set is the one most recently inserted: the stack implements a last-in, first-out, or LIFO, policy
Queue, the element deleted is always the one that has been in the set for the longest time: the queue implements a first-in, first-out, or FIFO, policy.
Stacks
The INSERT operation on a stack is often called PUSH, and the DELETE operation, which does not take an element argument, is often called POP.
The stack consists of elements S[1...S.top], where S[1] is the element at the bottom of the stack and S[S.top] is the element at the top.
When S.top = 0, the stack contains no elements and is empty. If we attempt to pop an empty stack, we say the stack underflows, which is normally an error. If S.top exceeds n, the stack overflows. Each of the three stack operations below takes O(1) time.
Stacks Operations - Pseudocode
STACK-EMPTY(S)
if S.top == 0
return true
else return false
PUSH(S,x)
S.top = S.top + 1
S[S.top] = x
POP(S)
if STACK-EMPTY(S)
error “underflow”
else S.top = S.top - 1
return S[S.top + 1]
INSERT operation on a queue ENQUEUE, and we call the DELETE operation DEQUEUE; like the stack operation POP, DEQUEUE takes no element argument.
The queue has an attribute Q.head that indexes, or points to, its head. The attribute Q.tail indexes the next location at which a newly arriving element will be inserted into the queue.
The elements in the queue reside in locations Q.head, Q.head + 1, ... , Q.tail - 1, where we “wrap around” in the sense that location 1 immediately follows location n in a circular order. When Q.head = Q.tail, the queue is empty.
Initially, we have Q.head = Q.tail = 1. If we attempt to dequeue an element from an empty queue, the queue underflows. When Q.head = Q.tail + 1, the queue is full, and if we attempt to enqueue an element, then the queue overflows.
Queue Operations - Pseudocode
ENQUEUE(Q,x)
Q[Q.tail] = x
if Q.tail == Q.length
Q.tail = 1
else Q.tail = Q.tail + 1
DEQUEUE(Q)
x = Q[Q.head]
if Q.head == Q.length
Q.head = 1
else Q.head = Q.head + 1
return x
Q. Illustrate the result of each operation in the sequence PUSH(S,4),PUSH(S,1),PUSH(S,3),POP(S),PUSH(S,8),and POP(S) on an initially empty stack S stored in array S[1..6].
Q. Explain how to implement two stacks in one array A[1 .. n] in such a way that neither stack overﬂows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.
We will call the stacks T and R. Initially, set T.top = 0 and R.top = n + 1. Essentially, stack T uses the first part of the array and stack R uses the last part of the array. In stack T, the top is the rightmost element of T. In stack R, the top is the leftmost element of R.
Algorithm 1: PUSH(S,x)
if S == T then
if T.top + 1 == R.top then
error "overflow"
else
T.top = T.top + 1
T[T.top] = x
end if
end if
if S == R then
if R.top - 1 == T.top then
error "overflow"
else
R.top = R.top - 1
T[T.top] = x
end if
end if
Algorithm 2: POP(S)
if S == T then
if T.top == 0 then
error "underflow"
else
T.top = T.top - 1
return T[T.top + 1]
end if
end if
if S == R then
if R.top == n + 1 then
error "underflow"
else
R.top = R.top + 1
return R[R.top - 1]
end if
end if
Q. Whereas a stack allows insertion and deletion of elements at only one end, and a queue allows insertion at one end and deletion at the other end, a deque (doubleended queue) allows insertion and deletion at both ends. Write four O(1) time procedures to insert elements into and delete elements from both ends of a deque implemented by an array.>
Algorithm 4: DEQUEUE
if Q.tail == Q.head then
error "underflow"
end if
x = Q[Q.head]
if Q.head == Q.length then
Q.head = 1
else
Q.head = Q.head + 1
end if
return x
Algorithm 5: HEAD-ENQUEUE(Q,x)
Q[Q.head] = x
if Q.head == 1 then
Q.head = Q.length
else
Q.head = Q.head - 1
end if
Algorithm 6: TAIL-ENQUEUE(Q,x)
Q[Q.tail] = x
if Q.tail == Q.length then
Q.tail = 1
else
Q.tail = Q.tail + 1
end if
Algorithm 7: HEAD-DEQUEUE(Q,x)
x = Q[Q.head]
if Q.head == Q.length then
Q.head = 1
else
Q.head = Q.head + 1
end if
Algorithm 8: TAIL-DEQUEUE(Q,x)
x = Q[Q.tail]
if Q.tail == 1 then
Q.tail = Q.length
else
Q.tail = Q.tail - 1
end if
A linked list is a data structure in which the objects are arranged in a linear order. Unlike an array, however, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object.
Each element of a doubly linked list L is an object with an attribute key and two other pointer attributes: next and prev. The object may also contain other satellite data. Given an element x in the list, x.next points to its successor in the linked list, and x.prev points to its predecessor. If x.prev = NIL, the element x has no predecessor and is therefore the ﬁrst element, or head, of the list. If x.next = NIL, the element x has no successor and is therefore the last element, or tail, of the list. An attribute L.head points to the ﬁrst element of the list. If L.head = NIL, the list is empty.
Linked List Operations - Pseudocode
LIST-SEARCH(L,k)
x = L.head
while x ≠ NIL and x.key ≠ k
x = x.next
return x
To search a list of n objects, the LIST-SEARCH procedure takes Θ(n) time in the worst case, since it may have to search the entire list.
Algorithm 2: LIST-INSERT(L,x)
x.next = L.head
if L.head ≠ NIL
L.head.prev = x
L.head = x
x.prev = NIL
The running time for LIST-INSERT on a list of n elements is O(1).
Algorithm 3: LIST-DELETE(L,x)
if x.prev ≠ NIL
x.prev.next = x.next
else L.head = x.next
if x.next ≠ NIL
x.next.prev = x.prev
LIST-DELETE runs in O(1) time, but if we wish to delete an element with a given key, Θ(n) time is required in the worst case because we must ﬁrst call LIST-SEARCH to find the element.
Q. 5 The given diagram shows the
fowchart for a recursive function A(n).
Assume that all statements, except for the recursive calls, have O(1) time complexity. If the worst case time complexity of this function is O(n^{α}), then the
least possible value (accurate up to two decimal positions) of α is .
Flowchart for Recursive Function A(n)
(GATE 2016 SET B)
Ans . 2.32
Solution steps: In worst case, least possible value of α from the flowchart can be given as:
T(n) = 5T(n/2) + c, which evalutes to (By Master Method)
T(n) = log_{2}5
T(n) = 2.32
that is, α = 2.32
Q. 6 N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: θ(N) delete, O(log N) insert, O(log N) find, and θ(N) decrease-key. What is the time complexity of all these operations put together? (GATE 2016 SET B)
O(log_{2}N)
O(N)
O(N^{2})
θ(N ^{2}logN).
Ans . C
Solution steps: The time complexity of decrease-key operation is θ(1) since we have the pointer to the record where we have to perform the operation. However, we must keep the doubly linked list sorted and after the decrease-key operation we need to find the new location of the key. This step will take θ(N) time and since there are θ(N) decrease-key operations, the time complexity becomes O(N^{2}).
Q.1 A queue is implemented using an array such that Enqueue and Dequeue operations are performed effciently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)? (GATE 2016 SET A)
Both operations can be performed in O(1) time
At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)
The worst case time complexity for both operations will be Ω(n)
Worst case time complexity for both operations will be Ω(logn)
Ans : (A)
Solution steps:
In a Queue, ENQUEUE and DEQUEUE operations are performed at rear end and front end of Queue respectively with O(1) time.
Q. Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter
\(MultiDequeue(Q)\{ \)
\(m = k \)
\(while(Q \ is \ not \ empty) and ( m > 0) \{ \)
\(Dequeue (Q) \)
\(m = m - 1 \)
\(\} \)
\(\}\)
What is the worst case time complexity of a sequence of n queue operations on an initially empty queue? (GATE 2013 SET D)
\(\theta(n)\)
\(\theta(n + k)\)
\(\theta(n \times k)\)
\(\theta(n^2)\)
Ans . 1
One option is to perform all Enqueue operations i.e. n Enqueue operations. Complexity will be \( \theta(n)\).
We can perform a mix of Enqueue and Dequeue operations. It can be Enqueue for first n/2 times and then Dequeue for next n/2, or Enqueue and Dequeue alternately, or any permutation of Enqueues and Dequeues totaling n times. Complexity will be \( \theta(n)\).
We can perform Enqueues and MultiDequeues. A general pattern could be as follows:
Enqueue Enqueue......(ktimes) MultiDequeue Enqueue Enqueue......(ktimes) MultiDequeue Up to total n
.... k items enqueued .... k items deleted .... k items enqueued .... k items deleted .... and so on.
The number of times this k-Enqueues, MutiDequeue cycle is performed = \(\frac{n}{k + 1}\) So,
Complexity will be (k times Enqueue + 1 MultiDequeue) \(\times \frac{n}{k + 1} \)
Which is \(\theta(2k \times \frac{n}{k+1}) = \theta(n) \)
We can just perform n MultiDequeues (or n Dequeues for that matter): Each time the while condition is false (empty queue), condition is checked just once for each of the n operations. So \(\theta(n)\)
Q.Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is (GATE 2015 SET B)
O(logn)
O(n)
O(nlogn)
O(n2)
Ans . A
Solution:
Q.An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is (GATE 2015 SET B)
T(nlogn)
T(n)
T(logn)
T(1)
Ans . D
Solution:
Q.A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is(GATE 2012)
Θ(n log n)
Θ\((n^2log n)\)
Θ\((n^2+log n)\)
Θ\((n^2)\)
Ans . 2
The height of the recursion tree using merge sort is logn and n2 comparisons are done at each level, where at most n pairs of strings are compared at each level and n comparisons are required to compare any two strings, So the worst case running time is O \((n^2 logn)\)
full: (REAR+1) mod n==FRONT empty: REAR ==FRONT
full:(REAR+1)mod n==FRONT empty: (FRONT+1)mod n==REAR
full: REAR==FRONT empty: (REAR+1) mod n ==FRONT
full:(FRONT+1)mod n==REAR empty: REAR ==FRONT
Ans . 1
The counter example for the condition full : REAR = FRONT is
Initially when the Queue is empty REAR=FRONT=0 by which the above full condition is
satisfied which is false
The counter example for the condition full : (FRONT+1)mod n =REAR is Initially when the Queue is empty REAR=FRONT=0 and let n=3, so after inserting one element REAR=1 and FRONT=0, at this point the condition full above is satisfied, but still there is place for one more element in Queue, so this condition is also false
The counter example for the condition empty : (REAR+1)mod n = FRONT is
Initially when the Queue is empty REAR=FRONT=0 and let n=2, so after inserting one element REAR=1 and FRONT=0, at this point the condition empty above is satisfied, but the queue of capacity n-1 is full here
The counter example for the condition empty : (FRONT+1)mod n =REAR is
Initially when the Queue is empty REAR=FRONT=0 and let n=2, so after inserting one element REAR=1 and FRONT=0, at this point the condition empty above is satisfied, but the queue of capacity n-1 is full here