Stacks & Queues
LIFO and FIFO — expression evaluation, BFS/DFS, and classic interview problems. A recurring 1–2 mark topic in GATE CS every year.
Last updated: April 2026 | GATE CS 2024–2026 syllabus
Key Takeaways
- Stack: LIFO. Operations push, pop, peek — all O(1). Implemented with array or linked list.
- Queue: FIFO. Enqueue at rear, dequeue at front — O(1) each. Circular queue avoids space waste.
- Infix to postfix: shunting-yard algorithm using a stack, O(n) time.
- Postfix evaluation: scan left to right; push operands, pop two on operator. O(n).
- Queue using 2 stacks: amortised O(1) per operation.
- Stack using 2 queues: O(n) push or O(n) pop depending on variant.
- Deque (double-ended queue): O(1) insert/delete at both ends. Used in sliding window maximum.
1. Stack
A stack is a Last-In-First-Out (LIFO) data structure. The element most recently pushed is the first to be popped.
Array implementation: maintain top index. Push: A[++top] = x. Pop: return A[top–].
Linked list implementation: push/pop at head.
Applications
- Function call stack (activation records)
- Expression conversion and evaluation
- DFS (iterative) — use explicit stack instead of recursion
- Parenthesis matching, undo operations
- Monotonic stack problems (next greater element)
2. Queue
A queue is a First-In-First-Out (FIFO) structure. Elements enter at rear and leave at front.
Array (linear) issue: front keeps moving right; space before front is wasted. Solved by circular queue.
Linked list implementation: maintain head (front) and tail (rear) pointers.
Applications
- BFS traversal of graphs and trees
- CPU scheduling (FCFS), I/O request queues
- Level-order traversal of binary trees
- Producer-consumer buffer
3. Circular Queue
Empty: front == rear
Full: (rear + 1) % capacity == front (one slot wasted to distinguish empty from full)
Size: (rear − front + capacity) % capacity
| Operation | Time | Condition |
|---|---|---|
| Enqueue | O(1) | Check not full before inserting |
| Dequeue | O(1) | Check not empty before removing |
| Peek (front) | O(1) | — |
4. Expression Conversion & Evaluation
Operator Precedence (high to low)
| Precedence | Operators | Associativity |
|---|---|---|
| Highest | ^ (exponentiation) | Right |
| High | *, / | Left |
| Low | +, − | Left |
Infix to Postfix (Shunting-Yard)
• Operand → output directly
• ‘(’ → push to stack
• ‘)’ → pop and output until ‘(’; discard ‘(’
• Operator op: pop and output while stack top has ≥ precedence (and is left-associative); push op
• End: pop all remaining operators to output
Time: O(n) Space: O(n)
Postfix Evaluation
• Operand → push to stack
• Operator → pop two operands b (top), a (second), compute a op b, push result
Final stack top = result. Time: O(n)
Prefix Evaluation
Scan right to left. Same rules: operand push; operator pop two, compute, push. Or convert prefix to infix then evaluate.
5. Queue from Two Stacks & Stack from Two Queues
Queue using Two Stacks (S1 for enqueue, S2 for dequeue)
Dequeue(): if S2 empty, pop all from S1 and push to S2; pop from S2
Amortised dequeue: O(1) (each element moved at most once from S1 to S2)
Stack using Two Queues
Push(x): enqueue x to Q2; dequeue all from Q1 to Q2; swap Q1 and Q2. O(n) push, O(1) pop.
Variant 2 (costly pop):
Push(x): enqueue to Q1 — O(1). Pop: dequeue all from Q1 to Q2 except last; dequeue last (= top); swap. O(n) pop, O(1) push.
6. Deque (Double-Ended Queue)
Supports insert and delete at both front and rear in O(1). Can simulate both stack (use one end) and queue (insert at one end, delete at other).
Classic application: Sliding window maximum — maintain a monotonic deque of indices; O(n) total.
7. Key Applications Summary
| Application | Structure | Why |
|---|---|---|
| DFS | Stack | LIFO matches backtracking |
| BFS | Queue | FIFO matches level-by-level expansion |
| Function calls | Stack | Last function called returns first |
| Undo/redo | Two stacks | Undo = pop undo stack, push redo stack |
| Balanced parentheses | Stack | Match open/close pairs |
| Level-order tree traversal | Queue | Process nodes level by level |
| Sliding window max | Deque | Monotonic deque in O(n) |
8. GATE CS Solved Examples
Example 1 — Infix to Postfix (GATE CS 2020)
Q: Convert A + B * C − D / E to postfix.
Trace:
| Token | Action | Stack | Output |
|---|---|---|---|
| A | Output | [] | A |
| + | Push | [+] | A |
| B | Output | [+] | A B |
| * | Push (* > +) | [+, *] | A B |
| C | Output | [+, *] | A B C |
| − | Pop * and +, push − | [−] | A B C * + |
| D | Output | [−] | A B C * + D |
| / | Push (/ > −) | [−, /] | A B C * + D |
| E | Output | [−, /] | A B C * + D E |
| End | Pop all | [] | A B C * + D E / − |
Example 2 — Circular Queue State (GATE CS 2018)
Q: Circular queue, capacity 6. front=2, rear=4. Elements: [_, _, 10, 20, 30, _]. Dequeue twice, then enqueue 40 and 50. New front, rear and contents?
Solution: Dequeue: front=(2+1)%6=3, then front=4. Enqueue 40: rear=(4+1)%6=5, A[5]=40. Enqueue 50: rear=(5+1)%6=0, A[0]=50. front=4, rear=0. Contents: [50, _, _, _, 30, 40].
Example 3 — Queue using 2 stacks cost (GATE CS 2015)
Q: n enqueue and n dequeue operations on a queue implemented with 2 stacks. Total number of stack push + pop operations?
Solution: Each element: 1 push to S1 (enqueue) + 1 pop from S1 + 1 push to S2 (first dequeue batch) + 1 pop from S2 (dequeue) = 4 operations. For n elements: 4n.
9. Common Mistakes
Mistake 1 — Wrong full condition for circular queue
Using rear == front as full. Correct full condition: (rear+1) % capacity == front. One slot is sacrificed to distinguish full from empty.
Mistake 2 — Wrong operand order in postfix evaluation
For binary operator, second pop is left operand, first pop is right: a = pop(), b = pop(), result = b op a. Order matters for − and /.
Mistake 3 — Not popping equal precedence operators in infix-postfix
For left-associative operators, pop stack while top precedence ≥ current. For right-associative (like ^), pop only while top precedence > current.
Mistake 4 — Stating queue-from-2-stacks dequeue is O(n) always
Worst case is O(n) but amortised is O(1). Each element is moved S1→S2 exactly once across all dequeue calls.
Mistake 5 — Prefix scan direction
Prefix evaluation scans right to left (opposite of postfix). When you see an operator, the next two items on the stack are left then right operand (push order).
10. FAQ
How do you convert an infix expression to postfix?
Shunting-yard algorithm: output operands immediately; push operators on a stack, popping operators of ≥ precedence first; handle parentheses by pushing ‘(’ and popping till ‘(’ on ‘)’. O(n) time.
What is a circular queue and why is it used?
Circular queue uses modular arithmetic (index = (index+1)%capacity) to reuse freed positions. Solves the front-drift problem of linear array queues. Full when (rear+1)%cap == front; empty when front == rear.
How do you implement a queue using two stacks?
Enqueue to S1. Dequeue: if S2 empty, move all S1 elements to S2 (reversing order), then pop S2. Amortised O(1) per operation.
What is the difference between a stack and a deque?
Stack allows push/pop at one end only. Deque allows insert/delete at both ends. Deque generalises both stack and queue.