Stacks and queues basics in Python

Why it matters

Stacks and queues are the two simplest containers where the order of removal is the whole point. Undo in a text editor, the back button in a browser, the record of which function is running right now and the line of jobs waiting for a printer all depend on one of them. Many data structure interviews include at least one question that needs a stack or a queue, and many need both.

This lesson teaches the rules, shows how each one works inside, and gives you the Python tools you will use in real code. The next three lessons use these ideas for harder problems.

Words you will need

These are the terms the lesson uses. Each one is explained again where it first matters, so you can come back here when a word slips.

• Data structure: a way of arranging values in memory so that some actions are fast. A list is a data structure. So is a dictionary.
• Operation: an action a structure supports, such as adding a value or taking one out.
• Index: the position of a value in a list. The first position is index 0, the second is index 1, and so on. A negative index counts from the end, so -1 is the last position.
• Object: a value with its own data and its own actions. Every value in Python is an object, including numbers and text.
• Class: a blueprint in Python that groups data together with the functions that work on that data.
• Method: a function that belongs to a class or to an object. You call it with a dot and parentheses, as in stack.append(5).
• List: Python's built-in ordered container. It grows and shrinks as you add and remove items. You write one with square brackets, as in [5, 8, 2].
• deque: a double-ended queue from the standard library module collections. It adds and removes items at both ends quickly. You create one with deque().
• Type hint: a note such as list[int] that says what kind of values a container holds. Python does not check type hints while the program runs. Readers and tools use them.
• Constant time, written O(1): an operation whose cost does not grow when the container gets bigger. Ten items or ten million items, the step count stays the same.

The first principle: the rule decides what comes out

Every container has a rule that decides which item you get back when you take one out. A list has no such rule. You ask for index 3 and you get the value at index 3, no matter when it was put there. A stack and a queue each have a single rule, and that rule is the reason they exist.

Think of a pile of plates in a kitchen. A clean plate goes on the top. When you need a plate, you take the top one. The plate you placed last comes off first. Computer scientists call this last in, first out, written LIFO.

Now think of a line at a ticket counter. People join at the back. The person at the front is served. The person who arrived first gets served first. Computer scientists call this first in, first out, written FIFO.

Both containers hide most of their contents. You can touch only the ends that matter. That limit is the source of their speed. When you only ever touch one end, you never have to search, shift items or walk through the middle.

The stack, precisely

A stack is a container with a top. It supports three main operations. In Python, a plain list can do all three.

Python lists have no peek method. The usual way to read the top is stack[-1]. That line raises an error on an empty list, so check the list first.

You also need a way to ask whether there is anything to take. Python treats an empty list as false inside an if, so if not stack: means "if the stack is empty". The explicit form len(stack) == 0 says the same thing and is easier for some readers.

Every one of these operations looks only at the top. Pushing one item or ten million items costs the same number of steps, so each operation is O(1). The list grows in steps, so an occasional append takes longer when the list has to make room. The average cost over many pushes still stays O(1). This is called amortized O(1), and the edge cases section returns to it.

The queue, precisely

A queue is a container with a front and a back. It supports three main operations. Python's collections.deque does all three.

The standard library also has a module named queue, with a class called Queue. That class is built for programs that run several threads, which are parts of one program running at the same time. For ordinary queues, use deque.

A plain list can also act as a queue with pop(0). It gives the right order. The cost is that every remaining item moves one place to the left on each call, so the call takes longer as the list grows. Use deque for queues.

Like the stack, every queue operation touches only one end, so each one is O(1).

Worked example 1: trace a stack on paper

Before you write any code, trace the rule by hand. Start with an empty stack and follow these steps: push 5, push 8, push 2, pop, push 9, peek, pop. Write the stack after each step, with the top on the right.

The values returned by the pops and peeks are 2, 9 and 9, in that order. Notice that the 5 went in first and is still at the bottom at the end. It leaves only after 8 has left.

Now do the same with a queue: enqueue 5, enqueue 8, enqueue 2, dequeue, enqueue 9, peek, dequeue. The queue after step 3 is [5, 8, 2] with 5 at the front. The values returned are 5, 8 and 8, in that order. The first dequeue returns 5, not 2. This one difference between the two rules is the whole lesson in a single example.

