Python stacks, queues and deque

Why it matters

Many programs care less about what is in a container than about the order in which things come back out. A browser's back button returns the page you visited most recently. A print spooler prints the job that arrived first. A calculator evaluates the operator it read most recently. Stacks and queues are the two simplest rules for the order of removal, and a third container, the deque, combines both. These three shapes appear in undo features, scheduling, parsing and nearly every graph algorithm you will meet later in this course.

This lesson shows how to use them in Python, what each operation costs, and the three interview problems that use them most: matching brackets, evaluating an expression and finding the next greater value.

The order of removal is the whole idea

Every container answers one question: when I take something out, which item comes out? A list lets you take out any item by its index, so the question does not really arise. A stack and a queue each give a single answer, and that answer is what makes them useful.

Take a pile of paper. Put one page on the pile, then another, then another. When you take pages from the same pile, you take the one you put on last. That rule is called last in, first out, shortened to LIFO.

Now stand in a line at a ticket counter. The first person in line is served first, and new people join at the back. That rule is first in, first out, shortened to FIFO.

A deque, pronounced "deck" and short for double-ended queue, lets you add and remove at both ends. It is not a third order. It is the freedom to choose the end, and a deque can behave as a stack or as a queue depending on which ends you use.

Stack: last in, first out

A stack is a container with three operations. Push adds an item on top. Pop removes the top item and returns it. Peek returns the top item without removing it. Each of these works only at the top, which is why a stack is so simple to reason about.

Python has no separate stack class. A plain list is a stack. append is push, pop() with no argument is pop, and stack[-1] is peek. The top of the stack is always the last item in the list. Here is a complete program:

The output is:

['home', 'docs', 'settings']
back to settings
now on docs
['home', 'docs', 'billing']
3

Three appends put home, then docs, then settings on the stack. The first print shows the whole list, and the top item is the last one shown. A Python list prints from the bottom up, so settings is at the end. The pop() call removes settings from the end and returns it, which is why the message says back to settings. The index [-1] then shows that docs is now the top. The new append of billing puts it at the top again, and the length is 3.

Python lists are the right stack because append and pop at the end both cost O(1). Do not use insert(0, x) and pop(0) for a stack. Those work at the front, and every item moves when you use them, so each call costs O(n).

Stacks are everywhere in computing. The call stack that tracks which function is running is a stack. The undo history in a text editor is a stack. Each step of a depth-first search is a stack, as you will see in the graph modules. Whenever a task must be finished in the reverse of the order it started, a stack is the natural tool.

Queue: first in, first out

A queue is the opposite rule. Add puts an item at the back. Remove from the front takes the item at the front and returns it. Looking at the front without removing it is peek. Think of the ticket counter. New people join at the back, and the person at the front is served next.

A plain list can be a queue, but removing from its front with pop(0) moves every other item one slot to the left, which costs O(n). Use collections.deque instead. It is a standard-library type that removes from its front in O(1). You get it with from collections import deque.

The output is:

served: Ravi
next up: Meera
serving Meera
serving Dev
serving Asha
peek on empty: None

Three people join at the back: Ravi, Meera and Dev. The first popleft serves Ravi, who is at the front. Asha joins at the back, so the line is now Meera, Dev, Asha. The index tickets[0] shows Meera as the next person. The while loop keeps serving until the deque is empty, and the people leave in the order they arrived. The last line checks for an empty deque before it reads the front. The phrase if tickets is true when the deque has at least one item, so it is the standard way to test for empty in Python.

Queues drive breadth-first search, which explores a graph one ring of neighbours at a time. They also model waiting lines in simulations, such as the list of print jobs or the list of customers.

Deque: both ends

A deque lets you add and remove at both ends. Its methods come in pairs, one for each end. appendleft, popleft and [0] work at the front. append, pop and [-1] work at the back. Each of these operations is O(1).

Here is a program that uses one deque at both ends. It also shows what happens when you take from an empty one.

The output is:

peek on empty: None
caught: pop from an empty deque
caught: deque index out of range
0 1

The first line shows the safe way to peek. The check if d returns None when the deque is empty. The pop call raises IndexError with the message pop from an empty deque. Reading d[0] on an empty deque raises IndexError too, with the message deque index out of range. The last lines add 1 to the back and 0 to the front, so d[0] is 0 and d[-1] is 1.

