Stacks, Queues, and Deques

Stacks and queues are collections with a strict rule about which item comes out next; a deque makes both fast.

Stack (LIFO)

• Stack: last in, first out. Add and remove at the same end (the top).
• push: add to the top. pop: remove and return the top. peek: read the top without removing.
• Build with a Python list: append to push, pop() (no arg) to pop, list[-1] to peek.
• The “top” is the right end of the list.
• append and pop() are O(1); space is O(n).

Queue (FIFO)

• Queue: first in, first out. Enter at the back, leave from the front.
• enqueue: add to the back. dequeue: remove and return the front.
• A plain list is a poor queue: pop(0) shifts all remaining items left, so it is O(n) per removal.
• Use deque from collections: append to enqueue, popleft to dequeue, both O(1).

Deque (double-ended queue)

• from collections import deque (not built in).
• Four O(1) end moves: append (right), appendleft (left), pop (right), popleft (left).
• Reaching into the middle by index is O(n); use a list if you need random access.
• Works as a fast stack too, but a list already suffices for a stack.

Complexity

Which end

STACK (LIFO)          QUEUE (FIFO)
push/pop -> top       enqueue -> back
newest leaves first   oldest leaves first
                      front <- dequeue

Gotchas

• pop() on an empty list / popleft() on an empty deque raises an error. Check if stack: before removing.
• Using list.pop(0) for a queue works but is O(n) per removal; use deque + popleft.
• Mixing up ends: a list-stack’s top is list[-1], the right end.
• Forgetting from collections import deque raises NameError.

Uses

• Stack: undo history, the call stack, balanced brackets, expression evaluation.
• Queue: tasks in arrival order (print jobs, requests), breadth-first search (BFS).