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. Below are 12 solved MCQs from KnowledgeGate's published question bank, almost all previous-year GATE problems with the year marked. Attempt each before the explanation, which is short by design. A note on the deep links: where a question is carried as a solved GATE PYQ inside the course, we link its exact page; one definitional question has no such page, so for that one the Queue learn module is your entry point.
Stacks: LIFO order and valid sequences
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 solved page).
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 solved page).
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 solved page).
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 solved page).
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 solved page).
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 solved page).
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 solved page).
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 solved page).
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 solved page).
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 solved page).
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 solved page).
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. This question has no separate solved page, so use the Queue learn module for its practice set.
How stacks and queues are examined
The set tracks the real exam pattern: LIFO order and legal stack sequences (Q1 to Q3), infix-to-postfix conversion driven by precedence and associativity (Q4 to Q6), FIFO behaviour with array and stack-based implementations (Q7 to Q9), and the boundary conditions of circular queues and deques (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.
