GATE CS - PROGRAMMING & DATA STRUCTURES:Stacks and Queues

Stacks and Queues

GATE uses stacks for expression conversion/evaluation, recursion models, and parenthesis matching, and queues for BFS and circular-buffer questions. Credit goes to tracing a push/pop sequence on paper — not to memorising “applications: undo/redo.”

Stack (LIFO)

Operations: push, pop, peek — all O(1) for a well-implemented stack. Overflow = push on full; underflow = pop on empty.

Array implementation keeps an index top (often starting at −1). Linked implementation pushes at the head so both push and pop stay O(1).

Worked: postfix evaluation

Expression: 2 3 4 * + (infix 2 + 3*4)

1. Push 2, push 3, push 4
2. See *: pop 4 and 3 → push 12
3. See +: pop 12 and 2 → push 14

Answer on top: 14.

Trap: operator order — for binary ops, the first popped value is the right operand.

Infix → postfix (outline)

Scan left to right. Operands go to output. Operators go on a stack, popping higher/equal precedence first (depending on associativity). ( pushes; ) pops until (. Empty the stack at the end.

Parenthesis matching

Push opening brackets. On a closer, pop and check the match. Empty stack at the end ⇒ balanced. GATE may mix (), [], {}.

Queue (FIFO)

enqueue at rear, dequeue from front — O(1) with proper pointers. A plain array queue that never wraps wastes slots; circular queue uses (index + 1) % MAX.

Full condition (one common convention): (rear + 1) % MAX == front. Empty: front == -1 (or front == rear with a different sentinel scheme — read the question’s convention).

Deque and priority queue

• Deque: insert/delete both ends (can simulate stack or queue).
• Priority queue: dequeue by priority; heap implementation is O(log n) for insert/extract — often tested under heaps, not “queue theory.”

Stack vs queue (exam view)

Next: Trees, then timed drills on the GATE hub.