Working a trace on paper is the most reliable way to check your understanding. Whenever a stack or queue program gives an odd answer, write the state after each step on paper and compare.

Building a stack from a fixed-size list

A Python list grows on its own, so in real code you would use a plain list for a stack. Building one with a fixed size shows the index idea in its simplest form. The list holds the values. A separate number, which this lesson calls top, says how many slots are in use. The item at index top - 1 is the newest, and index top is the next free slot.

Here is a complete class with a small test at the bottom. Click Run to see the output.

3
2
False

The word class starts the blueprint. The line s = ArrayStack(5) builds one object from it and asks for room for five values. Python runs the method named __init__ on the new object. That method is the constructor. It creates self.data, a list of five slots, and sets self.top to 0.

The first parameter of every method is self. It is the object the method was called on. Python passes it for you, so you call s.push(1) and write self.data inside the class. The two underscores on each side of __init__ mark it as a special method that Python calls for you.

The expression [None] * capacity makes a list with capacity copies of None. None is Python's word for "no value", and it is the value an empty slot holds here.

Python has no ++ operator. Writing top++ is a syntax error, so the code uses self.top += 1 on its own line. The pop method works the other way round. It first moves top down, then reads the slot at the new top. The value comes back, and that slot is free again.

The raise line starts an exception. An exception is Python's way of stopping the current task and reporting an error. The text in brackets is the message you chose.

Read the output against the trace from the last section. The first pop removes 3 because 3 was pushed last. Then peek shows 2, which is now the top. The stack still holds 1 and 2, so is_empty returns False. Python writes the two boolean values as True and False, with capital letters.

What happens in memory

When [None] * 5 runs, Python creates a list with five slots. Each slot holds a reference to an object. A reference is a stored address that tells Python where a value lives. You do not see the addresses, but the rule is the same as for any array: each slot holds one value.

The value of top is a separate small number stored on the object. It is not part of the list. This is why the list can have room that is not in use. After the three pushes, the list holds [1, 2, 3, None, None], and top is 3. Slots 3 and 4 are free.

Here is the important detail about pop. It does not erase the old value. After pop returns 3, the list still holds [1, 2, 3, None, None], and top is 2. The 3 sits in slot 2 until another push writes over it. Your code must never read a slot at or above top, because the stack's rule says only the slots below top count.

Step through the animation above. Watch how top moves with each push and pop, and notice that a popped value stays visible in the list until it is overwritten.

What happens when the stack is full

Suppose you push a sixth value into the five-slot stack. The check self.top == len(self.data) becomes true, so the method raises an exception. Here is a program that pushes six values in a loop. The loop prints each value after it is pushed, so you can see where the error happens.

pushed 1
pushed 2
pushed 3
pushed 4
pushed 5
Traceback (most recent call last):
  File ".../l1_array_full.py", line 15, in <module>
    s.push(value)
    ~~~~~~^^^^^^^
  File ".../l1_array_full.py", line 8, in push
    raise IndexError("stack full")
IndexError: stack full

The folder part of each file path is shown as .... Your paths will show the folder where you saved the file.

Python prints a traceback, which lists each call that led to the error, from the outermost call down to the line that raised it. The last line is the exception name and its message. Read the last line first, because it says what went wrong. Then look at the line above it to find the code that failed.

A fixed-size stack is simple, but it has a limit. Python's list has no such limit, so the next section uses the built-in types.

Python's own tools: list and deque

A Python list already works as a stack. append adds at the end, and pop removes from the end. Both are O(1) on average. You do not need to write a class to use one.

For a queue, use collections.deque. The name is usually said "deck". It has append to add at the right end, popleft to remove from the left end, and appendleft to add at the left end. Its pop removes from the right end, so the same object can serve as a stack or as a queue.

The stack top is at the right end in Python. The natural stack uses append and pop, which both work at the right end. Both lists and deques print with the newest item on the right.

Here is the same stack and queue work done with a deque. The printed text shows the whole collection, which lets you see the order inside it.

stack: deque(['a', 'b', 'c'])
pop: c
after pop: deque(['a', 'b'])
queue: deque(['a', 'b', 'c'])
popleft: a
after popleft: deque(['b', 'c'])

