Stacks and queues look simple, and that is exactly why the questions get sharp. Examiners test whether you truly track LIFO and FIFO order under a mixed sequence of operations, whether you can convert infix to postfix with correct precedence, and whether you know the boundary conditions of a circular queue cold. Eleven of the twelve problems here are previous-year GATE questions, from 1991 through 2017, and the twelfth is UGC NET 2021. Attempt each one before you read the explanation, and open the linked solution for any answer you got wrong. If you would rather rebuild the fundamentals first, the Stack learn module and the Queue learn module cover the operations these questions assume you already know.
Stacks: LIFO order, valid sequences and stack recurrences
Q1. The sequence PUSH(10), PUSH(20), POP, PUSH(10), PUSH(20), POP, POP, POP, PUSH(20), POP is performed on a stack. What is the sequence of values popped out? (GATE 1991)
(a) 20, 10, 20, 10, 20
(b) 20, 20, 10, 10, 20
(c) 10, 20, 20, 10, 20
(d) 20, 20, 10, 20, 10
Answer: (b) 20, 20, 10, 10, 20. A stack is Last In First Out, so each POP returns the most recently pushed value still present. Trace it: the pops return 20, then 20, then 10, then the first 10, and finally the last pushed 20. Tracking the top after every operation is the whole skill here (see the full solution).
Q2. Characters a, b, c, d are pushed onto a stack in that order, and the top may be popped at any time. Which output string CANNOT be generated? (GATE 2004)
(a) abcd
(b) dcba
(c) cbad
(d) cabd
Answer: (d) cabd. To output c first, we must have pushed a, b, c, leaving a below b on the stack. Because b sits above a, b must come out before a. So any valid output with c first has b before a, but cabd puts a before b. That ordering is impossible with a single stack (see the full solution).
Q3. A function f on stacks of integers satisfies f(empty) = 0 and f(push(S, i)) = max(f(S), 0) + i. If S holds 2, -3, 2, -1, 2 from bottom to top, what is f(S)? (GATE 2005)
(a) 6
(b) 4
(c) 3
(d) 2
Answer: (c) 3. Apply the rule from the bottom up. Push 2 gives 2, push -3 gives max(2,0)-3 = -1, push 2 gives max(-1,0)+2 = 2, push -1 gives max(2,0)-1 = 1, push 2 gives max(1,0)+2 = 3. This is the maximum-suffix-sum pattern dressed up as a stack recurrence (see the full solution).
Infix, postfix and expression conversion
Q4. Which of the following is essential for converting an infix expression to postfix efficiently? (GATE 1997)
(a) An operator stack
(b) An operand stack
(c) An operand stack and an operator stack
(d) A parse tree
Answer: (a) an operator stack. In the shunting-yard algorithm, operands are written straight to the output as they are read, so they never need a stack. Only operators and parentheses must be held and reordered by precedence, and a single operator stack does that. No operand stack or parse tree is required (see the full solution).
Q5. The postfix form of the infix expression A + B x (C + D) / F + D x E is (GATE 1995)
(a) A B + C D + x F / D + E x
(b) A B C D + x F / + D E x +
(c) A x B + C D / F x D E + +
(d) A + x B C D / F x D E + +
Answer: (b). Resolve precedence step by step. The bracket C + D becomes C D +, then B x (C + D) becomes B C D + x, and dividing by F gives B C D + x F /. Adding A yields A B C D + x F / +, and D x E becomes D E x. Appending it produces A B C D + x F / + D E x + (see the full solution).
Q6. With +, -, x left associative and ^ right associative, and precedence ^ > x > + > -, the postfix form of a + b x c - d ^ e ^ f is (GATE 2004)
(a) a b c x + d e f ^ ^ -
(b) a b c x + d e ^ f ^ -
(c) a b + c x d - e ^ f ^
(d) - + a x b c ^ ^ d e f
Answer: (a) a b c x + d e f ^ ^ -. Because ^ is right associative, d ^ e ^ f groups as d ^ (e ^ f), giving d e f ^ ^. Then b x c is b c x, and a + (b x c) is a b c x +. The final subtraction of the exponentiation term appends the minus, producing a b c x + d e f ^ ^ - (see the full solution).
Queues: FIFO, array queues and stack-queue simulation
Q7. What is the minimum number of stacks of size n required to implement a queue of size n? (GATE 2001)
(a) One
(b) Two
(c) Three
(d) Four
Answer: (b) Two. A single stack is LIFO and cannot preserve FIFO order alone. With two stacks, enqueue pushes onto the first; for dequeue, when the second stack is empty, pour everything from the first into the second, which reverses the order and exposes the oldest element on top. Two stacks are both necessary and sufficient (see the full solution).
Q8. A queue is implemented using an array so that ENQUEUE and DEQUEUE are efficient. Which statement is correct (n is the number of items)? (GATE 2016)
(a) Both operations can be performed in O(1) time
(b) At most one operation is O(1), the other is worst-case Omega(n)
(c) Both operations are worst-case Omega(n)
(d) Both operations are worst-case Omega(log n)
Answer: (a). Use a circular buffer with head and tail indices. Enqueue writes at tail and advances tail modulo capacity; dequeue reads at head and advances head modulo capacity. Each does a constant number of index updates, so both are O(1). The circular trick is what avoids the shifting that would make one operation linear (see the full solution).
Q9. With ENQUEUE, DEQUEUE and a MultiDequeue(Q) that repeatedly dequeues up to k elements (k a global parameter), what is the worst-case time for a sequence of n queue operations on an initially empty queue? (GATE 2013)
(a) Theta(n)
(b) Theta(n + k)
(c) Theta(nk)
(d) Theta(n squared)
Answer: (a) Theta(n). This is an amortized-counting question. Every element is enqueued at most once and dequeued at most once, whether the dequeue happens directly or inside MultiDequeue. So the total number of dequeue actions across the whole sequence cannot exceed the number of enqueues, which is at most n. The k in the loop never lets total work exceed the elements that exist (see the full solution).
Circular queues and deques
Q10. A circular queue of capacity n-1 elements is implemented in an array of n slots, with REAR and FRONT as index variables, initially REAR = FRONT = 0. The full and empty conditions are (GATE 2012)
(a) full: (REAR+1) mod n == FRONT; empty: REAR == FRONT
(b) full: (REAR+1) mod n == FRONT; empty: (FRONT+1) mod n == REAR
(c) full: REAR == FRONT; empty: (REAR+1) mod n == FRONT
(d) full: (FRONT+1) mod n == REAR; empty: REAR == FRONT
Answer: (a). One slot is deliberately left unused so full and empty can be told apart. Empty is REAR == FRONT. Full is (REAR+1) mod n == FRONT, because advancing REAR one more step would collide with FRONT. This one reserved slot is the classic reason a size-n array stores only n-1 elements (see the full solution).
Q11. A circular queue is implemented with a singly linked list, keeping exactly two external pointers FRONT and REAR, so that both insertion and deletion are O(1). What must hold? (GATE 2017)
(a) FRONT.next points to REAR
(b) REAR.next points to FRONT
(c) both of the above
(d) neither of the above
Answer: (b) REAR.next points to FRONT. Making the rear node point back to the front closes the ring. Insertion links a new node after REAR and updates REAR, keeping REAR.next = FRONT, all in O(1). Deletion advances FRONT to FRONT.next and keeps the ring intact, also O(1). Pointing FRONT.next to REAR would not give constant-time insertion at the rear (see the full solution).
Q12. A double-ended queue (deque) supports AddFront, AddRear, RemoveFront and RemoveRear. If you may use only stacks to implement it, the time for AddFront and AddRear respectively is (UGC NET 2021)
(a) O(m) and O(n)
(b) O(1) and O(n)
(c) O(n) and O(1)
(d) O(n) and O(m)
Answer: (b) O(1) and O(n). With a single main stack, AddFront just pushes on top, which is O(1). AddRear must reach the bottom, so you pop everything onto a temporary stack, push the new element, then pour it all back, which is O(n). This asymmetry is the point: a stack makes one end cheap and the other expensive, and it is why a deque built only from stacks is never symmetric (see the full solution).
How stacks and queues are examined
Examiners come back to four things on this topic. First, whether you can trace LIFO order through a mixed operation sequence and judge which output orders a single stack is even capable of producing (Q1 to Q3). Second, whether precedence and associativity survive your infix-to-postfix conversion, which is where right-associative exponentiation catches most attempts (Q4 to Q6). Third, whether you can argue about cost rather than mechanics: two stacks to get FIFO out of LIFO, O(1) enqueue and dequeue once the array is treated as circular, and an amortized Theta(n) for a whole sequence of MultiDequeue calls (Q7 to Q9). Fourth, the one reserved slot that separates a full circular queue from an empty one, and the pointer discipline a linked circular queue needs to keep both ends O(1) (Q10 to Q12). A missed question here is nearly always an order-tracking slip, not a gap in practice volume.
When you are ready for the next structure, our binary tree MCQs collection is the natural companion set. GATE aspirants get the whole Data Structures sequence inside GATE Guidance by Sanchit Sir, and the GATE CS Exam category shows where it sits in the syllabus. Solve, review what you missed, and return a week later; the second pass is where the marks lock in.
