Stacks & Queues Foundations

8 concept walkthroughs, each with a worked explanation and an interactive visualization, before you start solving problems in this area.

A Stack: A Pile of Trays

Think of a pile of trays at a canteen. Each tray has a number written on it: 10, then 20, then 30 on top. You may only touch the top tray. To add a tray, you put it on top. To remove a tray, you lift off the top one. So the last tray put on is the first tray taken off. This rule is called last in, first out, and a pile that follows it is called a stack. In Python a stack is just a list, a row of boxes written in square brackets, like [10, 20, 30]. The end of the list is the top of the pile. stack.append(30) puts a value on top (we say push). stack.pop() lifts the top value off and hands it back (we say pop). stack[-1] looks at the top without removing it (we say peek). The number in the brackets is an index, the position of a box, and -1 means the last box. An empty pile is []. The loop while stack: keeps going as long as the pile has something in it, and len(stack) counts the trays.

The intuition

A stack always hands you the newest thing first, so it gives things back in the reverse of the order they arrived. That is exactly what you want when the newest thing is the one you must deal with first. It is also cheap. Push, pop and peek each take about one step, whether the pile has 3 trays or 3 million, because they only touch the top and nothing else moves. Big-O is a short way of writing how the number of steps grows as the data grows. Here the steps do not grow at all, and we write it O(1), said order one.

A real-world analogy

A pile of trays at a canteen. The pile is the list. The top tray is the last box of the list. Putting a tray on top is append, lifting the top tray is pop, and glancing at the top tray without lifting it is stack[-1]. Nobody pulls a tray out of the middle, because the trays above it would fall. It is the same in a stack: the only tray you can reach is the top one, and nothing in the pile moves except at the top.

stack = []                 # an empty pile
stack.append(10)           # put a tray on top
stack.append(20)
stack.append(30)
print(stack[-1])           # look at the top without taking it: 30
top = stack.pop()          # take the top tray off
print(top, stack)          # 30 [10, 20]
while stack:               # keep going while the pile is not empty
    print(stack.pop())     # 20, then 10
print(len(stack) == 0)     # True: the pile is empty

A Queue: A Line at a Counter

A queue is a line at a service counter. Ana arrives first, then Bo, then Cy. The person at the front is served first, and new people join at the back. So the first one in is the first one out. We call this first in, first out. It is the opposite of a stack, where the newest comes out first. In Python we do not keep a line in a plain list. We use a deque (said "deck"), which you get with from collections import deque. A deque is a list-like row that is fast to change at both ends. line.append("Ana") makes a person join at the back. line.popleft() serves the person at the front and hands them back. line[0] looks at the front without removing anyone. The words in quotes are strings, pieces of text. And while line: loops as long as somebody is still waiting, just as it does for a stack.

The intuition

Why a deque and not a list? A list has a pop(0) that removes the front, but then every person behind must slide one box to the left to close the gap. With Bo and Cy that is 2 slides. With a line of 1,000,000 people it is 999,999 slides, just to serve one person. We say the cost grows in step with the length of the line: if n is the number of items, it is about n steps, written O(n). A deque's popleft simply lets go of the front box, and nobody slides: one step, O(1), however long the line is.

A real-world analogy

A line at a bakery counter. The line is the deque. The person at the front is line[0]. A new customer walks to the back of the line (append), and the baker serves whoever has waited longest (popleft). With a plain list it would be as if the whole line had to shuffle one step forward every time someone was served. With a deque the front person simply leaves, everybody else keeps standing where they are, and the next person becomes the front.

from collections import deque     # deque: a line that is fast at both ends
line = deque()                    # an empty line
line.append("Ana")                # a person joins at the back
line.append("Bo")
line.append("Cy")
print(line[0])                    # the front of the line: Ana
served = line.popleft()           # the front person leaves
print(served, list(line))         # Ana ['Bo', 'Cy']
slow = ["Ana", "Bo", "Cy"]        # the same line kept in a list
slow.pop(0)                       # works, but Bo and Cy each slide one box left
print(slow)                       # ['Bo', 'Cy']

Matching Pairs: The Newest Unfinished Thing