The first line of code imports deque from the standard library module collections. An import line makes names from another module available in your program.

Printing a deque shows the word deque followed by the items in a list. The items run from left to right. For the stack, the top is c, which is the rightmost item. For the queue, the front is a, which is the leftmost item and the oldest one. Both lines match the FIFO and LIFO rules.

Notice that both uses create the same kind of object. The choice between stack and queue comes from the methods you call, not from the object. You must keep the method pattern consistent in each use. If you mix append with popleft on a stack, the order becomes hard to predict.

Choosing a container

Use a list when you need a stack, or when you need to read or change items by position. Use a deque when you need a queue or when items are added and removed at both ends. Use a dictionary or a set when you need to look items up by key or check membership quickly. This module is mostly about the first two. Later modules cover the others.

The question to ask is always about the order of removal. If you cannot name the order you need, you have not yet understood the problem.

Worked example 2: a command runner

Stacks are easiest to understand when you watch them respond to commands. The program below reads commands from the Input box. The first line says how many commands follow. Each command is a word, optionally followed by a number. The program keeps a stack and prints the result of each command.

Type this into the Input box, one line at a time, and then click Run.

7
push 4
push 9
peek
pop
pop
pop
size

9
9
4
empty
0

Start with the input. input() reads one whole line and returns it as text, without the line break at the end. int(...) turns the text 7 into the number 7. The loop runs n times, once for each command line.

The line input().split() cuts a line such as push 4 into the list ["push", "4"]. Python's split with no argument cuts at any run of spaces, so an extra space does no harm. Then parts[0] is the command word and parts[1] is the number that follows it.

The match statement picks one branch by the command word. It is Python's version of a switch. Each case line is one branch, and only the matching branch runs. The last branch, case _, matches anything else. match needs Python 3.10 or newer.

The pop and peek branches use a small rule that beginners often miss. Popping an empty stack raises an exception, so the program checks the stack first. The expression stack.pop() if stack else "empty" has the form X if condition else Y. It gives X when the condition is true and Y when it is false. An empty deque counts as false, so if stack means "if the stack has items".

Trace the output. push 4 and push 9 fill the stack to [4, 9] with 9 on the right. peek prints 9 and leaves the stack alone. The first pop prints 9 and leaves [4]. The second pop prints 4 and leaves nothing. The third pop finds the stack empty and prints empty. The last command, size, prints 0.

The queue in Python

A queue follows the same pattern, with append and popleft in place of append and pop. The next program simulates a printer. Jobs join the queue in the order they are sent. The printer serves them one at a time, oldest first.

This version reads one job per line. Python's input() reads a whole line, so one name per line keeps the code short.

Type this into the Input box:

3
report
resume
photo

1: printing report
2: printing resume
3: printing photo
queue empty: True

The f before the text makes an f-string. Anything inside braces in an f-string is replaced by its value. So {step} becomes the current number, and {printer.popleft()} becomes the job name that was removed from the front.

The while printer: loop runs as long as the deque has something in it. Each popleft removes the front item, so the jobs print in arrival order. The last line checks that the queue is empty. not printer is true when the deque has no items, so the output says True.

Notice what the program does not do. It never looks inside the queue to find a job. It only takes the front. A queue is a line where only the front is served, and this program follows that rule exactly.

Step through the queue above. Watch the front stay fixed while new items join at the back, and notice that each dequeue shows the oldest item first.

Empty containers: exceptions, not None

What should a container do when you ask for an item and it has none? Python never returns a special empty value from these operations. Each one raises an exception. This choice trips up many learners, so it is worth reading slowly.

The rule is this. Python containers do not have a "nothing here" value of their own. Your code has to check first, with if stack: or if not queue:, or it has to catch the exception.

None is an ordinary value in Python. A deque can hold None as an item, so None cannot mean "empty" by itself. The next program shows the exceptions and the one way to tell that a deque holds None.

peek on empty list: list index out of range
pop on empty list: pop from empty list
popleft on empty deque: pop from an empty deque
index 0 on empty deque: deque index out of range
deque with None: deque([None])

The try block holds the code that might fail. If an operation raises an exception, Python jumps to the matching except block and skips the rest of the try. The name e holds the exception object, and print(e) shows its message.

