Stack and queue explained: LIFO vs FIFO with Python examples

What problem stacks and queues solve

Many programs need to remember items and process them later in a fixed order. A stack gives you the most recent item first, which matches nested work: function calls, undo history, matching brackets, and depth-first search. A queue gives you the oldest item first, which matches fair waiting: print jobs, task schedulers, message queues and breadth-first search.

Both are abstract data types: they are defined by their operations, not by how they are stored. You can build either one on top of an array or a linked list.

Operations and names

Worked example: push and pop step by step

Push 1, 2 and 3 into both structures, then remove two items.

Python implementation

A Python list is already a good stack: append and pop() work on the end of the list in O(1) amortized time. For a queue, do not use list.pop(0), because it shifts every remaining element and costs O(n). Use collections.deque, which is O(1) at both ends.

from collections import deque
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop(), stack[-1])   # 3 2
queue = deque()
queue.append("a")
queue.append("b")
queue.append("c")
print(queue.popleft(), queue[0])  # a b
print(len(stack), len(queue))     # 2 2

If you want named methods and clear errors, wrap the built-ins in a small class:

from collections import deque
class Queue:
    def __init__(self):
        self._items = deque()
    def enqueue(self, item):
        self._items.append(item)
    def dequeue(self):
        if not self._items:
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()
    def __len__(self):
        return len(self._items)
q = Queue()
q.enqueue("job1")
q.enqueue("job2")
print(q.dequeue(), len(q))  # job1 1

Classic stack problem: balanced brackets

To check that every bracket is closed in the right order, push each opening bracket. When you see a closing bracket, the top of the stack must be its matching opener.

def is_balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack
print(is_balanced("f(a[1], {b: 2})"))  # True
print(is_balanced("(]"))               # False
print(is_balanced("(("))               # False

The same idea evaluates expressions in reverse Polish notation, converts recursion into a loop, and drives depth-first search: replace the call stack with your own list.

Classic queue problem: breadth-first search

Breadth-first search visits a graph level by level. A queue makes that happen: nodes discovered first are processed first.

from collections import deque
def bfs_order(graph, start):
    seen = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return order
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(bfs_order(graph, "A"))  # ['A', 'B', 'C', 'D']

Time and space complexity

Amortized means that an occasional append resizes the underlying array and costs O(n), but averaged over many operations each one is O(1).

Variants and common mistakes

• Deque (double-ended queue): add and remove at both ends. collections.deque is one, and it can act as both a stack and a queue.
• Priority queue: removes the smallest (or largest) item first, not the oldest. Use heapq; see the binary heap page.
• Circular buffer: a fixed-size queue stored in an array with wrapping indexes. deque(maxlen=n) drops the oldest item when full.
• Thread-safe queues: queue.Queue for threads and asyncio.Queue for coroutines block while waiting for items.
• A queue built from two stacks: push to an in-stack, and when the out-stack is empty move everything across. Each item moves once, so operations are O(1) amortized.