Definition
How does the undo button know what to undo?
A stack is a collection where the last item added is the first one removed (last in, first out, LIFO). A queue is a collection where the first item added is the first removed (first in, first out, FIFO). In Python a list works well as a stack, and collections.deque works well as a queue.
In simple words
A stack is a pile of plates: you add to the top and take from the top. Undo works like that, removing your most recent action first. A queue is a line at a ticket counter: the first person to join is served first. A printer serves documents in the order they were sent.
Why it matters
Stacks and queues are the engines of many algorithms you will meet. Depth-first search in classical AI uses a stack; breadth-first search uses a queue. Browsers, editors and operating systems use both constantly.
How it works
| Stack (list) | Queue (deque) | |
|---|---|---|
| Add | stack.append(x) | queue.append(x) |
| Remove | stack.pop() # newest | queue.popleft() # oldest |
| Look without removing | stack[-1] | queue[0] |
| Order | Last in, first out | First in, first out |
In code
An undo stack for a text editor and a print queue.
from collections import deque
history = [] # a stack
for action in ["type 'Hi'", "make bold", "add image"]:
history.append(action)
print("Did:", action)
print("Undo:", history.pop())
print("Undo:", history.pop())
print("Left in history:", history)
printer = deque() # a queue
for doc in ["notes.pdf", "photo.jpg", "form.docx"]:
printer.append(doc)
while printer:
print("Printing", printer.popleft())Output
Did: type 'Hi' Did: make bold Did: add image Undo: add image Undo: make bold Left in history: ["type 'Hi'"] Printing notes.pdf Printing photo.jpg Printing form.docx
Try it yourself
Stack or queue?
Does each situation work last-in-first-out or first-in-first-out?
The browser back button
A pile of books where you take the top one
Customers waiting at a bank counter
Undo in a drawing app
Messages waiting to be sent
Common mistakes
- Using pop() when you meant the oldest item. pop() gives the newest.
- Popping from an empty stack or queue: IndexError. Check first with if stack:.
- Using a list as a long queue with pop(0), which is slow.
Check yourself
Summary
- Stack: last in, first out; list.append and list.pop.
- Queue: first in, first out; deque.append and deque.popleft.
- Search algorithms in classical AI are built on them.
Finished reading?
Sources: W3Schools DSA with Python