Two kinds of removal

Some languages have removal methods that return a special value on an empty container, and others raise an error. Python's built-in stack and queue operations take the error route. A method such as pop or popleft raises IndexError when there is nothing to remove, and indexing an empty container raises the same error.

The table below lists what happens when you take from an empty container.

If an empty container is a bug you want to find early, let the error happen. If an empty container is a normal state, such as an empty queue of waiting jobs, check it before you take an item, as in if queue:. Most loops that drain a queue use while queue:, which is why the earlier examples used it.

The most common trap is calling pop in a loop that can run on an empty stack. The bracket problem below shows the fix: check the stack before you pop.

What happens inside a deque

A deque does not store its items in one row of slots, the way a list does. CPython, the standard Python interpreter, stores a deque as a chain of small fixed-size blocks. Each block holds several items, and the blocks are linked to each other. The deque keeps track of the first and last blocks. When you add or remove at an end, only that end block changes, so the cost does not depend on how many items the deque holds. That is O(1).

This is an implementation detail. The guarantee you can rely on is the cost: adding or removing at either end is O(1), and indexing into the middle costs O(n).

Compare this with a list. A list keeps one row of references in a single array. Appending at the end is O(1) on average, because the array sometimes grows and copies all its references. Inserting or removing at the front of a list is O(n), because every item moves one slot. That is why a deque is the better choice for a queue.

Worked example: balanced brackets

