Two everyday scenes. Scene one: the tatkal counter at a railway station — whoever joined the line first gets served first, and nobody argues, because it's the fairest rule there is. Scene two: the steel plates stacked in your kitchen rack — you always take the plate on top, the one washed last, because digging out the bottom plate would be absurd.
Two opposite rules: first-come-first-served, and last-placed-first-taken. In code they are the queue and the stack — and this lesson's real job is training you to hear which rule a problem is quietly asking for.
Two rules, two structures
A stack is LIFO — last in, first out. One open end: you push onto the top, you pop from the top. A queue is FIFO — first in, first out. Two ends: join at the back, leave from the front.
That's the entire theory. Both do their core operations in O(1). Everything interesting is in choosing which rule your problem needs — so let's build that instinct.
The stack: push, pop, peek
In Python, a plain list IS a stack — append and pop both work at the end in O(1):
stack = []
stack.append(10) # push
stack.append(20)
stack.append(30)
print(stack.pop()) # -> 30, the LAST one in
print(stack[-1]) # peek: look at the top without removing
print(stack.pop()) # -> 20Result
30 20 20
Here is the mental model that makes stacks click: a stack remembers the most recent UNFINISHED thing. Push when something starts; pop when it completes. That's exactly why function calls live on a "call stack" — the most recently called function is the one that must finish first. You watched its frames pile up in lesson 1.
The queue — and a Python trap
Student question: for a queue, can't I just use a list with append() and pop(0)?
You can — and you'll regret it. Remember lesson 2: pop(0) is a front-delete on an array, so every remaining element shifts left. O(n) per dequeue. Draining a 1-lakh-person queue this way does ~500 crore shifts. The right tool is collections.deque, built for both ends:
from collections import deque
q = deque()
q.append("ravi") # enqueue at the back O(1)
q.append("priya")
q.append("amit")
print(q.popleft()) # dequeue from the front O(1)
print(q.popleft())
# NOT this:
# q = []; q.pop(0) # O(n) EVERY time - the array shift trapResult
ravi priya
One import, and the queue is honest O(1) at both ends. Using deque unprompted is a small signal to interviewers that you've actually written code before.
Where they hide in real systems
| System | Structure | The rule at work |
|---|---|---|
| Undo (Ctrl+Z) | stack | undo the MOST RECENT action |
| Browser back button | stack | return to the page you just left |
| Function calls / recursion | stack | innermost call finishes first |
| Printer / job queue | queue | first submitted, first printed |
| Chat message delivery | queue | messages arrive in send order |
| BFS traversal | queue | explore nearest first |
| DFS traversal | stack | dive deepest first |
Look hard at the last two rows. In the graph lessons you will see that BFS and DFS are the same algorithm with the container swapped — choose the container and you have chosen the exploration order. A data structure decision that IS an algorithm decision.
Let's solve one properly: balanced brackets
The signature stack problem, asked everywhere from TCS MCQs to Amazon phone screens: is ([]{}) a valid bracket string? Is ([)]?
First, let's understand what "valid" really demands. Read ([)] character by character: when the ) arrives, which opener is it trying to close? The most recent unclosed opener is [ — and ) doesn't match [. Invalid. So the rule of nesting is:
Every closer must match the most recent unfinished opener.
Read that sentence again — "most recent unfinished thing". You already know whose job description that is.
Why not a simple counter?
Hold on though — before reaching for a structure, let's try the cheapest idea, because a good engineer always does. What if we just count? +1 for every opener, −1 for every closer; valid if the count never dips below zero and ends at zero.
For ONE bracket type, this works perfectly — try it on (()()). Now run it on ([)]: two openers, two closers, count never negative... the counter says valid. But we just saw it's invalid!
What information did the counter throw away? It remembered how many things were unfinished — but not what they were, in what order. The moment types can interleave, we need the full memory of unfinished openers, newest on top. That is precisely a stack, and now the algorithm writes itself:
def is_valid(s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in "([{":
stack.append(ch) # a new unfinished opener
else:
if not stack: # a closer with nothing open
return False
if stack.pop() != pairs[ch]: # closes the WRONG opener
return False
return not stack # anything left unclosed?Each line earns its place: not stack inside the loop catches )( (closing before opening), the pop-compare catches type mismatches, and the final not stack catches ((( (openers nobody closed). Those three checks ARE the three ways a bracket string can go wrong.
Dry run: the stack catches what the counter missed
input "([)]"
ch = ( push stack: [ ( ]
ch = [ push stack: [ ( [ ]
ch = ) pop -> [ but ) needs ( -> MISMATCH -> False
input "([]{})"
ch = ( push stack: [ ( ]
ch = [ push stack: [ ( [ ]
ch = ] pop -> [ matches -> ok stack: [ ( ]
ch = { push stack: [ ( { ]
ch = } pop -> { matches -> ok stack: [ ( ]
ch = ) pop -> ( matches -> ok stack: []
end: stack empty -> TrueOne pass, O(n) time, O(n) stack in the worst case (all openers). Notice the deeper thing: the nesting structure of brackets and the LIFO structure of a stack are the same shape — which is why the solution feels like it wrote itself once the rule was stated.
A taste of the monotonic stack
One level up sits a pattern product companies love. Problem: for each element of [4, 5, 2, 10], find the next greater element to its right (answer: [5, 10, 10, -1]).
The natural approach — for each element, scan rightward until something bigger appears — is O(n²). Where is the wasted work? When 10 arrives, it answers 2 AND 5 (and would have answered anything smaller) in one appearance — but the naive scan re-discovers 10 separately for each of them.
So flip the viewpoint: keep a stack of elements still waiting for their answer. When a new element arrives, it answers every waiting element smaller than itself — pop them all — then joins the queue of waiters itself:
def next_greater(arr):
res = [-1] * len(arr)
waiting = [] # indices; their values decrease
for i, x in enumerate(arr):
while waiting and arr[waiting[-1]] < x:
res[waiting.pop()] = x # x answers this waiter
waiting.append(i)
return res
print(next_greater([4, 5, 2, 10]))Result
[5, 10, 10, -1]
"There's a while inside the for — isn't that O(n²)?" Count per element, not per iteration: each index is pushed once and popped at most once in its whole life, so total work ≤ 2n → O(n). This charge-the-element-not-the-loop argument is called amortised analysis, and it returns twice more in this course. The same skeleton solves stock span, daily temperatures, and largest rectangle in a histogram.
What if...?
What if I pop an empty stack? Python raises an IndexError. Guard every pop that could face empty: if not stack: ... — in brackets, that guard IS one of the three correctness checks.
What if the bracket string is empty? The loop never runs, the stack is empty, we return True. An empty string is validly balanced — confirm that reading with your interviewer; it's a spec question, not a code question.
What if I need the minimum of a stack in O(1) at any moment? One number can't survive pops — popping the minimum needs the previous minimum. The fix (a second stack of "minimum so far at each level") is the min-stack problem in your Practice Zone.
What if I only have stacks but need a queue? Two stacks: one for arrivals, one for departures; drain the first into the second only when the second is empty — two LIFO reversals cancel into FIFO, amortised O(1) per operation. Also in the Practice Zone, with the amortised argument spelled out.
Common mistakes
- Using
list.pop(0)as a dequeue — O(n) per operation; usedeque.popleft(). - Popping without an empty-check where empty is possible.
- Forgetting the final
return not stackin brackets — quietly accepts(((. - Trusting a counter for multi-type bracket matching — it cannot see interleaving like
([)]. - In queue-from-two-stacks, refilling the out-stack while it still holds elements — re-reversing corrupts the order; refill only when empty.
- Calling the monotonic stack O(n²) because of the nested while — each element is pushed and popped at most once.
How do I recognise stack/queue problems?
- "matching", "nested", "undo", "most recent", "go back" → stack. The tell is needing the newest unfinished thing.
- "in order of arrival", "level by level", "nearest first", "buffer" → queue. The tell is fairness by time.
- "next greater/smaller element", "span", "previous larger" → monotonic stack.
- expression evaluation, infix/postfix → stack (the Infosys favourite — it appears on the company pages).
When you hear one of these words, don't start coding. First say which rule — LIFO or FIFO — the problem's story is enforcing. The structure follows from the rule, never the other way around.
Quick revision
| Operation | Stack (list) | Queue (deque) | Note |
|---|---|---|---|
| Add | push O(1) | enqueue O(1) | list push: amortised (resizes) |
| Remove | pop O(1) | dequeue O(1) | list.pop(0) is the O(n) trap |
| Peek | O(1) | O(1) | — |
| Search inside | O(n) | O(n) | not what they're for |
One thing to remember
Stack = the most recent unfinished thing. Queue = fairness by arrival. Hear which sentence the problem is speaking, and the structure — and often the whole solution — picks itself.
Practice Zone — PYQs from real selection rounds
Six MCQs, then the three classics: balanced brackets, a min-stack with O(1) minimum, and a queue built from two stacks — each solution carries its trace.
You push 1, 2, 3, 4 onto a stack, then pop twice. What do the pops return, in order?
Asked in
Which of these is a natural QUEUE, not a stack?
Asked in
Checking balanced brackets — "([]{})" valid, "([)]" invalid — uses a stack because:
Asked in
Why is list.pop(0) a bad queue dequeue in Python, and what is the right tool?
Asked in
A queue built from two stacks (push onto in, pop from out, refill out by draining in when empty) has what dequeue cost?
Asked in
For arr = [4, 5, 2, 10], the 'next greater element' for each position is:
Asked in
Hands-on tasks:
Check whether a bracket string is valid: every opener closed by the right type, in the right order. Trace your code on "([)]".
Asked in
Design a stack that supports push, pop and get_min — all O(1). Pushing 5, 3, 7, 2 then popping once should leave min = 3.
Asked in
Implement a FIFO queue using only two stacks. enqueue(1), enqueue(2), enqueue(3), then two dequeues must return 1 then 2.
Asked in
FAQ
What is a deque, exactly?
A double-ended queue: O(1) append and pop at BOTH ends. It can impersonate a stack (use one end) or a queue (use both), which is why collections.deque answers most "which container?" questions in Python. Under the hood it's a linked list of fixed-size blocks — lesson 3 paying rent.
What is a priority queue then — a fancier queue?
A different rule entirely: elements leave by urgency, not arrival — the hospital emergency room versus the railway line. It's built on a heap, and it gets its own lesson: lesson 8.
Why do deep recursions crash with 'maximum recursion depth exceeded'?
Because the call stack is a real stack with a size limit (~1000 frames by default in Python). Any recursion can be rewritten with an explicit stack you control — same logic, heap-sized limit — a conversion worth practising once.
Can I build a stack from two queues — the reverse trick?
Yes: push into one queue; to pop, rotate all but the last element into the other queue. One operation becomes O(n). It's asked occasionally as the mirror of queue-from-two-stacks — mostly to check you understood the first trick rather than memorised it.
Two rules down. Next, the structure that answers "have I seen this before?" among crores of records in constant time — Lesson 5: Hash Tables →