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.
Overview
- Stacks and queues are linear data structures that control the order in which items are added and removed.
- A stack is Last In, First Out (LIFO); a queue is First In, First Out (FIFO).
- Their basic operations are push/pop for stacks and enqueue/dequeue for queues, each in constant time.
- In Python, a list works well as a stack; collections.deque is the right choice for a queue.
- Popping from an empty stack or queue is an underflow error that programs must check for.
- Search algorithms in AI use them directly: depth-first search uses a stack, breadth-first search a queue.
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.
Key terms
- Stack
- A collection where the last item added is the first removed (LIFO).
- Queue
- A collection where the first item added is the first removed (FIFO).
- Push and pop
- Adding to and removing from the top of a stack.
- Enqueue and dequeue
- Adding to the back and removing from the front of a queue.
- deque
- collections.deque, a double-ended queue that adds and removes quickly at both ends.
- Abstract data type
- A description of how a collection behaves, independent of how it is built.
Types
Beyond the basic stack and queue, there are several variants, each changing where items enter and leave or which item leaves first.
1. Stack (LIFO)
A collection where the last item added is the first removed.
- How it works: push adds to the top and pop removes from the top; peek looks at the top without removing it; with a list, use append() and pop().
- Example: The undo button, browser back button, and checking balanced brackets in ((2 + 3) * 4).
- When to use it: Use it when the newest item must be handled first: undo, backtracking, function calls and depth-first search.
2. Queue (FIFO)
A collection where the first item added is the first removed.
- How it works: enqueue adds at the back and dequeue removes from the front; deque.append() and deque.popleft() do both in constant time (list.pop(0) is slow).
- Example: A ticket counter line, a printer queue, or customer-support chats served in order.
- When to use it: Use it when items must be handled in arrival order: scheduling, buffering and breadth-first search.
3. Deque (double-ended queue)
A sequence that allows adding and removing at both ends.
- How it works: collections.deque supports append, appendleft, pop and popleft in constant time, and maxlen keeps only the latest items.
- Example: deque(maxlen=5) holding the last five sensor readings for a moving average.
- When to use it: Use it when you need both stack and queue behaviour, or a sliding window of recent items.
4. Priority queue
A queue where the item with the highest priority (or lowest cost) leaves first, whatever its arrival time.
- How it works: Python's heapq module keeps a list arranged as a binary heap, so the smallest item is always at index 0; push and pop take O(log n).
- Example: A hospital emergency room treating the most serious patient first; the open list in A* search.
- When to use it: Use it for scheduling by urgency and for best-first, Dijkstra and A* search algorithms.
5. Circular queue (ring buffer)
A fixed-size queue stored in an array whose end wraps around to the start.
- How it works: Front and rear indexes move forward with modulo arithmetic, (i + 1) % size, so freed space at the front is reused.
- Example: Audio and network buffers that keep the most recent data in a fixed block of memory.
- When to use it: Use it when memory is fixed and data streams in continuously, as in devices and embedded systems.
Explained in detail
Two rules for order
Stacks and queues are not new Python types; they are rules about the order in which items leave a collection. A stack is like a pile of plates: you add to the top and take from the top, so the most recent plate comes off first. A queue is like the line at a railway ticket window: people join at the back and are served from the front, so the earliest arrival is served first. Choosing the right rule makes many algorithms simple, and choosing the wrong one makes them incorrect.
Where you meet them
| Structure | Real use |
|---|---|
| Stack | Undo in an editor: the last change is undone first |
| Stack | The browser back button |
| Stack | Python's call stack, which tracks function calls and recursion |
| Stack | Checking that brackets in an expression are balanced |
| Queue | A printer printing jobs in the order they were sent |
| Queue | Requests waiting for a web server or an AI model |
| Queue | Breadth-first search, which explores a maze level by level |
Building them in Python
A plain list makes an excellent stack: append() pushes to the end and pop() removes from the end, and both are fast. A list makes a poor queue, because pop(0) removes from the front and forces every remaining item to shift one place, which is slow for long lists. For queues, use collections.deque: append() adds to the back and popleft() removes from the front, both instantly. deque also supports appendleft() and pop(), so it can act as either structure.
A worked example: balanced brackets
- Read the expression one character at a time.
- When you see an opening bracket, push it onto a stack.
- When you see a closing bracket, pop the stack and check the popped bracket matches.
- If the stack is empty when you need to pop, or the brackets do not match, the expression is unbalanced.
- At the end, the expression is balanced only if the stack is empty.
Editors and compilers use exactly this algorithm to tell you a bracket is missing. In AI, queues reappear when you study search: breadth-first search uses a queue to explore the nearest options first, while depth-first search uses a stack to follow one path as far as it goes.
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