Picture the steel plate rack at a busy college canteen counter. A worker washes a plate and places it on top of the pile. The next clean plate goes on top of that one. When a student needs a plate, they don't reach into the middle of the stack — they take the one sitting on top, which happens to be the very last one placed there. Now picture a completely different scene: the queue outside an IRCTC ticket counter at a railway station. The person who arrived first stands at the front and gets served first. Someone who joins the queue now goes to the back and waits their turn, no matter how much they'd like to jump ahead. Both scenes involve a collection of things waiting to be processed, but the rule for "who goes next" is the exact opposite. That difference — last-served-first versus first-served-first — is the entire subject of this chapter, and it turns out to be one of the most useful ideas in all of computer science.
Two Ways to Organize a Line of Things
Every day you deal with collections where order matters: books piled on a study table, WhatsApp messages arriving in a group, people waiting at a bus stop, tabs open in a browser. Computer scientists noticed that almost all of these situations reduce to one of two access patterns, and they gave each pattern a name along with a strict set of allowed operations. These named patterns are called abstract data types, or ADTs. The word "abstract" here is important: an ADT is defined by what operations you're allowed to perform and what order those operations must respect, not by how the data happens to be stored in memory. This is the first idea that separates a real understanding of stacks and queues from a superficial one, so hold onto it — we'll come back to it once you've seen both structures in action.
The Stack: Last In, First Out
Go back to the plate rack. The rule is simple: whichever plate was placed most recently is the one removed next. Computer scientists call this rule LIFO — Last In, First Out. The data structure that enforces this rule is called a stack.
A stack allows exactly two operations that change its contents, plus a couple that only look at it:
- push — add a new item to the top of the stack.
- pop — remove and return the item currently at the top of the stack.
- peek (sometimes called top) — look at the item on top without removing it.
- isEmpty — check whether the stack has any items left.
Notice what's missing: there is no operation to grab the third plate from the top, or to insert a plate underneath the others. That restriction is not a limitation of a poorly designed system — it is the entire point. By refusing to let you touch anything except the top, a stack guarantees predictable, efficient behaviour, which we'll use to our advantage again and again.
In Python, the simplest way to build a stack is to use an ordinary list and treat the end of the list as the "top." This might feel backwards if you're imagining the plate rack drawn on paper with the top physically at the top, but it's a deliberate engineering choice: adding or removing from the end of a Python list is fast, while adding or removing from the front is slow, because every other element would have to shift over. We'll return to exactly why in a later section. For now, here is a stack of exam scores being built up and unwound:
stack = [] # an empty stack
stack.append(10) # push 10 -> stack is [10]
stack.append(20) # push 20 -> stack is [10, 20]
stack.append(30) # push 30 -> stack is [10, 20, 30]
print(stack.pop()) # removes 30 from the top, prints 30
print(stack.pop()) # removes 20 from the top, prints 20
print(stack) # [10]
Let's trace this line by line, because tracing is exactly the skill your CBSE exam will test. We start with an empty list. stack.append(10) places 10 at the end, so the list becomes [10]. stack.append(20) places 20 after it: [10, 20]. stack.append(30) gives us [10, 20, 30]. Here, 30 is the "top" because it's the most recently added element — it sits at the end of the list, not the beginning. The first stack.pop() removes and returns whatever is at the end, which is 30, so the program prints 30, and the list shrinks to [10, 20]. The second stack.pop() removes 20 and prints 20, leaving [10]. The final print(stack) shows [10]. Notice that 30 came out before 20, and 20 came out before 10 — exactly reversed from the order they went in. That reversal is the signature of LIFO behaviour.
The Queue: First In, First Out
Now consider the IRCTC ticket counter queue again. The rule here is the opposite: whoever has been waiting longest gets served next. This is called FIFO — First In, First Out, and the structure that enforces it is called a queue.
A queue's allowed operations are:
- enqueue — add a new item to the back (the "rear") of the queue.
- dequeue — remove and return the item at the front of the queue.
- front (or peek) — look at the item at the front without removing it.
- isEmpty — check whether the queue has any items left.
A queue has two ends that matter — the front, where items leave, and the rear, where items arrive — while a stack has only one active end. This is the structural difference that produces the behavioural difference: a stack reverses order, a queue preserves order.
Here's a subtlety worth getting right the first time. If you build a queue using a plain Python list the same way you built the stack, and you use .append() to add items to the rear, you must NOT use .pop() to remove from the front, because .pop() removes from the end of the list by default — that would give you a stack, not a queue. To remove from the front of a list you'd need .pop(0). That works correctly, but it has a hidden cost we'll examine shortly. For now, Python's standard library gives us a structure built exactly for this job: collections.deque, which supports fast removal from either end.
from collections import deque
queue = deque()
queue.append("Asha") # Asha joins the line -> deque(['Asha'])
queue.append("Rohan") # Rohan joins the line -> deque(['Asha', 'Rohan'])
queue.append("Meera") # Meera joins the line -> deque(['Asha', 'Rohan', 'Meera'])
print(queue.popleft()) # removes from the FRONT, prints Asha
print(queue) # deque(['Rohan', 'Meera'])
Tracing this: we start with an empty deque. Each .append() adds a name to the rear, so after three calls the deque holds Asha, Rohan, Meera in that order, with Asha at the front because she joined first. queue.popleft() removes the front element — Asha — and returns her, so the program prints Asha. The final print shows deque(['Rohan', 'Meera']): Rohan is now at the front, waiting to be served next, and Meera is still at the rear. Compare this to the stack trace above: there, the item added last (30) came out first. Here, the item added first (Asha) came out first. That's the whole difference between LIFO and FIFO laid bare in two short programs.
Seeing Both Side by Side
Two Misconceptions Worth Correcting Now
Misconception 1: "A stack or a queue is just another name for an array or a list." This is one of the most common mix-ups CBSE students make, and it undersells what's actually going on. A Python list is a general-purpose container — you can insert, delete, or read any element at any position. A stack or a queue is an abstract data type: a contract that says only certain operations are allowed, in a certain order. You can build a stack using a list, a deque, or even a fixed-size array with an index tracking the top — the underlying storage is an implementation detail. What makes something "a stack" is that the rest of your program is only allowed to push, pop, and peek — nothing else. If you write code that reaches into the middle of your "stack" to grab the fifth element directly, you no longer have a stack; you have a list that you're calling a stack, and any algorithm that depends on LIFO order will silently break.
Misconception 2: "Since Python lists can pop from the front with .pop(0), that's a perfectly good way to build a queue." It produces the correct values in the correct order, so it's easy to believe there's no problem. But there's a real cost hiding underneath. A Python list is stored in memory as a contiguous block, like a row of numbered lockers. When you remove the first element with .pop(0), every remaining element has to shift one locker to the left to close the gap. If your queue holds a thousand people waiting for train tickets, removing the front person means moving all 999 others down by one — every single time someone is served. This takes time proportional to the size of the queue, which computer scientists write as O(n) ("order n"). Adding or removing from the end of a list, by contrast, never requires shifting anything else, so it takes constant time, written O(1), regardless of how large the list is. That's precisely why our stack example used the end of the list as the "top," and why our queue example used collections.deque instead of a plain list: a deque is built internally so that both ends can be added to or removed from in O(1) time, with no shifting at all. For small queues in a classroom exercise the difference is invisible; for a real system serving millions of requests, choosing .pop(0) over a deque could be the difference between an app that feels instant and one that visibly lags.
Why Stacks Show Up Everywhere: Real Applications
The "undo" button in a word processor is a stack in disguise. Every edit you make is pushed onto a history stack. Press Ctrl+Z, and the most recent edit is popped and reversed — never the oldest one, because undoing things out of order would make no sense. Your browser's "back" button works the same way: every page you visit gets pushed onto a stack, and clicking back pops the most recently visited page.
An even deeper application lives inside every program you run: the call stack. When a function calls another function, the computer pushes a "stack frame" recording where to return to once the called function finishes. Consider computing a factorial recursively:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4))
Calling factorial(4) doesn't produce an answer immediately — it needs the answer to factorial(3) first, so a stack frame for factorial(4) is pushed and it calls factorial(3), which pushes its own frame and calls factorial(2), and so on down to factorial(0), which finally returns 1 without calling anything further. Now the stack unwinds, popping one frame at a time: factorial(1) resumes and computes 1 * 1 = 1; factorial(2) resumes and computes 2 * 1 = 2; factorial(3) resumes and computes 3 * 2 = 6; factorial(4) resumes and computes 4 * 6 = 24. The final printed value is 24. Notice that the calls went in the order 4, 3, 2, 1, 0, but the multiplications completed in the exact opposite order — a direct consequence of the call stack being LIFO. This is also why writing a recursive function with no stopping condition crashes your program: each call keeps pushing a new frame with nothing ever being popped, until the stack runs out of memory. In fact, the well-known programming question-and-answer website Stack Overflow takes its name directly from this very error — a "stack overflow" is what happens when a program's call stack grows past its allotted space.
Stacks are also the natural tool for checking whether brackets in an expression are balanced — a task that shows up constantly in compilers, calculators, and even in checking whether your handwritten math expression has matched parentheses. Here's the algorithm:
def is_balanced(expression):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for char in expression:
if char in "([{":
stack.append(char)
elif char in ")]}":
if not stack or stack.pop() != pairs[char]:
return False
return len(stack) == 0
Let's trace is_balanced("{a*(b+c)}"). Reading left to right: { is an opening bracket, so it's pushed — stack is ['{']. The letter a and the symbol * are neither opening nor closing brackets, so they're skipped. ( is pushed — stack is ['{', '(']. The letters b, +, c are skipped. Then ) arrives: the stack isn't empty, so we pop its top, which is (, and check whether it matches what ) expects — pairs[')'] is '(', and indeed it matches, so we continue with stack now ['{']. Finally } arrives: we pop {, and pairs['}'] is '{', another match, leaving the stack empty. The loop ends, and since len(stack) == 0, the function returns True — correctly balanced. Now trace the trickier case is_balanced("([)]"): ( is pushed — ['(']; [ is pushed — ['(', '[']; then ) arrives, we pop the top, which is [, but pairs[')'] expects ( — they don't match, so the function immediately returns False. This correctly flags ([)] as unbalanced, even though it has equal numbers of each bracket type, because the closing brackets appear in the wrong order relative to the opening ones. This is exactly the kind of ordering violation a stack is built to detect.
Why Queues Show Up Everywhere: Real Applications
A shared office printer processes documents in a queue: whichever document was sent first gets printed first, even if five more documents pile up behind it in the meantime, because printing the newest document first while an earlier one waits forever would be unfair and, worse, unpredictable. Customer support systems and call centres use the same idea — "your call will be answered in the order it was received" is FIFO stated in plain English. When you send a message on WhatsApp while your friend is offline, the messages queue up on the server and get delivered to their phone in the same order you sent them, not in reverse.
Operating systems use queues to decide which waiting task gets the processor's attention next, so that programs don't stall each other unfairly; a common scheme called round-robin scheduling gives each waiting task a short turn and then sends it to the back of the queue if it isn't finished, cycling through fairly. Later in your CS journey, when you study graph traversal algorithms, you'll meet Breadth-First Search, which explores a network — say, the shortest number of friend-connections between two people — one "layer" at a time, and it does this by keeping the nodes still to be explored in, precisely, a queue.
Circular Queues: Fixing a Wasted-Space Problem
If you implement a queue using a fixed-size array instead of a flexible list — common in embedded systems with limited memory, like the kind that might run on a small microcontroller — a naive approach tracks a front index and a rear index, incrementing front every time you dequeue. The trouble is that once rear reaches the end of the array, the array looks "full" even though the front slots emptied out earlier are sitting unused. The standard fix is a circular queue: after the rear index reaches the last position, it wraps back around to index 0, reusing the freed space, as long as it doesn't run into the front index. This wrap-around is usually implemented with the modulo operator — computing rear = (rear + 1) % capacity — so the index cycles 0, 1, 2, ..., capacity−1, 0, 1, 2, ... indefinitely. The two situations to watch for are an empty queue and a full queue, which can look confusingly similar (front equals rear in both cases) unless you keep an explicit count of how many items are currently stored.
Test Your Understanding
Work through each of these before checking the answer that follows it — the value comes from tracing it yourself first.
- A stack starts empty. Perform, in order: push(5), push(15), push(25), pop(), push(35), pop(), pop(). List the three popped values in order, and state what remains in the stack.
Answer: After push(5), push(15), push(25), the stack is [5, 15, 25]. pop() removes 25. push(35) gives [5, 15, 35]. pop() removes 35. pop() removes 15. The popped values in order are 25, 35, 15, and the stack ends with just [5] remaining. - A queue at a ticket counter has Vikram, then Sana, then Tariq waiting, in that order. Divya joins, then Om joins. Two people are served. Who are they, and in what order will the remaining people be served?
Answer: The two served are the two who arrived earliest — Vikram, then Sana — since a queue is FIFO. The remaining people, in the order they'll be served, are Tariq, then Divya, then Om. - A classmate implements a "queue" using a Python list, adding people with
.append()but removing them with.pop()(no argument). What actually happens, and why is it wrong?
Answer:.pop()with no argument removes from the end of the list, not the front. So the most recently added person gets served first, which is LIFO behaviour — this has secretly built a stack, not a queue, and will serve people in exactly the wrong, unfair order. - Trace
is_balanced("([)]")using the bracket-matching algorithm above and state the final answer, showing the stack's contents at each step.
Answer:(pushed → ['('].[pushed → ['(', '['].)arrives: pop top, which is '[', but ')' expects '(' — mismatch, so the function returns False immediately. The expression is correctly identified as unbalanced.
Quick Recap
A stack enforces Last In, First Out: the most recently pushed item is always the first one popped, which makes it the natural tool for undo history, browser back-buttons, function call stacks, and detecting mismatched brackets. A queue enforces First In, First Out: the item that has waited longest is always the first one dequeued, which makes it the natural tool for fair scheduling, printer jobs, message delivery, and any real-world "take a number" line. Both are abstract data types defined by which operations they permit — push/pop/peek for a stack, enqueue/dequeue/front for a queue — not by the underlying storage, though the choice of storage (a plain list versus a deque versus a circular array) has real, measurable consequences for speed. Whenever you're deciding which one fits a problem, ask a single question: when something needs to come out, should it be the one that arrived most recently, or the one that's been waiting longest? That answer tells you immediately whether you need a stack or a queue.
Think About It
Think about this: How would you explain stacks and queues: lifo and fifo 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.