Lessons · Python · stacks and queues

Last in first out, and first in first out

A stack hands back what you put in most recently; a queue hands back what has waited longest. A Python list is already a stack; use collections.deque for a queue.

Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.

What it is for

Undo, bracket matching and the call stack itself are stacks. Breadth-first search, job queues and anything processed in fairness order are queues. Recognising which one a problem wants is often the whole solution.

How to think about it

Ask what the problem takes NEXT. The most recent thing: a stack, so append and pop(). The oldest waiting thing: a queue, so deque with append and popleft().

Worked example

from collections import deque

The queue. A list would work and would be slow at the front.

stack = []

No import needed; a list is a stack.

stack.append('a'); stack.append('b')

Push twice.

print(stack.pop())

queue = deque(['a'])

Start with one waiting.

queue.append('b')

Joins the back.

print(queue.popleft())

print(list(queue))

['b']

Your turn

Take the item that has been waiting longest.

from collections import deque
q = deque(['a', 'b'])
first = q.()

The trap

list.pop(0) looks like a queue and is not: every remaining item shifts down one, so a loop over n items quietly costs n squared.

Practise stacks and queues on HoneA question on it now, a coding challenge where there is one, and it is remembered for review. Free, no email needed.