GATE DA / Programming, Data Structures and Algorithms

Stacks and Queues

The stack (LIFO) and queue (FIFO) abstract data types, array and linked implementations in Python, circular queues, deques and priority queues, and the classic applications — balanced brackets, postfix evaluation, infix-to-postfix conversion, recursion and the call stack, valid pop sequences, queues from stacks, and BFS.

Section 410 practice questions

Stack (LIFO)

A stack supports push(x) (add on top), pop() (remove the top), peek()/top() and is_empty() — all $O(1)$ . The last element pushed is the first popped.

Python

stack = []
stack.append(10)     # push
stack.append(20)
top = stack[-1]      # peek → 20
x = stack.pop()      # pop → 20 (IndexError if empty)

A Python list's end is a perfect stack (amortised $O(1)$ ). A linked list with insertion/removal at the head also works.

Applications

Problem	How the stack helps
Function calls, recursion	each call pushes a frame; return pops it. Deep recursion → stack overflow
Balanced brackets	push openers; on a closer, pop and check the match; succeed if the stack ends empty
Postfix evaluation	push operands; an operator pops two, pushes the result
Infix → postfix (shunting-yard)	stack holds operators by precedence
Undo/redo, browser back	most recent action first
Depth-first search	explicit stack or recursion
Next greater element, histogram area	monotonic stack — $O(n)$

Expression notation

Notation	Example for $(a + b)\times c$	Needs parentheses?
Infix	`(a + b) * c`	yes
Postfix (reverse Polish)	`a b + c *`	no
Prefix (Polish)	`* + a b c`	no

Infix to postfix: output operands immediately; for an operator, pop operators of higher (or equal, if left-associative) precedence to the output, then push it; ( is pushed; ) pops until (. At the end, pop everything.

Worked example

a * (b + c) - d / e:

token	output	stack
a	a
*	a	*
(	a	* (
b	a b	* (
+	a b	* ( +
c	a b c	* ( +
)	a b c +	*
−	a b c + *	−
d	a b c + * d	−
/	a b c + * d	− /
e	a b c + * d e	− /
end	`a b c + * d e / -`

Evaluating prefix works the same way scanning right to left.

Valid pop sequences

Pushing $1, 2, \dots, n$ in order with interleaved pops can produce exactly $C_n = \frac{1}{n+1}\binom{2n}{n}$ output permutations (1, 2, 5, 14, 42 for $n = 1..5$ ). A sequence is impossible iff it contains a pattern $\dots c \dots a \dots b \dots$ with $a < b < c$ (the "312" pattern) — e.g. 4, 2, 3, 1 contains 4, 2, 3.

Queue (FIFO)

A queue supports enqueue(x) at the rear and dequeue() from the front, both $O(1)$ with a proper implementation.

Python

from collections import deque
q = deque()
q.append(1)          # enqueue
q.append(2)
front = q.popleft()  # dequeue → 1

Circular queue (array implementation)

Indices wrap around with modulo arithmetic so the array is reused:

Elements occupy indices front … rear−1, wrapping past the end of the array.

Empty: front == rear. Full: (rear + 1) % n == front (one slot sacrificed), or keep an explicit count.
Number of elements: (rear - front + n) % n.

Variants

Structure	Operations	Python
Deque (double-ended queue)	add/remove at both ends, $O(1)$	`collections.deque`
Priority queue	insert, extract-min in $O(\log n)$	`heapq` (binary heap) — see trees and heaps
Queue from two stacks	amortised $O(1)$	inbox/outbox stacks
Stack from two queues	one operation $O(n)$

Applications

Breadth-first search, level-order tree traversal, scheduling (CPU, printers), buffering streams, and simulation of waiting lines. See graph traversals.

Quick revision

Practice questions

GATE-style questions: 3 one-mark and 7 two-mark. Wrong MCQs cost ⅓ of their marks in the real exam; MSQ and NAT have no negative marking. Attempt each before opening the solution.

Q1MCQ1 mark

Starting with an empty stack, the operations push(1), push(2), push(3), pop(), push(4), pop(), pop() are performed. The values popped, in order, are

Q2NAT2 marks

The value of the postfix expression 6 2 3 + - 3 8 2 / + * is ______.

Q3MCQ2 marks

The postfix form of the infix expression a + b * (c - d) / e is

Q4MCQ2 marks

The numbers 1, 2, 3, 4 are pushed onto a stack in this order, with pops allowed at any time in between. Which output sequence is impossible?

Q5NAT2 marks

A circular queue is stored in an array of size 5 with indices 0–4. Initially front = rear = 0. Enqueue writes at rear and then sets rear = (rear + 1) % 5; dequeue reads at front and then sets front = (front + 1) % 5. After 3 enqueues, 2 dequeues and 3 more enqueues, the value of rear is ______.

Q6MSQ1 mark

Which of the following are natural applications of a stack?

One or more options are correct.

Q7NAT2 marks

A queue is implemented with two stacks IN and OUT: enqueue pushes onto IN; dequeue pops from OUT, first moving all of IN onto OUT if OUT is empty. After enqueue(1), enqueue(2), enqueue(3), dequeue(), enqueue(4), dequeue(), dequeue(), the value returned by the third dequeue is ______.

Q8MCQ1 mark

In Python, which structure gives $O(1)$ enqueue and dequeue for a FIFO queue?

Q9NAT2 marks

The values 1, 2, 3, 4 are pushed in order onto an initially empty stack, with pops interleaved arbitrarily, until all four have been popped. The number of distinct output sequences possible is ______.

Q10MCQ2 marks

What does this program print?

Python

def ok(s):
    st = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in '([{':
            st.append(ch)
        elif not st or st.pop() != pairs[ch]:
            return False
    return not st

print([ok(x) for x in ["([]{})", "([)]", "(("]])