Python Stack and Queue, Two Ways to Line Up Data

Press Ctrl+Z and the last thing you typed goes away first. Press it again and the change before that goes away. Your editor doesn't undo in a random order. It undoes the most recent change first, then works backward. That's a stack, and you already know how it feels to use one.

A stack and a queue are two simple ways to hold a group of items and decide which one comes out next. A stack takes the newest item first. A queue takes the oldest item first. That one difference is the whole idea. This lesson shows you how to build both in Python, which tool to use for each, and why the obvious choice for a queue is the slow one.

What a stack is

A stack holds items in a pile. You add to the top, and you take from the top. Think of a pile of plates. You put a clean plate on top, and when you need one, you take the top plate. The last plate you added is the first one you take back.

That rule has a name: LIFO, which stands for last in, first out. The last item you put in is the first item you get out. There's no way to grab a plate from the middle without lifting the ones above it first.

Adding an item to a stack is called a push. Taking the top item off is called a pop. Two words, one end. Everything happens at the top.

What a queue is

A queue holds items in a line. New items join at the back, and you take items from the front. It works like a line of people at a ticket counter. The person who got there first is served first, and new people join at the end.

This rule is called FIFO, which stands for first in, first out. The item that has waited longest comes out next. A queue is fair in the way a stack is not. Nobody who joined earlier gets stuck behind someone who joined later.

So the two structures differ in one place: the end you take from. A stack takes from the same end it added to. A queue takes from the opposite end.

Where you meet them in real software

You use both of these every day without noticing. Here are the common ones.

• Undo history is a stack. Each edit gets pushed on top, and undo pops the most recent one first.
• The browser back button is a stack. Each page you visit is pushed on, and back pops the last page you were on.
• A print queue is a queue. The first document you send prints first, and later jobs wait their turn.
• Task queues in web apps are queues. Jobs like sending an email are handled in the order they arrive.

When the newest item should be handled first, you want a stack. When the oldest item should be handled first, you want a queue.

Building a stack with a plain list

Python doesn't have a separate stack type, and it doesn't need one. A plain list already does everything a stack needs. You push with append(), and you pop with pop(). Both work on the end of the list, which is exactly what a stack wants.

stack = []

stack.append("page1")
stack.append("page2")
stack.append("page3")
print(stack)
# Output: ['page1', 'page2', 'page3']

The last item you appended sits at the end. To look at the top item without removing it, read the last position with [-1]. This is called a peek:

print(stack[-1])
# Output: page3

To take the top item off, call pop() with no argument. It removes the last item and gives it back to you:

top = stack.pop()
print(top)
print(stack)
# Output:
# page3
# ['page1', 'page2']

To check whether the stack is empty, you can test the list itself. An empty list is falsy, so not stack is True when there's nothing left:

stack = ["a"]
stack.pop()
print(not stack)
# Output: True

What happens when you pop an empty stack

If you call pop() on an empty list, Python stops with an error. There's nothing to remove, so it raises an IndexError:

empty = []
empty.pop()
# IndexError: pop from empty list

This is why the empty check above matters. Before you pop, make sure something is there. A common pattern is to loop while the stack has items and stop when it's empty:

stack = ["x", "y", "z"]
while stack:
    print(stack.pop())
# Output:
# z
# y
# x

The loop runs as long as stack is truthy. Once the last item is popped, the list is empty, the condition becomes false, and the loop ends before it can raise the error.

Why a list is the wrong tool for a queue

A list works well as a stack because both ends of the action are the same: append and pop both touch the end. A queue is different. You add at the back and take from the front, and a list is slow at the front.

To take from the front of a list, you'd write pop(0). It works, but look at what Python has to do. When you remove the first item, every remaining item has to shift one place to the left to fill the gap. Position 1 moves to 0, position 2 moves to 1, and so on down the whole list.

line = ["Ann", "Ben", "Cara"]
first = line.pop(0)
print(first)
print(line)
# Output:
# Ann
# ['Ben', 'Cara']