Brackets come in pairs: an opener such as ( and a closer such as ). A text is balanced when every opener is closed by its own kind, in the right order. In {[()]}, the ( was opened last, so it must be closed first, then [, then {. Look at the word unfinished: an opener is unfinished until its closer arrives. A closer can only finish the newest unfinished opener, and "newest first" is exactly what a stack gives. So we walk through the text (a for loop over a string gives one character per round), push every opener, and for every closer we pop the top and check that it is the matching opener. To know which opener goes with which closer we use a dict, a small table of labels and values: pairs = {')': '(', ']': '[', '}': '{'}. Then pairs[')'] is '(' and ch in pairs asks whether ch is one of the labels. The code is wrapped in a function: def names it and return hands back the answer.

The intuition

Two things can go wrong, and the stack catches both. First, a closer arrives and the pile is empty, or the top is the wrong type: nothing unfinished matches it. Second, the text ends and openers are still on the pile: they were never finished, so the pile must be empty at the end. The same shape appears wherever something newer is started inside something older and must finish first: nested brackets, the undo button of an editor (the last change is undone first), and function calls, where a function that calls another one waits until the inner one has returned.

A real-world analogy

Walking into nested rooms through three doors. You open door {, then door [, then door (. Each door you open is pushed on the pile. To walk back out, you must close the door you opened last, ( first, then [, then {. The door you may close is always the top of the pile. If someone asks you to close a door you never opened, or the wrong door, the trip is wrong. And if you finish and a door is still open, the house was not properly closed.

def is_balanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}   # closer -> its opener
    stack = []
    for ch in s:
        if ch in pairs:                      # a closer arrived
            if not stack:
                return False                 # nothing is waiting for it
            if stack.pop() != pairs[ch]:
                return False                 # the newest opener is the wrong type
        else:
            stack.append(ch)                 # an opener waits
    return not stack                         # leftovers mean not balanced
print(is_balanced("{[()]}"), is_balanced("(]"), is_balanced("(("), is_balanced(")"))

A Stack That Remembers: Notes on Every Tray

Suppose someone keeps asking: what is the smallest number on the pile right now? You could look at every tray, but with 1,000 trays that is 1,000 looks every time. Here is a better idea: when a tray goes on, stick a note on it that says the smallest number at or below that tray, counting the tray itself. In Python the tray and its note travel together as a pair written (4, 4), called a tuple: two values in round brackets. pair[0] is the first value, pair[1] is the second, and a, b = pair splits the pair into two names. When we push val, the note is val itself if the pile is empty. Otherwise it is min(val, note on the top tray), where min gives the smaller of two numbers. Push 4, 6, 2, 5 and the pile is [(4, 4), (6, 4), (2, 2), (5, 2)]. The smallest is always the note on the top tray: pile[-1][1] means take the top pair, then its second value.

The intuition

The top tray's note is right because it was worked out from the note below it, and that one from the note below it, all the way down. When a tray leaves, its note leaves with it, and the new top tray still carries the correct answer for the trays that remain. We never search: the answer was written down when the tray arrived. It is a trade. We use a little extra memory, one note per tray, and in return every question costs one step. The same trick works for any fact about "everything at or below this tray".

A real-world analogy

A pile of trays where each tray has a sticker saying "cheapest price in the pile so far". When a new tray goes on, you read only the sticker on the tray below, compare it with the new tray's price, and write the smaller of the two on the new sticker. To learn the cheapest price in the whole pile, you read the top sticker. Taking a tray off takes its sticker with it, and the sticker underneath is already correct.

pile = []                                  # each tray is a pair (value, lowest so far)
def push(val):
    low = val                              # on an empty pile, val is the lowest
    if pile:
        low = min(val, pile[-1][1])        # pile[-1] is the top pair, [1] is its note
    pile.append((val, low))                # tray and note go on together
for v in [4, 6, 2, 5]:
    push(v)
print(pile)                                # [(4, 4), (6, 4), (2, 2), (5, 2)]
print(pile[-1][1])                         # 2, the lowest, read in one step
pile.pop()                                 # the 5 leaves with its note
pile.pop()                                 # the 2 leaves with its note
print(pile[-1][1])                         # 4

The Monotonic Stack: Waiting for Something Bigger

Here are seven days of temperatures: [30, 28, 35, 32, 29, 33, 40]. For each day we want to know how many days we must wait for a strictly warmer day, or 0 if none comes. Checking every later day for every day is slow. Instead we walk through the days once and keep a stack of the days still waiting for a warmer one. We store their indexes, the day numbers 0 to 6, because the answer is a distance in days. When today arrives, look at the newest waiting day, stack[-1]. While today is warmer than it, that day's wait is over: pop it and record today minus that day. Then push today. The temperatures of the waiting days always fall from bottom to top, and a stack that only moves in one direction is called monotonic. while repeats as long as its test is true, and "and" needs both sides true, so "stack and temps[i] > temps[stack[-1]]" checks the pile is not empty first. wait = [0] * 7 makes seven zeros. A dict can be filled too: warmer[32] = 33 stores 33 under the label 32, and warmer.get(32, -1) reads it, giving -1 for a missing label.

The intuition

Why is this fast? Every day is pushed once and popped at most once. With 7 days that is at most 7 pushes and 7 pops, even though a while loop sits inside the for loop. So the whole job takes about n steps for n days, O(n). Checking every later day for every day would take about n x n looks: 21 pairs for 7 days, and nearly 5 billion pairs for 100,000 days. Notice also that one arrival can settle several days at once: the 35 on day 2 finished both day 1 and day 0.

A real-world analogy

A pile of sticky notes on a desk. Each note shows a day number and its temperature, and it waits for a warmer day. When a new reading arrives, you look at the note on top. If the new reading is warmer, you peel that note off, write down how long it waited, and look at the next note. Once the top note is warmer than the newcomer, you stop and stick the newcomer on top. Notes still on the desk at the end are the days that never got a warmer day.

temps = [30, 28, 35, 32, 29, 33, 40]
wait = [0] * len(temps)                  # 0 means no warmer day yet
warmer = {}                              # temperature -> the next warmer temperature
stack = []                               # days still waiting, kept as indexes
for i in range(len(temps)):              # i is today
    while stack and temps[i] > temps[stack[-1]]:   # today beats the newest waiting day
        j = stack.pop()                  # that day stops waiting
        wait[j] = i - j                  # days between them
        warmer[temps[j]] = temps[i]      # and we learn its next warmer value
    stack.append(i)                      # today starts waiting
print(wait)                              # [2, 1, 4, 2, 1, 1, 0]
print(warmer.get(32, -1), warmer.get(40, -1))   # 33 -1

Waiting Bars: Pairs of Start and Height

A histogram is a row of bars, each 1 wide, with heights such as [3, 5, 6, 1, 4]. We want the biggest rectangle that fits inside the bars. A rectangle covers some bars in a row and is only as tall as the shortest bar it covers. Its area is height times width, where the width is the number of bars covered. Bars 1 and 2 (heights 5 and 6) give height 5, width 2, area 10. The best rectangle that is as tall as one bar stretches left and right until it meets a shorter bar. We call that shorter bar a wall. So a bar waits until a shorter bar arrives on its right, and we use a stack of waiting bars again. Each entry is a pair (start, height), where start is the first position that bar's rectangle reaches back to. When a shorter bar arrives at position i, it is the right wall of every taller bar on the stack: pop each one, and its area is height x (i - start). The newcomer can reach back as far as the last bar it popped, so it takes over that start. An equal bar does not pop anything.

The intuition

Why must an entry remember a start and not just its own position? Take the bar of height 1 at position 3. The bars before it are taller, so a rectangle of height 1 can reach back over all of them, to position 0. When it is finally popped, its width must be counted from 0, not from 3. That is why the newcomer inherits the start of the last bar it popped. Why a pretend bar of height 0 at the end? After the last bar some bars are still waiting with no wall on their right. A bar of height 0 is shorter than everything, so it is a wall for all of them and the same rule finishes them. Each bar is pushed once and popped once: O(n).

A real-world analogy

A row of books standing on a shelf, each a different height. You want to slide in the biggest flat board in front of some books that stand side by side. The board can be no taller than the shortest book it covers, or it would stick out above that book. A book keeps waiting for a shorter book to its right, because that shorter book is where its board has to stop. When the shorter book arrives, every taller book waiting before it gets its final board size.

def largest(heights):
    stack, best = [], 0                  # stack holds pairs (start, height); best starts at 0
    for i, h in enumerate(heights + [0]):    # i = position, h = height; the extra 0 is a pretend bar
        start = i                        # a new bar reaches back at least to itself
        while stack and stack[-1][1] > h:    # the top bar is taller than the newcomer
            s, tall = stack.pop()        # the newcomer is its right wall
            best = max(best, tall * (i - s))     # height times width
            start = s                    # the newcomer reaches back as far as it did
        stack.append((start, h))
    return best
print(largest([3, 5, 6, 1, 4]))          # 10

Evaluating Postfix with a Stack

We normally write an operator between its numbers: 20 - 6. In postfix notation the operator comes after them: 20 6 -. As a list of tokens, pieces of text, the expression is ["20", "6", "-", "4", "/", "2", "+"]. It means: 20 6 - gives 14, then 14 4 / gives 3, then 3 2 + gives 5. There are no brackets and no rules about which operator goes first, because the order is already in the tokens. A stack evaluates it in one pass. Read the tokens left to right. A number is pushed. An operator needs two numbers, and the two newest unused numbers are the top of the pile, so pop twice, apply the operator, and push the result back. The first number popped is the right-hand one, b, and the second is the left-hand one, a, so subtraction is a - b. int("20") turns the text 20 into a number. At the end exactly one number is left: the answer. For division, 14 / 4 is 3.5 and int(3.5) chops it to 3. Python's a // b rounds down instead, which differs for negatives: int(-7 / 2) is -3 but -7 // 2 is -4.

The intuition

Why does a stack fit? Look at the moment an operator shows up. The numbers it needs are the two most recent results that have not been used yet, and "most recent unused" is the top of a stack. Using them replaces two items with one result, which is again the newest unused thing, so it goes back on top. Every token is handled once, so n tokens cost about n steps, O(n). The order of the two pops matters: the newest number is the right side, so for 20 6 - the newest, 6, is on the right and the answer is 20 - 6, not 6 - 20.

A real-world analogy

A person at a desk with a pile of paper slips, each slip showing a number. Every operator is an instruction that says "combine the top two slips". You take the top two slips, work out the answer, write it on a fresh slip and put it back on top. The slips are the numbers on the stack, the instruction is the operator token, and the single slip left at the end is the answer.

def eval_postfix(tokens):
    stack = []
    for token in tokens:
        if token in ("+", "-", "*", "/"):    # an operator arrived
            b = stack.pop()                  # the newest number is the RIGHT one
            a = stack.pop()                  # the one before it is the LEFT one
            if token == "+": stack.append(a + b)
            elif token == "-": stack.append(a - b)
            elif token == "*": stack.append(a * b)
            else: stack.append(int(a / b))   # divide, then chop the fraction toward zero
        else:
            stack.append(int(token))         # a number: text to number, then wait
    return stack.pop()
print(eval_postfix(["20", "6", "-", "4", "/", "2", "+"]))   # 5

Precedence: Settling Terms with a Stack

Now the expression is written the usual way, with the operator between the numbers: s = "12+3*10-9/4". Multiplication and division bind tighter than plus and minus: this is called precedence. So we read the expression as a sum of terms. A term is a number with its chain of * and /. Here the terms are 12, 3*10 and 9/4, and the minus sign belongs to the whole term 9/4. Their values are 12, 30 and -2 (9/4 is 2.25, chopped to 2, with the minus in front). The total is 12 + 30 - 2 = 40. The stack holds the finished terms, with their signs. A * or / always works on the newest term, the top of the stack, so it changes the top. A + or - starts a new term, so it pushes num or -num. We keep three things: the stack, num (the number being built) and op (the operator waiting before num, starting as +). A digit extends num: num = num * 10 + int(ch), so 1 then 2 gives 12. When an operator arrives, num is finished, so apply the waiting op to it, then op becomes the arrived operator and num restarts at 0.

The intuition

Why push the term and not add it to a total at once? Because a * or / may still follow, and it must apply to the whole term. In 12+3*10, if we added 3 into a total of 12 we would have 15, and then * 10 would give 150. The truth is 12 + 30 = 42. Pushing 3 on its own lets the * 10 turn it into 30 without disturbing the 12 below. In the same way the minus is stored with the number: -9 is pushed, and the later / 4 turns it into -2. Everything under the top is finished for good. Each character is read once, so the pass is O(n).

A real-world analogy

A shopkeeper working out a bill from a slip that reads 12 + 3 x 10 - 9 / 4. Each finished line item goes on a spike as its own receipt. When the slip says "x 10" after the 3, the shopkeeper changes only the newest receipt, the one on top of the spike. The lines under it are settled and never touched again. Only at the very end are all the receipts on the spike added up to give the total. The spike is the stack and each receipt is a term.

def calc(s):
    stack, num, op = [], 0, '+'          # finished terms, number being built, operator waiting
    for ch in s + '+':                   # the extra + settles the last number
        if ch.isdigit():
            num = num * 10 + int(ch)     # 1 then 12: add the digit on the right
        elif ch != ' ':                  # an operator (or the end mark) arrived
            if op == '+': stack.append(num)
            elif op == '-': stack.append(-num)
            elif op == '*': stack.append(stack.pop() * num)
            else: stack.append(int(stack.pop() / num))
            op, num = ch, 0              # remember the new operator, restart the number
    return sum(stack)
print(calc("12+3*10-9/4"))               # 40

All DSA learning paths