If you leave out the try and call pop on an empty list, the program stops and prints a traceback. The traceback is shown in the common mistakes section below. A real program would usually do something more useful in the except block, such as printing a message for the user or returning a safe value.

Worked example 3: reverse a string with a stack

A stack reverses order, because the last value pushed is the first value popped. This makes it the natural tool for reversing anything you can read one piece at a time. Here the piece is a character.

Type this into the Input box:

stack and queue

eueuq dna kcats

The loop for ch in s visits each character in order from left to right and pushes it. Python has no separate character type. A character is a string of length 1, so ch is a string. After the loop, the stack holds the characters with the last one on the right. The second loop pops until the stack is empty. The first character to come out is the last one that went in, so the text comes out backwards.

Strings in Python cannot change in place. The code therefore collects the characters in a list called out and joins them at the end with "".join(out). The empty string before .join is the separator placed between the pieces. Adding text with += in a loop also works, but each += may build a new string, so the list and join pattern is the usual choice.

Python's slice text[::-1] also reverses a string in one step. It is shorter, but it does not show the stack rule, and the exercises ask for the stack version.

Trace the whole input. The pushes put its letters on the stack in order, so the last letter, e, is on the right. The first five pops give e, u, e, u and q, which spell eueuq, the word queue backwards. Then the pops give a space, then d, n and a, then a space, then k, c, a, t and s. Together they form eueuq dna kcats, the output.

This method is O(n) in time, because each character is pushed once and popped once. It is O(n) in space too, because the stack holds every character at the peak.

Common mistakes

These are the mistakes that beginners make most often. For each one, the message you will see and the fix are listed.

Popping an empty stack. The program below pops from an empty list without checking it first.

stack = []
stack.pop()

Traceback (most recent call last):
  File ".../l1_pop_empty.py", line 2, in <module>
    stack.pop()
    ~~~~~~~~~^^
IndexError: pop from empty list

The fix is to check the list before you pop: if stack: first, or a try block around the pop.

Calling peek on a list. Python lists have no peek method. Calling it raises an AttributeError, which means the object has no attribute with that name.

stack = [1, 2]
try:
    stack.peek()
except AttributeError as e:
    print(e)

'list' object has no attribute 'peek'

The fix is stack[-1], after you check that the list is not empty.

Taking from the wrong end of a queue. A deque can be used as a stack or a queue, so the wrong method gives a wrong answer without any error. Using pop on a queue takes the newest item, not the oldest.

from collections import deque
 
q = deque()
q.append(1)
q.append(2)
print(q.pop())

2

For a queue, the first item out must be the first item in, which is 1. The fix is popleft.

Confusing peek with pop. stack[-1] shows the top and leaves it alone. stack.pop() removes it. A loop that reads the top but never pops never ends, because the stack never shrinks. Check that each loop moves the container toward empty.

Expecting a for loop to go top first. The loop for x in stack on a deque visits the items from left to right. In Python the top is on the right, so the loop visits the bottom first.

from collections import deque
 
s = deque()
s.append("bottom")
s.append("middle")
s.append("top")
for x in s:
    print(x)

bottom
middle
top

If you need the top first, use reversed(s). It visits the items from right to left without changing the deque.

Reading past the top of a list stack. Suppose you push 1, 2 and 3 into the fixed-size stack, and then read data[top] by mistake. The slot is free, so the value is None. Python does not crash, which makes this bug quiet and hard to find. The top item is always at top - 1.

data = [1, 2, 3, None, None]
top = 3
print("data[top] =", data[top])

data[top] = None

A free slot holds None, so it is easy to spot when it is printed.

Forgetting the parentheses. deque on its own is the class. deque() creates an object from it. Writing d = deque and then calling a method on d gives a confusing message.

from collections import deque
 
d = deque
try:
    d.append(1)
except TypeError as e:
    print(e)

descriptor 'append' for 'collections.deque' objects doesn't apply to a 'int' object

The message does not say "missing parentheses", so check the line that created the object first.

Debugging walkthrough

Suppose the stack returns a value you did not expect. The class is short, so you might be tempted to stare at it. A faster approach is to print the internal state after each step. For a list stack, that means the list and the value of top.