With three items you won't notice. With a hundred thousand items, that shift happens on every single pop(0), and the program slows down a lot. Using pop(0) on a big list is slow because Python moves every other item each time. Python has a tool built for exactly this, so use that instead.

The right tool for a queue is deque

The fix lives in the standard library. collections.deque is a list-like container built to be fast at both ends. The name is short for "double-ended queue" and it's said like "deck". You import it first:

from collections import deque

queue = deque()
queue.append("Ann")
queue.append("Ben")
queue.append("Cara")
print(queue)
# Output: deque(['Ann', 'Ben', 'Cara'])

Notice how a deque prints. It shows the word deque wrapped around the list, so you always know what type you're looking at. To add to the back you use append(), the same as a list. To take from the front you use popleft(), which removes the first item and stays fast no matter how big the deque gets:

first = queue.popleft()
print(first)
print(queue)
# Output:
# Ann
# deque(['Ben', 'Cara'])

A deque works from both ends, so it also gives you appendleft() to add at the front and pop() to take from the back:

from collections import deque

d = deque(["Ben", "Cara"])
d.appendleft("Zoe")
print(d)
# Output: deque(['Zoe', 'Ben', 'Cara'])

last = d.pop()
print(last)
print(d)
# Output:
# Cara
# deque(['Zoe', 'Ben'])

To peek at the front of the queue without removing anyone, read q[0], the same way you read the first item of a list:

from collections import deque

q = deque(["Ann", "Ben"])
print(q[0])
# Output: Ann

For a queue, use a deque with append() and popleft(). It reads almost the same as a list but stays fast on large data.

Keeping only the most recent items with maxlen

A deque can be given a size limit when you create it. Pass maxlen and it will never grow past that number. When it's full and you add one more, the item at the other end drops off automatically. This is handy for a "last N items" list, like recent searches or the last few moves in a game:

from collections import deque

recent = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    recent.append(x)

print(recent)
# Output: deque([3, 4, 5], maxlen=3)

Five items went in, but only the last three stayed. Adding 4 pushed out 1, and adding 5 pushed out 2. The deque prints its limit too, so you can see the maxlen=3 in the output.

The queue module is a different thing

Python also has a module named queue, and it's easy to mix up with the idea of a queue. The queue module is for programs that run several threads at once and need to hand work between them safely. You don't need it yet, and for a normal single-threaded program a deque is the simpler and faster choice.

Two short worked examples

Both structures come together in tiny programs like these. The first reverses a word with a stack. The second serves customers with a queue.

Reversing a word with a stack

A stack flips the order of whatever you put in, because the last thing pushed is the first thing popped. That makes it a neat way to reverse a word. Push each letter, then pop them all back out:

word = "python"

stack = []
for ch in word:
    stack.append(ch)

reversed_word = ""
while stack:
    reversed_word += stack.pop()

print(reversed_word)
# Output: nohtyp

The letters go in as p, y, t, h, o, n. They come out as n, o, h, t, y, p, because pop always takes the newest one. If you're building the letters up into a new string like this, a quick reminder on how string slicing handles reversal is worth a look too, since word[::-1] does the same job in one line for plain text.

Serving customers with a deque queue

Here's the queue side, a small program that serves people in the order they arrived. Each person joins the back with append(), and you serve from the front with popleft() until nobody is left:

from collections import deque

queue = deque()
queue.append("Ann")
queue.append("Ben")
queue.append("Cara")

while queue:
    person = queue.popleft()
    print("Serving", person)

print("Done, queue is", queue)
# Output:
# Serving Ann
# Serving Ben
# Serving Cara
# Done, queue is deque([])

Ann arrived first, so Ann is served first. An empty deque prints as deque([]), which is how you can tell the line is clear.

Stack versus queue at a glance

Here's the whole comparison in one place. The boolean test not container checks empty for both.

Question	Stack	Queue
Which item comes out first	Newest (LIFO)	Oldest (FIFO)
Everyday example	Undo, back button	Print jobs, ticket line
Best Python tool	list	collections.deque
Add an item	append()	append()
Remove an item	pop()	popleft()
Peek at next out	stack[-1]	q[0]

