Queue / Stack

A deque (you say it like "deck") is a list you can add to and remove from at both ends in O(1) time. Here's everything you'll use in an interview:

from collections import deque

d = deque([1, 2, 3])  # create from any iterable
d.append(4)           # add to the right end, O(1)
d.appendleft(0)       # add to the left end, O(1)
right = d.pop()       # remove from the right end, O(1)
left = d.popleft()    # remove from the left end, O(1)
front = d[0]          # peek at the left end, O(1)
back = d[-1]          # peek at the right end, O(1)
size = len(d)         # count the items, O(1)

print(left, right, front, back, size, d)
main.py

You can use this one class as a queue or as a stack. The rest of this page shows how each one works. It also explains when a deque is better than a plain list.

Queue vs stack

You'll need queues and stacks for bigger topics like graph and tree traversal. The only difference between them is which end you take items from.

  • Example of a QueueQueue: First In, First Out (FIFO). A queue gives you back the oldest item first. Think of a line at a ticket counter. The first person to get in line is the first person to leave it. You'll use queues a lot in breadth-first search.
  • Example of a StackStack: Last In, First Out (LIFO). A stack gives you back the newest item first. Think of a stack of pancakes. You add new pancakes to the top. You also eat from the top. Stacks show up in problems about recursion, reversing things, and matching pairs like Valid Parenthesis.

In Python, you use the same class for both: the deque. You don't have to memorize two different classes!

deque vs list: why not just use a list?

A list is fast at its right end and slow at its left end. When you call list.pop(0), Python has to shift every other item over by one. That makes it O(n). A deque doesn’t store its items that way. Its popleft() is O(1) no matter how big the deque gets:

from collections import deque

# Pretend each number is a task waiting in line.
tasks = [1, 2, 3, 4]

as_list = list(tasks)
first = as_list.pop(0)  # O(n): every other item shifts left
print(first, as_list)

as_deque = deque(tasks)
first = as_deque.popleft()  # O(1): nothing shifts
print(first, as_deque)
main.py

This matters most in breadth-first search. BFS pops from the front of the queue once for every node it visits. With list.pop(0), each of those pops is O(n). That can turn your O(V + E) search into O(V²). Interviewers will notice this.

For a stack, a plain list is totally fine. append() and pop() both work on the right end. They’re O(1) either way. A list is also faster when you need to index into the middle. That’s O(1) on a list but O(n) on a deque.

stack = []
stack.append("a")
stack.append("b")
stack.append("c")
print(stack.pop())
print(stack[-1])
main.py

Note

Don’t mix this up with queue.Queue. That class is built for passing work between threads. It’s slower. You also don’t need it in an interview. Use collections.deque instead.

Queue

deque pop() vs popleft()

They do the same thing at opposite ends. pop() removes and returns the item on the right. popleft() removes and returns the item on the left. Both are O(1).

from collections import deque

d = deque(["a", "b", "c"])
print(d.pop())      # "c", from the right
print(d.popleft())  # "a", from the left
print(d)            # only "b" is left
main.py

Which one you pick decides what you’ve built. If you add with append() and remove with popleft(), the oldest item leaves first. That’s a queue. If you remove with pop() instead, the newest item leaves first. That’s a stack. Both raise an IndexError on an empty deque. Remember to check if d: first.

Creating a queue

To make a queue, call the deque constructor:

# Most interview editors already have this imported.
# If yours doesn't, remember that most of the fancier
# data structures live in the collections library!
from collections import deque

ticket_line = deque()
print(ticket_line)
main.py

You can also start the deque off with some values:

Create simple queue
from collections import deque

ticket_line = deque(["#1", "#2", "#3"])
print(ticket_line)
main.py

Adding an item to the queue

O(1)

In a queue, new items always go to the back of the line. You do that with append():

Append to simple queue
from collections import deque

ticket_line = deque(["#1", "#2", "#3"])
ticket_line.append("#4")
print(ticket_line)
main.py

Removing an item from the queue

O(1)

To take an item off the queue, use popleft(). Remember, people join at the back of the line and leave from the front:

Popleft from simple queue
from collections import deque

ticket_line = deque(["#1", "#2", "#3"])
ticket_line.popleft()
print(ticket_line)
main.py

Peeking at the front of the queue

O(1)

popleft() also returns the item it removed. That’s how you get the front of the queue. If you just want to look at the front without removing it, use ticket_line[0]. The back of the queue is ticket_line[-1].

from collections import deque

ticket_line = deque(["#1", "#2", "#3"])
first_element = ticket_line.popleft()
print(ticket_line)
print(first_element)
print(ticket_line[0])
print(ticket_line[-1])
main.py

Note

Indexing or popping an empty deque raises an IndexError. In a loop, remember to check while ticket_line: before you pop.

Stack

Creating a stack

You make a stack the same way you make a queue. It's the same class.

from collections import deque

pancake_stack = deque()
print(pancake_stack)
main.py

You can start a stack off with values, too:

Initialize stack
from collections import deque

pancake_stack = deque(["bottom", "middle", "top"])
print(pancake_stack)
main.py
Append to stack

Adding an item to the stack

O(1)

New items go on the "top" of the stack. We’ll treat the right end of the deque as the top. That means you add items with append():

from collections import deque

pancake_stack = deque(["bottom", "middle", "top"])
pancake_stack.append("top_top")
print(pancake_stack)
main.py

Removing an item from the stack

O(1)

To take an item off a stack, use pop(). That's the only difference in code between a stack and a queue. The problems you use them for are very different, though.

Pop from stack
from collections import deque

pancake_stack = deque(["bottom", "middle", "top"])
pancake_stack.pop()
print(pancake_stack)
main.py

Peeking at the top of the stack

O(1)

Just like with the queue, pop() returns the item it removed. To look at the top without removing it, use pancake_stack[-1].

from collections import deque

pancake_stack = deque(["bottom", "middle", "top"])
top_element = pancake_stack.pop()
print(pancake_stack)
print(top_element)
print(pancake_stack[-1])
main.py

deque(maxlen=k): You probably won’t need this in an interview. It’s still handy to know. If you pass maxlen, the deque never grows past that size. Once it’s full, each new item pushes the oldest one out the other end. That gives you a fixed-size sliding window with no extra code:

from collections import deque

window = deque(maxlen=3)
for num in [4, 8, 15, 16, 23]:
    window.append(num)
    print(list(window))
main.py