The next program adds a show method to the class. It is a short version of the class, with the check lines left out so the example stays small.

after pushes: [1, 2, 3, None, None] top = 3
after pop: [1, 2, 3, None, None] top = 2

Reading this output tells you three things in one look. The three pushed values are where they should be. The None values in slots 3 and 4 are unused. After the pop, top moved down to 2, while the old 3 stayed in the list, which is correct behaviour. If the printed top after a pop were still 3, you would know the bug is in pop. If data[top] held a real value after a pop that should have cleared it, you would know the old value was being read. Printing the state turns a guess into an observation.

The same idea works with a deque. Print the whole deque after each operation. Its printed form lists the items from left to right, so the top of a stack is on the right.

Variations and edge cases

Interviewers like to test what happens at the edges. Here are the edge cases you should check whenever you write stack or queue code.

Empty input. A stack or queue with no items should answer len(stack) == 0 with True, and reading its top or front should raise an error that your code handles. Test this first.

Capacity zero. A fixed-size stack created with ArrayStack(0) is full from the start. Its first push raises IndexError: stack full. A list or deque has no such limit.

One item. After one push, reading the top and popping should show the same item. After one pop, the stack is empty again. Many bugs show up only when the size goes from 1 to 0.

Equal values. Pushing 7, 7, 7 gives a stack of three equal values. pop removes one 7 at a time. Stacks and queues do not care whether values repeat, so they are useful when you need a count of items as well as their order.

Threads. The Python documentation says that appends and pops at either end of a deque are thread-safe. For a queue that several threads share, and that a thread should wait on until an item arrives, use queue.Queue. It adds the waiting and the locking for you.

Large numbers of items. A list grows by copying its contents into a bigger block now and then. A single append that triggers a copy is slow, but averaged over many appends the cost per item stays O(1). Computer scientists call this amortized O(1). The next lesson uses the same idea.

Interview view: what the question is really asking

Interviewers rarely ask "implement a stack" alone. More often, a question needs a stack as a tool. The way to spot that need is to look for a rule that says "the most recent unfinished thing comes first". Brackets that must close in reverse order fit that rule. Undo fits it. Matching the nearest previous opening item fits it.

For a queue, look for a rule that says "the first one who arrived goes first". A list of tasks that must be done in order, or a search that visits nodes in rings around a start point, fit that rule.

When you explain your choice aloud, name the rule first and the structure second. For example: "Each new bracket has to be closed before the older ones, so the most recent open bracket is the one to check. That is a stack." Interviewers listen for this reasoning more than for the code.

Expect two follow-up questions. The first is the cost of each operation. Answer O(1) for append and pop on a list, and for append and popleft on a deque, and mention that growth makes append amortized O(1). The second is what you would do if the input were too large to fit in memory. The answer depends on the problem, but a stack or queue of only the needed items is usually the first thing to try.

Real-world uses

Undo and redo. An editor pushes each action onto an undo stack. Pressing undo pops the most recent action and reverses it. Redo uses a second stack. Pushing a new action clears the redo stack, which is why redo stops working after you type something new.

The call stack. When one function calls another, Python records the call: where to return, and the values of the local variables. When the called function finishes, Python removes that record and returns to the caller. A recursive function is a pile of these records. A recursion that never stops fills the stack, and Python raises a RecursionError.

The next program shows the error. It calls a function that calls itself forever.

import sys
 
 
def count_down(n):
    return count_down(n + 1)
 
 
print("limit:", sys.getrecursionlimit())
count_down(0)

limit: 1000
Traceback (most recent call last):
  ...
RecursionError: maximum recursion depth exceeded

The traceback lines in the middle are omitted here. They repeat the same call many times. Python stops the recursion at the limit printed on the first line, which is 1000 on Python 3.14. The number of repeated lines in the traceback depends on the Python version and the machine.

Browser history. Each page you visit goes on a back stack. The back button pops the last page and shows it. Going forward uses another stack.

Printers and job queues. A printer serves jobs in arrival order, so it uses a queue. So does a web server that handles requests as they come in, and a chat app that delivers messages in order.

Breadth-first search. Searching a map or a graph level by level uses a queue. The next lesson on queues shows how.