The most famous stack problem in interviews asks whether a string of brackets is balanced. Every opening bracket must be closed by the same kind of bracket, and the brackets must nest properly. The string ([]{}) is balanced. The string (] is not, because the closing square bracket does not match the open round bracket. The string (( is not, because it never closes.

The stack solves this neatly. Read the string from left to right. Push every opening bracket. When you meet a closing bracket, the most recent opening bracket still on the stack must be its partner. Pop it and check that it matches. If the stack is empty when a closing bracket arrives, there is no opener to match. At the end, the stack must be empty, or some opener was never closed.

The program below reads a number t and then t strings, one per line. Save it as a file and run it. Then type this input, one line at a time:

4
([]{})
(]
((
{[()()]}

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in s:
        if c in "([{":
            stack.append(c)
        else:
            if not stack:
                return False
            if stack.pop() != pairs[c]:
                return False
    return not stack
 
 
t = int(input())
for _ in range(t):
    s = input().strip()
    print(s, "->", is_valid(s))

The output is:

([]{}) -> True
(] -> False
(( -> False
{[()()]} -> True

The dictionary pairs maps each closing bracket to the opening bracket it needs. Trace ([]{}) step by step. The ( is an opener, so it is pushed: the stack is ['(']. The [ is pushed: ['(', '[']. The ] is a closer. The stack is not empty, and the last item is [, which matches ], so it is popped. The stack is ['(']. The { is pushed: ['(', '{']. The } pops {, which matches. The ) pops (, which matches. The stack is empty at the end, so the string is valid.

Now trace ((. Both characters are openers, so the stack holds two items. The loop ends with the stack not empty, so the final check returns False. The string was never closed.

The program also shows a habit that matters. The if not stack check comes before every pop. Without it, the string ) would pop from an empty stack and raise an error. The final return not stack is just as important. Without it, (( would pass, because the loop itself would never find a mismatch.

The cost is O(n) time, because each character is pushed or popped at most once. The space is O(n) in the worst case, when the string is all openers. Interviewers often ask for the cost, so practise saying it: one pass, one stack, linear time and linear space.

Worked example: a reverse Polish calculator

A reverse Polish notation expression puts each operator after its operands. Instead of 3 + 4, you write 3 4 +. Instead of (3 + 4) * 2, you write 3 4 + 2 *. This notation needs no brackets, because the order of the tokens already says which operation comes first. Some older calculators used it, and it is a perfect stack problem.

The rule is simple. Read the tokens from left to right. A number is pushed onto the stack. An operator pops the top two numbers, applies the operator, and pushes the result. Notice the order: the first number popped is the right operand, so a - b needs b popped first.

Save the program below as a file. When it asks for input, type this line:

3 4 + 2 * 7 -

stack = []
for tok in input().split():
    match tok:
        case "+":
            b = stack.pop()
            a = stack.pop()
            stack.append(a + b)
        case "-":
            b = stack.pop()
            a = stack.pop()
            stack.append(a - b)
        case "*":
            b = stack.pop()
            a = stack.pop()
            stack.append(a * b)
        case _:
            stack.append(int(tok))
    print(tok, "->", stack)
print("result", stack.pop())

The output is:

3 -> [3]
4 -> [3, 4]
+ -> [7]
2 -> [7, 2]
* -> [14]
7 -> [14, 7]
- -> [7]
result 7

The match statement picks a branch by the value of tok, the same job as a switch. The case _ branch catches everything else and treats it as a number. int(tok) turns the text into a number, because input() always gives text. The split() call with no argument splits on any run of spaces, so you do not need to handle extra spaces yourself.

Each line shows the list after one token. The list prints from the bottom up, so the top of the stack is the last value shown. The first two tokens are numbers, so they are pushed, and the top is 4 with 3 underneath. The + pops 4 and 3, adds them, and pushes 7. The 2 is pushed, and the * pops 2 and 7 and pushes 14. The 7 is pushed on top. Then - must handle the order carefully: it pops b first, which is 7, and then a, which is 14. The result is 14 - 7, which is 7.

The - branch uses separate variables on purpose. Suppose you wrote stack.append(stack.pop() - stack.pop()) instead. Python evaluates the left operand first, so the first pop returns the top, 7, and the second returns 14. That computes 7 - 14, which is -7. The wrong sign is a classic bug, and the trace above shows where it comes from. Practice exercise 9 asks you to find it.

Worked example: the next greater value

A common interview pattern uses a stack to answer questions about the next item that is bigger than the current one. Given the numbers 4 5 2 25, the next greater value of 4 is 5, of 5 is 25, of 2 is 25, and of 25 there is none, so it gets -1.

A naive solution looks forward from each item, which is O(n squared). The stack gives O(n). The idea is to keep, on the stack, the positions of items that still need a greater value to their right. When a new value arrives, it is the next greater value for every item on the stack that is smaller than it. Those items pop off, and the new value is pushed. The stack stays in a useful order, which is why this pattern is called a monotonic stack.

The output is:

[5, 25, 25, -1, 8, -1]

The expression [-1] * len(a) makes a list with one -1 for each item, so every answer starts as -1. Trace the first four values. The stack starts empty. The value 4 at index 0 is pushed. The value 5 at index 1 is larger than the value at the top of the stack, which is 4, so index 0 is popped and its answer becomes 5. Index 1 is then pushed. The value 2 at index 2 is smaller than 5, so it is pushed. The value 25 at index 3 is larger than 2, so index 2 pops and gets 25. It is also larger than 5, so index 1 pops and gets 25. Index 3 is pushed. The stack now holds only index 3, which has no answer yet, so it keeps -1.

The stack stores indexes, not values. That lets the program both compare values through a[stack[-1]] and write the answer to result[stack.pop()]. A common beginner mistake is to push values and lose track of positions. Store the position whenever you need to write back to it.

Each index is pushed once and popped at most once, so the total time is O(n). The stack can hold up to n items, so the space is O(n).

Walking through a queue at work

Queues often model a line of waiting work. Imagine a print server where documents arrive in a fixed order and each one takes one turn to print. You can simulate the line by adding each document at the back and removing at the front. The ticket counter example already does this for people. The same pattern runs whether the items are documents, customers, packets of data or tasks in a background worker.

The queue algorithm used most in this course is breadth-first search. It starts from one node, visits its neighbours, then their neighbours, one ring at a time. The queue holds the nodes waiting to be visited. The first node added is the first one explored, which keeps the rings in order. You will write that algorithm in the graph modules, but the code uses exactly the append, popleft and if queue checks you practised here.

Debugging walkthrough: a wrong answer in the calculator

Suppose you wrote the calculator and it returns the wrong answer for 7 3 -. You expected 4, but the program printed -4. How do you find the bug?

Start with the trace. Print the stack after each token, the way the program does. After the two numbers, the list is [7, 3], with 3 at the end, which is the top. The - token must pop two values. If the code pops them in the order stack.pop() then stack.pop() inside one subtraction, the first call returns the top value, 3, and the second returns 7. That computes 3 - 7, which is -4.

The fix is to pop into named variables in a known order. The first pop is the right operand, so it goes into b, and the second pop is the left operand, so it goes into a. Then the code computes a - b, which is 7 - 3, or 4. The trace makes the reversed order visible, and the named variables make it correct.

This kind of bug is common because Python evaluates the parts of an expression from left to right. Two pop calls inside one expression run in that order, and the operands end up swapped for any operator where order matters. Subtraction and division are the operators that expose it. Addition and multiplication do not, because the order does not change the answer. That is why the bug can pass a test with + and fail on the first test with -.

Two worked traces: breadth-first order and undo

Traces make stacks and queues concrete. Here are two you will meet again.

Breadth-first order with a queue. Suppose a tree has node A at the top, with children B and C. B has children D and E. C has one child, F. Breadth-first search visits every node at depth 1, then every node at depth 2, and so on. It keeps a queue of nodes that have been discovered but not yet visited. Start with the queue holding only A.

Step 1: remove A from the front and print it. Add its children B and C at the back. The queue is B, C.

Step 2: remove B and print it. Add its children D and E. The queue is C, D, E.

Step 3: remove C and print it. Add its child F. The queue is D, E, F.

Step 4: remove D, E and F, printing each one as it leaves.

The printed order is A, B, C, D, E, F. The queue kept the nodes in the order they were discovered, so each level finished before the next one began. The queue's rule is the reason for this order. You will build this algorithm for real in the graph modules, and the operations are the same append and popleft you practised here.

Undo and redo with two stacks. A text editor needs undo and redo. Keep two stacks of edits, one for undo and one for redo. When the user makes a new edit, push it onto the undo stack and clear the redo stack. Undo pops from the undo stack, reverses that edit, and pushes it onto the redo stack. Redo pops from the redo stack, reapplies the edit, and pushes it back onto the undo stack.

Trace it. Type a, so the undo stack holds ['a'] and the text reads a. Type b, so the undo stack holds a at the bottom and b at the top, and the text reads ab. Undo pops b, so the text reads a and the redo stack holds b. Undo again pops a, so the text is empty and the redo stack holds b with a on top. Redo pops a, so the text reads a again. Now type c. The redo stack is cleared, because a new edit ends the old future, and the text reads ac.

The example uses the stack rule at every step. It also shows a rule users rely on: a new edit throws away the redo history.

The call stack is a stack too

The stack idea is inside every running Python program. When one function calls another, Python remembers where the first function was and starts the second one on top. Each call gets a frame, a small block of memory that holds its local variables. When the inner function returns, its frame is removed, and the outer function continues where it left off. That is last in, first out again.

A recursive function works the same way. Each recursive call adds a frame, and the frames come off as the calls return. Python limits how deep the stack can grow, so that a runaway recursion fails in a controlled way. The limit is about 1000 calls by default, and you can read it with sys.getrecursionlimit(). When a call goes past the limit, Python raises RecursionError:

The output is:

caught: maximum recursion depth exceeded

A traceback lists the calls from the outermost to the innermost. The last line of a traceback names the error, and the lines above it show the calls that led to it. The next example shows this order with two functions:

def inner():
    raise ValueError("boom")
 
 
def outer():
    inner()
 
 
outer()

The output is:

Traceback (most recent call last):
  File "main.py", line 9, in <module>
    outer()
    ~~~~~^^
  File "main.py", line 6, in outer
    inner()
    ~~~~~^^
  File "main.py", line 2, in inner
    raise ValueError("boom")
ValueError: boom

The path before main.py depends on where you save the file. Read the traceback from the bottom up to find the innermost call. The last frame, inner, is the one that raised the error. Knowing that the call stack is a real stack makes these traces easier to read.

Choosing between a stack and a queue

The two structures look alike, since both hold items and both have a remove operation. The difference is which item leaves first, and that decides the answer to many problems.

Take the same input, the numbers 1, 2 and 3, and then remove everything. A stack gives 3, 2, 1. A queue gives 1, 2, 3. If the problem asks for the most recent item first, such as undo, bracket matching or evaluating nested expressions, use a stack. If it asks for items in arrival order, such as fair scheduling, serving customers or breadth-first search, use a queue.

A useful test is to ask what should happen to the oldest item when a new one arrives. If the answer is "it waits its turn," the job is a queue. If the answer is "the newest one is the one that matters," the job is a stack. Interviewers often hint at the choice in their wording: "undo" points to a stack, and "in the order received" points to a queue.

There is also a middle case. A deque allows both ends, so it covers both behaviours in one structure. A sliding window of recent readings is a deque: new readings join at the back, old ones leave at the front, and a bigger reading can push smaller ones out of the back. The monotonic deque lesson later in this module builds on that idea.

Common mistakes

Calling stack methods on a list that has none. A list has append and pop, but no push. Python reports 'list' object has no attribute 'push'. Use append for push.

Using pop(0) on a list as a queue. It works, but every item moves on each call, so a long queue becomes slow. Use deque and popleft().

Popping from an empty stack. Calling pop() on an empty list raises IndexError: pop from empty list. Check the list before every pop, especially in the bracket problem, where a closing bracket can arrive first.

Forgetting the final emptiness check. A string such as (( passes the loop without any mismatch. Only the final check on the stack catches the unclosed opener.

Storing values when you need positions. In the next-greater problem, the stack must hold indexes so that you can write the answer to the right place.

Reading [-1] as removal. stack[-1] returns the top but leaves it in place. A loop that reads [-1] and expects the item to disappear runs forever.

Using None as an empty marker. A deque accepts None as a real item. If the front value is None, that does not mean the deque is empty. Check if queue: for emptiness, and read the front only after that check.

Variations and edge cases

An empty string is a valid input for the bracket problem, and it is balanced. Your code must return True without touching the stack. The loop does not run, and the final check sees an empty stack.

A single bracket such as ( or ) must be handled. The first returns False because the stack is not empty at the end. The second returns False because the stack is empty when the closer arrives.

Reversing a string is a classic first use of a stack. Push every character, then pop them all into a new string. The characters come back in reverse order. This takes O(n) time and O(n) space. In Python, text[::-1] does the same job in one step, but the stack version is the one that shows the rule.

Two stacks can build a queue, and two queues can build a stack. Interviewers ask this to test whether you understand the rules, not to get you to build a slower structure. In practice, a deque alone is the right answer.

A deque can hold a sliding window. You can keep the indexes of the useful items in a deque, dropping from the front when they leave the window and from the back when a bigger value arrives. This is the sliding-window maximum pattern, which the monotonic deque lesson later in this module covers.

Interview-style and real-world uses

Interviewers like stacks because the code is short and the reasoning is clear. Be ready for three questions. First, "Check whether brackets are balanced." The answer is the stack from this lesson, in O(n) time and O(n) space. Second, "Evaluate an expression." The answer is a stack of operands, with the careful pop order from the calculator. Third, "Find the next greater value for each item." The answer is the monotonic stack with indexes.

Interviewers also ask why you chose the structure. A good answer names the rule: "I need to match the most recent opener, so last in, first out fits." A weak answer just names the type. Practise explaining the rule first and the type second.

In real software, stacks and queues appear everywhere. Undo buttons use stacks of past actions. Schedulers use queues of waiting jobs. Parsers use stacks to track nesting in code and in data formats such as JSON. Web servers use queues to hold requests before a worker is free. When you see a problem about order of arrival or about undoing the latest change, a stack or queue is usually the first tool to try.

Practice

1. Reverse the string "course" using a list as a stack. Print the reversed string.
2. Simulate a queue of three print jobs, A, B and C, with a deque. Remove them in order and print each job as it leaves.
3. What does is_valid("{[}]") return, and at which character is the answer decided? Trace the stack after each character to find out.
4. Write a function that checks whether a string of only ( and ) characters is balanced, using a counter instead of a stack. Explain when the counter approach works and when it does not.
5. Write a function eval_rpn(tokens) that evaluates a reverse Polish expression given as a list of strings. Support +, -, * and /, where / is integer division with //.
6. Write a function that returns the first non-repeating character in a string using a queue of candidates. Explain why a queue is a good fit for the candidates.
7. Given the list [2, 1, 5, 6, 2, 3], use the monotonic stack to compute, for each index, the next greater value. Write the expected result in a list, then check it with the code from this lesson.
8. Explain, without code, how a stack can implement undo for a text editor that supports typing and deleting one character. Say what gets pushed and what gets popped.
9. A coworker wrote stack.append(stack.pop() - stack.pop()) for the calculator. Give an input where the answer is wrong, show the value the code computes, and write the correct lines.
10. Write a function has_sum(items, target) that checks whether any two items sum to the target. Sort a copy of the list first, then use two indexes, one at each end. Explain why sorting makes the indexes work, and state the time cost.

Exercise 1. Show the answer:

stack = list("course")
out = ""
while stack:
    out += stack.pop()
print(out)

The output is esruoc.

Exercise 2. Show the answer:

from collections import deque
 
jobs = deque(["A", "B", "C"])
while jobs:
    print("printing " + jobs.popleft())

Exercise 3. Show the answer: is_valid("{[}]") returns False. The { and [ are pushed, so the stack is ['{', '['] with [ on top. The } arrives. The top is [, which does not match }, so the answer is decided at the third character.

Exercise 4. Show the answer:

def balanced_parens(s):
    open_count = 0
    for c in s:
        if c == "(":
            open_count += 1
        elif open_count == 0:
            return False
        else:
            open_count -= 1
    return open_count == 0

The counter works only when every bracket is the same kind, because it cannot remember which kind it saw. With three bracket types, you need the stack, since the kind of the most recent opener matters.

Exercise 5. Show the answer:

def eval_rpn(tokens):
    stack = []
    for tok in tokens:
        if tok in ("+", "-", "*", "/"):
            b = stack.pop()
            a = stack.pop()
            if tok == "+":
                stack.append(a + b)
            elif tok == "-":
                stack.append(a - b)
            elif tok == "*":
                stack.append(a * b)
            else:
                stack.append(a // b)
        else:
            stack.append(int(tok))
    return stack.pop()

Exercise 6. Show the answer: keep a deque of characters that have not repeated yet, and a dictionary of counts. When a character repeats, mark it as used. Remove from the front until you find a candidate whose count is 1. A queue keeps the candidates in the order they first appeared, so the front is the earliest character that might still be unique.

Exercise 7. Show the answer: for [2, 1, 5, 6, 2, 3] the answer is [5, 5, 6, -1, 3, -1]. Index 0 (2) is answered by 5. Index 1 (1) is answered by 5. Index 2 (5) is answered by 6. Index 3 (6) has no greater value to its right, so -1. Index 4 (2) is answered by 3. Index 5 (3) has nothing after it, so -1.

Exercise 8. Show the answer: push each command that changes the text, along with what it changed. For typing, push the typed character. For deleting, push the deleted character and its position. Undo pops the latest command and reverses it, which restores the text before that command. The stack's last in, first out rule is exactly the order undo needs.

Exercise 9. Show the answer: for 7 3 - the code computes 3 - 7, which is -4, because the first pop returns the top, 3. The correct version pops into named variables: b = stack.pop(), then a = stack.pop(), then stack.append(a - b).

Exercise 10. Show the answer:

def has_sum(items, target):
    values = sorted(items)
    left, right = 0, len(values) - 1
    while left < right:
        total = values[left] + values[right]
        if total == target:
            return True
        if total < target:
            left += 1
        else:
            right -= 1
    return False

Sorting makes the two indexes work, because moving the left index up makes the sum bigger and moving the right index down makes it smaller. The sort costs O(n log n), and the scan costs O(n), so the total is O(n log n). A set-based version runs in O(n) on average without sorting, which the fourth lesson of this module covers.

What you now know

• A stack is last in, first out. In Python, use a list with append, pop() and [-1].
• A queue is first in, first out. Use a deque with append, popleft() and [0].
• A deque adds and removes at both ends, and every end operation is O(1).
• Taking from an empty list or deque raises IndexError. Check with if stack: or if queue: before you take an item.
• The bracket problem, the calculator and the next-greater problem each use a stack, and each runs in O(n) time.
• Pop operands in named variables when operand order matters, because a - b depends on which value you pop first.
• Check the stack before you pop, and check the final stack at the end of a bracket check.