Practice exercises

Try each one before you open the solution. Everything you need is above.

Build an undo stack

Push three edits onto a stack, then undo the last one and print what's left.

# Solution
history = []
history.append("typed hello")
history.append("bold hello")
history.append("added a comma")

undone = history.pop()
print("Undid:", undone)
print("Remaining:", history)
# Output:
# Undid: added a comma
# Remaining: ['typed hello', 'bold hello']

Reverse a word with a stack

Use a stack to reverse the word "stack".

# Solution
word = "stack"
stack = []
for ch in word:
    stack.append(ch)

result = ""
while stack:
    result += stack.pop()

print(result)
# Output: kcats

Serve a queue in order

Add three names to a deque and serve them from the front until it's empty.

# Solution
from collections import deque

queue = deque(["Sam", "Priya", "Leo"])
while queue:
    print("Now serving", queue.popleft())
# Output:
# Now serving Sam
# Now serving Priya
# Now serving Leo

Keep the last three scores

Use a deque with a size limit so only the three most recent scores are kept.

# Solution
from collections import deque

scores = deque(maxlen=3)
for s in [10, 20, 30, 40]:
    scores.append(s)

print(scores)
# Output: deque([20, 30, 40], maxlen=3)

Common mistakes

• Using pop(0) to build a queue. It works but gets slow on big lists because every other item shifts one place. Use a deque and popleft() instead.
• Popping an empty stack. [].pop() raises IndexError: pop from empty list. Check with while stack: or if stack: before you pop.
• Forgetting the import. Using deque without from collections import deque raises NameError. The import goes at the top of the file.
• Using insert(0, ...) to add to a queue. Like pop(0), this shifts every item and is slow. Use append() on a deque for the back, or appendleft() for the front.
• Mixing up which end you take from. A stack pops the newest item, a queue takes the oldest. If your output comes out in the wrong order, check whether you meant pop() or popleft().

Frequently asked questions

What is a stack in Python?

A stack is a group of items where you add and remove from the same end, the top. The last item you add is the first one you take back. In Python you build one with a plain list, using append() to add and pop() to remove.

What is a queue in Python?

A queue is a group of items where you add at the back and remove from the front, so the oldest item comes out first. The best tool for it is collections.deque, using append() to add and popleft() to remove.

What is the difference between a stack and a queue?

The order they release items. A stack is last in, first out, so the newest item comes out first. A queue is first in, first out, so the oldest item comes out first. A stack acts on one end, a queue acts on both ends.

How do I make a stack in Python?

Start with an empty list, push items with append(), take the top with pop(), and peek at the top with stack[-1]. No import is needed, since a list already does the job.

Why is deque better than a list for queues?

Taking from the front of a list with pop(0) forces every other item to shift one place, which is slow on large data. A deque removes from the front with popleft() and stays fast no matter how many items it holds.

What does LIFO mean?

LIFO stands for last in, first out. It's the rule a stack follows: the last item you put in is the first one you get out, like taking the top plate off a pile.

Is there a built-in stack type in Python?

No. Python has no separate stack class because a plain list already supports the push and pop operations a stack needs. For a queue there's collections.deque, which is the recommended tool.

When do I actually need these?

Any time order matters. Reach for a stack when the newest item should be handled first, like undo history or a browser back button. Reach for a queue when the oldest item should go first, like print jobs or a task list.

Key takeaways

• A stack is last in, first out. Build it with a list: append() to push, pop() to take the top, stack[-1] to peek.
• A queue is first in, first out. Build it with collections.deque: append() to add, popleft() to take the front, q[0] to peek.
• Don't use a list for a queue. pop(0) and insert(0, ...) shift every item and get slow on big data.
• A deque prints as deque(['a', 'b']), works from both ends with appendleft() and pop(), and can cap its size with maxlen.
• Popping an empty stack raises IndexError, so check while stack: before you pop.

Both of these are built out of the same two moves you already know from lists, append() to add and pop() to remove. If you want to see everything a list can do, from adding items to sorting them, the full rundown of Python list methods is the place to go next.