Complexity summary

Your own ArrayStack has the same O(1) costs for push, pop and peek, because it never searches. It has no growth, so a push on a full stack raises an error instead of becoming slower.

Practice

Try each exercise before you open its answer. Use paper for the traces. Each answer lists the output, so you can check your work.

1. Add a size() method to ArrayStack that returns how many values are on the stack.

Show the answer

Add this method to the class:

def size(self):
    return self.top

top already counts the values that are in use, so size only needs to return it.

2. Push 1, 2 and 3 onto an ArrayStack, then pop twice. What does peek() return? Explain why, using the trace method.

Show the answer

peek() returns 1. The two pops remove 3 and then 2, which leaves 1 as the only value and therefore the top.

3. Write a function reverse(s) that uses a stack. It must not use slicing, such as s[::-1].

Show the answer

from collections import deque
 
 
def reverse(s):
    stack = deque()
    for ch in s:
        stack.append(ch)
    out = []
    while stack:
        out.append(stack.pop())
    return "".join(out)

This is the same function as worked example 3.

4. Add an is_full() method to ArrayStack. Then push five values into a five-slot stack and print is_full().

Show the answer

def is_full(self):
    return self.top == len(self.data)

The output of the test is True, because the five pushes filled all five slots.

5. Trace this queue by hand, then check your answer: append 4, append 7, popleft, append 9, popleft, popleft. Write down each value that popleft returns.

Show the answer

The three popleft calls return 4, 7 and 9, in that order. The deque keeps the oldest value on the left, so 4 leaves first, then 7, then 9.

6. Predict the output of this code, then check it.

from collections import deque
 
d = deque()
d.append(1)
d.appendleft(2)
d.append(3)
print(d[0], d.pop())

Show the answer

The output is 2 3. The append(1) puts 1 on the right. The appendleft(2) puts 2 on the left, so the deque reads [2, 1]. The append(3) puts 3 on the right, giving [2, 1, 3]. Then d[0] reads the left end, 2, and pop() removes and returns the right end, 3.

7. Write a function pop_or_default(stack) that returns the top value, or -1 when the stack is empty. Do not let it raise an exception.

Show the answer

def pop_or_default(stack):
    if not stack:
        return -1
    return stack.pop()

Checking the list first means pop is never called on an empty list. The call pop_or_default([]) returns -1, and pop_or_default([5]) returns 5.

8. Show that a deque can store None, and that pop on an empty deque raises an exception. Write the code and state the exception.

Show the answer

from collections import deque
 
d = deque()
d.append(None)
print(d, len(d))
try:
    deque().pop()
except IndexError as err:
    print("IndexError:", err)

The output is deque([None]) 1, then IndexError: pop from an empty deque. Python lets a deque hold None, so None cannot be used to mean "empty" here.

9. Read a line of words, split it at spaces, push each word onto a stack, then print the words in reverse order on one line. For the input one two three, the output is three two one.

Show the answer

from collections import deque
 
stack = deque()
for w in input().split():
    stack.append(w)
out = []
while stack:
    out.append(stack.pop())
print(" ".join(out))

The output for the input one two three is three two one.

10. Add a __str__ method to ArrayStack that returns the values from the bottom to the top, in the form [1, 2, 3]. Use only the list and top.

Show the answer

def __str__(self):
    return str(self.data[:self.top])

The slice self.data[:self.top] copies the first top values, which are the ones in use. Python calls __str__ when you print the object, so print(s) shows [1, 2, 3] after three pushes.

What you now know

• A stack is last in, first out. In Python, append, pop and stack[-1] on a list do its main jobs, and each takes O(1) time.
• A queue is first in, first out. In Python, use collections.deque with append, popleft and queue[0], and each takes O(1) time.
• A list can hold a stack with an index called top. Popping moves top but leaves the old value in place until the next push.
• Python containers raise IndexError on an empty pop or read. Check if stack: before you pop, or catch the exception.
• Python has no peek method for lists. Use stack[-1] after checking that the list is not empty.
• A stack reverses order, which is why it is the natural tool for reversing text and for matching nested pairs.

The next lesson uses a stack to check that brackets are balanced, and the lesson after that uses one to find the next larger value for each item in a list.