Two Lines You Already Know
Picture the steel plate rack in a college canteen. A worker washes a plate and places it on top of the stack. The next worker who needs a plate does not reach into the middle of the pile — they take the plate sitting right on top, because that is the only one they can physically reach. The plate that was placed most recently is the plate that gets used first. The plate placed at the very bottom of the pile, from this morning, will only be reached once every plate above it has been removed.
Now picture the ticket counter at your nearest railway reservation office. Rahul reaches the counter first and joins the line. Priya arrives two minutes later and stands behind him. Ahmed arrives after that and stands behind Priya. When the clerk calls the next customer, it is Rahul who steps up — not Ahmed, even though Ahmed is standing right there. The person who joined the line first is served first. Everyone who joins later waits behind everyone who joined earlier.
These two everyday scenes are not just similar to each other — they are opposites, and computer science has exact names for both. The plate rack behaves like a stack, where the last item added is the first item removed. The ticket line behaves like a queue, where the first item added is the first item removed. Every programming language you will ever use, and a large fraction of the algorithms running inside apps like IRCTC, WhatsApp, and your web browser, are built on exactly these two ideas. This chapter builds both from the ground up, formalizes them precisely, and then shows you the real code and real algorithms that depend on them.
Formalizing the Plate Rack: LIFO and the Stack
The rule the plate rack follows has a name: LIFO, which stands for Last In, First Out. Whatever item entered the structure most recently is the one that leaves first. A data structure that enforces this rule is called a stack.
A stack supports exactly four operations, and it is important that you know all four by name because every textbook and every exam question uses this exact vocabulary:
- push(x) — place a new item x on top of the stack.
- pop() — remove and return the item currently on top of the stack.
- peek() or top() — look at the item on top without removing it.
- is_empty() — check whether the stack has any items left.
Notice what is deliberately missing from this list: there is no operation to look at or remove the third item from the top, or the item at the bottom. A stack only ever exposes its top. This restriction is not a limitation someone forgot to fix — it is the entire point. By refusing to let you touch anything except the top, a stack guarantees LIFO order automatically, and that guarantee is what makes it useful.
Formalizing the Ticket Line: FIFO and the Queue
The rule the ticket line follows also has a name: FIFO, which stands for First In, First Out. Whatever item entered the structure earliest is the one that leaves first. A data structure that enforces this rule is called a queue.
A queue has its own four operations, and note how their names deliberately differ from a stack's, even though both structures "add" and "remove" items:
- enqueue(x) — add a new item x to the back (the "rear") of the queue.
- dequeue() — remove and return the item at the front of the queue.
- peek() or front() — look at the item at the front without removing it.
- is_empty() — check whether the queue has any items left.
A queue therefore needs to keep track of two positions — the front, where removal happens, and the rear, where addition happens — while a stack only ever needs to track one position, the top, because both push and pop happen at the same end. This single difference is the root of everything else that makes stacks and queues behave, and get implemented, differently.
The Diagram: Both Structures Side by Side
On the left, plates 5, 8, and 2 were pushed in that order, so 2 sits on top — it will be the first one popped. On the right, Rahul, Priya, and Ahmed enqueued in that order, so Rahul sits at the front — he will be the first one dequeued. Same three items on each side, opposite rule for which one comes out first.
Building a Stack with Real Code
A stack is not a new kind of storage — it is an ordinary list with a strict rule about which end you are allowed to touch. Here is a complete, working stack built on top of Python's list, which already supports adding and removing from its end in a single step:
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if self.is_empty():
raise IndexError("pop from empty stack")
return self.items.pop()
def peek(self):
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
Trace this line by line, keeping a running picture of self.items in your head, exactly as you would be expected to on a CBSE practical exam:
s = Stack()
s.push(5) # items = [5]
s.push(8) # items = [5, 8]
s.push(2) # items = [5, 8, 2]
print(s.peek()) # looks at items[-1] -> prints 2, items unchanged
print(s.pop()) # removes and returns items[-1] -> prints 2, items = [5, 8]
print(s.pop()) # prints 8, items = [5]
print(s.is_empty()) # len(items) == 0 is False -> prints False
Two design choices here matter more than they look. First, push and pop both act on the same end of the list — index -1, the last position — never the front. This is exactly why a Python list makes an efficient stack: adding or removing the last element takes a fixed, small number of steps no matter how large the list already is, because nothing else in the list has to move. Second, pop checks is_empty() first and raises an error rather than silently returning something meaningless. A stack that has nothing left to pop is a genuine error condition, not an edge case to shrug off — you will see exactly this failure, called a stack underflow, if you ever call pop() one time too many.
Building a Queue — and Why the Array Trick Doesn't Work the Same Way
It is tempting to build a queue exactly like a stack, just removing from the front instead of the back:
queue = []
queue.append("Rahul") # queue = ["Rahul"]
queue.append("Priya") # queue = ["Rahul", "Priya"]
queue.append("Ahmed") # queue = ["Rahul", "Priya", "Ahmed"]
queue.pop(0) # removes "Rahul", returns "Rahul"
This works and gives the right answer — but it is quietly expensive. When pop(0) removes the element at index 0, Python cannot just delete it and leave a gap; a list has to stay contiguous in memory. So it shifts every remaining element one position to the left: the item that was at index 1 moves to index 0, index 2 moves to index 1, and so on. For a queue holding 3 people this shift is unnoticeable, but for a queue holding 3,000 pending print jobs or 3,000 waiting API requests, every single dequeue would require shifting roughly 3,000 items — the cost grows with the size of the queue, which is a genuinely bad property for an operation you expect to run constantly.
This is why Python's standard library ships a purpose-built structure for this exact job: collections.deque ("deque" is short for "double-ended queue"). It is implemented internally so that adding or removing from either end takes a fixed, small number of steps, with no shifting required:
from collections import deque
line = deque()
line.append("Rahul") # enqueue -> Rahul joins the rear
line.append("Priya") # enqueue -> Priya joins the rear
line.append("Ahmed") # enqueue -> Ahmed joins the rear
print(line.popleft()) # dequeue -> removes and returns "Rahul"
print(line.popleft()) # dequeue -> removes and returns "Priya"
print(line) # deque(["Ahmed"])
The lesson generalizes beyond Python: a stack is naturally efficient when built on a simple array because both its operations happen at one end, but a queue needs either a dedicated structure like a deque, or a technique called a circular queue, where the "front" and "rear" are tracked as two indices that wander forward and wrap back around to position 0 when they reach the end of the array — avoiding both the shifting cost and the need to keep growing the array. You do not need to implement a circular queue by hand to use this chapter's ideas correctly, but you should be able to explain, in an exam answer, why a naive front-removal queue is slower than a naive stack, and that reason is the shifting cost above.
Worked Example: Checking Balanced Brackets with a Stack
Here is the single most common real use of a stack in a CBSE Computer Science course, and also in real compilers: deciding whether an expression's brackets are correctly matched. Consider the expression ((a+b)*(c-d)). A human can see at a glance that it is balanced, but a program needs a precise rule, and a stack provides exactly that rule.
def is_balanced(expression):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for char in expression:
if char in '([{':
stack.append(char)
elif char in ')]}':
if not stack or stack[-1] != pairs[char]:
return False
stack.pop()
return len(stack) == 0
The idea: every opening bracket gets pushed. Every closing bracket must match whatever opening bracket is currently on top of the stack — if it does not match, or if the stack is already empty when a closing bracket shows up, the expression is broken. Trace it character by character on ((a+b)*(c-d)):
'(' -> push stack = ['(']
'(' -> push stack = ['(', '(']
'a','+','b' -> ignored (not brackets)
')' -> top is '(', matches -> pop stack = ['(']
'*' -> ignored
'(' -> push stack = ['(', '(']
'c','-','d' -> ignored
')' -> top is '(', matches -> pop stack = ['(']
')' -> top is '(', matches -> pop stack = []
end of string reached, stack is empty -> return True
Now trace a broken expression, (a+b], to see the failure path: '(' is pushed, giving stack = ['(']; a, +, b are ignored; then ']' arrives, and pairs[']'] is '[', but stack[-1] is '(' — they do not match, so the function returns False immediately, correctly flagging the mismatched brackets even though the string never actually runs out of brackets to check. This is precisely the kind of check your code editor runs, live, every time it underlines a mismatched bracket in red as you type.
Worked Example: Simulating the Ticket Counter with a Queue
Return to Rahul, Priya, and Ahmed at the counter. Suppose the counter opens at the 0-minute mark and serves exactly one person every 2 minutes. Because a queue enforces FIFO, we can calculate each person's waiting time using nothing but arrival order:
from collections import deque
names = ["Rahul", "Priya", "Ahmed", "Sana"]
line = deque(names)
service_time = 2
clock = 0
while line:
person = line.popleft()
print(person, "served at minute", clock)
clock += service_time
Running this through by hand: the loop starts with line = deque(["Rahul","Priya","Ahmed","Sana"]) and clock = 0. First iteration pops "Rahul", prints "Rahul served at minute 0", then clock becomes 2. Second iteration pops "Priya", prints "Priya served at minute 2", clock becomes 4. Third pops "Ahmed", prints "Ahmed served at minute 4", clock becomes 6. Fourth pops "Sana", prints "Sana served at minute 6", clock becomes 8. The loop then finds line empty and stops. Notice that Sana, who arrived last, is guaranteed to wait longest — 6 minutes — purely because of arrival order, with no other rule needed. This is the fairness property that makes FIFO the natural choice for ticket counters, print queues, and customer support call queues: whoever showed up first gets served first, full stop.
A Second Real Use of a Stack: The Function Call Stack
Stacks are not only something you build yourself — one is running invisibly underneath every program you write, tracking function calls. Consider this recursive factorial function:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
When you call factorial(3), Python does not finish that call immediately — it needs the result of factorial(2) first, so it pushes a record of the current call (with n = 3, paused mid-calculation) onto an internal call stack and starts factorial(2). That call, in turn, needs factorial(1), so it too gets pushed and paused. That needs factorial(0), which is pushed and paused. Only factorial(0) can actually finish right away, because n == 0 is true, so it returns 1 without waiting on anything else. At that point the call stack looks, from bottom to top, like: factorial(3) waiting, factorial(2) waiting, factorial(1) waiting. The stack unwinds top-first, exactly like popping plates: factorial(1) resumes, computes 1 * 1 = 1, and returns; factorial(2) resumes, computes 2 * 1 = 2, and returns; factorial(3) resumes, computes 3 * 2 = 6, and returns 6 as the final answer. The very last call made — factorial(0) — was the first one to return. That is LIFO, operating exactly the way the plate rack does, just with paused function calls standing in for plates. This is also precisely why deeply recursive functions can crash with a RecursionError in Python: the call stack has a finite size, and enough nested, unfinished calls piling up will exhaust it — a real stack overflow, the same name given to the classic error and to the well-known programmer question-and-answer website.
Common Misconception, Corrected
A mistake students often make once they have seen both structures implemented on top of a Python list is assuming that a stack's pop() and a naive queue's "remove the front" are basically the same operation, just aimed at different ends of the same kind of list — and therefore equally cheap. They are not. list.pop() with no argument removes the last element and costs a fixed, small number of steps regardless of list size, because nothing shifts. list.pop(0) removes the first element and forces every remaining element to shift down by one position, so its cost grows with how many items are left in the list. The direction you remove from is not a cosmetic detail — it is the entire reason stacks are naturally cheap on arrays while naive queues are not, and it is exactly why production systems use a deque or a circular queue for anything queue-shaped rather than a plain list with front-removal.
Where This Shows Up Around You
Once you know to look for LIFO and FIFO, you will notice them everywhere in software you already use. Your browser's back button is a stack: every page you visit gets pushed, and pressing back pops the most recently visited page — it can never take you to the very first page you visited today without first popping through everything in between. The undo feature in a word processor works the same way: each edit is pushed onto an undo stack, and Ctrl+Z pops the most recent one first. A printer's job queue, by contrast, is a FIFO structure: whichever document you sent to print first comes out of the printer first, regardless of which document is smaller. Algorithms that explore a network level by level — such as finding the shortest chain of mutual connections between two people, or the shortest route out of a maze — use a queue to decide what to visit next, a technique called breadth-first search. Algorithms that instead commit to one path as deep as possible before backtracking — such as solving a Sudoku puzzle by trying a digit, going deeper, and undoing the choice if it fails — use a stack, a technique called depth-first search. In every one of these cases, the choice between a stack and a queue is not arbitrary; it is dictated entirely by whether the problem needs "undo the most recent thing" or "honor whoever arrived first."
Stack vs Queue: Side-by-Side Summary
- Order rule: Stack is LIFO (last in, first out). Queue is FIFO (first in, first out).
- Access points: Stack has one active end (the top). Queue has two active ends (front for removal, rear for addition).
- Core operations: Stack uses push and pop. Queue uses enqueue and dequeue.
- Efficient array implementation: Stack — trivial, both operations at the list's end. Queue — needs a deque or circular queue to avoid costly shifting.
- Classic real examples: Stack — undo history, browser back button, function call stack, depth-first search. Queue — print spooler, ticket counter, message delivery order, breadth-first search.
- Failure mode: Stack underflow (popping an empty stack) or stack overflow (too many pushes/nested calls). Queue underflow (dequeuing an empty queue).
Test Yourself
Q1. A stack starts empty. The operations push(10), push(20), pop(), push(30), pop(), pop() are performed in that order. What does each pop() return, and what is in the stack at the very end?
Answer: After push(10), push(20): stack = [10, 20]. First pop() returns 20, stack = [10]. push(30): stack = [10, 30]. Second pop() returns 30, stack = [10]. Third pop() returns 10, stack = [] (empty).
Q2. A queue starts empty. The operations enqueue("X"), enqueue("Y"), dequeue(), enqueue("Z") are performed in that order. What is the queue's content from front to rear at the end, and what did dequeue() return?
Answer: After enqueue("X"), enqueue("Y"): queue = [X, Y] (X at front). dequeue() returns "X", queue = [Y]. enqueue("Z"): queue = [Y, Z], with Y still at the front.
Q3. Trace is_balanced("([)]") using the algorithm given earlier. Is it balanced?
Answer: '(' pushed, stack=['(']. '[' pushed, stack=['(','[']. ')' arrives: pairs[')'] is '(', but stack[-1] is '[', so they do not match — the function returns False immediately. The brackets are not balanced, even though every bracket does have a partner somewhere in the string — order matters, not just counting.
Q4. Why is list.append(x) followed later by list.pop() an efficient way to run a stack in Python, while list.append(x) followed later by list.pop(0) is an inefficient way to run a queue?
Answer: Both operations in the stack pair act on the last position of the list, which requires no shifting of other elements. pop(0) removes the first position, which forces every remaining element to shift one step left to keep the list contiguous, so its cost grows as the list grows.
Q5. A recursive function calls itself 500 levels deep before hitting its base case. Which data structure is responsible for remembering all 500 paused calls, and in what order do they finish?
Answer: The function call stack. It is LIFO, so the most recently made call (the 500th, deepest one) is the first to finish and return, and the original outermost call is the last to finish.
Chapter Summary
A stack enforces Last In, First Out order using only two active operations, push and pop, both acting on a single end called the top — this is what makes it a natural, efficient fit for arrays, and it is the exact mechanism behind undo histories, browser back buttons, and every function call your programs make. A queue enforces First In, First Out order using enqueue at the rear and dequeue at the front, modeling fairness in waiting lines, print jobs, and message delivery — but because it touches both ends of the underlying storage, it needs either a deque or a circular queue to stay efficient, unlike a stack's free ride on a plain array. The choice between the two is never cosmetic: it is decided entirely by whether a problem needs "undo the most recent step" behavior or "serve whoever arrived first" behavior, and recognizing which one a problem calls for is one of the most useful instincts you can build in early algorithmic thinking.
Think About It
Think about this: How would you explain stacks and queues: lifo and fifo data structures to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.
Practice Exercises
Now it is time to practice! Complete these challenges to solidify your understanding:
- Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
- Exercise 2: Find a real-world example where stacks and queues: lifo and fifo data structures is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
- Exercise 3: Create a mind-map connecting stacks and queues: lifo and fifo data structures to at least 3 other topics you have studied.