Stacks, queues, and deques

Choose a stack for undo history, a queue for arriving jobs, and a deque when either end can change.

Predict what leaves next

Add A, B, C:

Stack:  bottom [A B C] top     remove -> C
Queue:  front  [A B C] back    remove -> A
Deque:  front  [A B C] back    remove -> A or C

These names describe interfaces. A stack removes the newest item: last in, first out. A queue removes the oldest: first in, first out. A deque supports insertion and removal at both ends.

A priority queue chooses by priority instead of arrival time. See heaps for that separate interface.

Keep the ends cheap

A dynamic array makes a good stack. Push appends at the end; pop shortens that end. Push costs O(1) amortized, pop costs O(1) without shrinking, and peeking costs O(1).

Removing an array's first element by shifting costs O(n). A circular array avoids that shift. It stores a front index and wraps indices around the allocation.

Capacity 4, front = 2, size = 3
Physical slots:  [C, _, A, B]
Logical queue:         A, B, C

remove A:       [C, _, _, B]   front = 3, size = 2
add D:          [C, D, _, B]   logical queue B, C, D

The invariant: logical item i lives at (front + i) modulo capacity, for 0 ≤ i < size. Storing size distinguishes an empty buffer from a full buffer when indices wrap.

A fixed-capacity circular queue offers O(1) insertion and removal, but must reject, overwrite, or wait when full. A growing version occasionally copies items into logical order in a larger array. Its insertion cost becomes O(1) amortized.

A linked queue with head and tail pointers also offers O(1) enqueue and dequeue. A doubly linked list or circular array can implement a deque. All store O(n) items; links or spare capacity add overhead. Searching for an arbitrary value still takes O(n).

Predict and modify

1. Push A, push B, pop, push C, pop on a stack. What remains?
2. Why is an array plus a forever-increasing front index insufficient for a long-running queue?
3. Add removal from the back to the circular queue. Which index should you clear?

class RingQueue:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.slots = [None] * capacity
        self.front = 0
        self.size = 0

    def push(self, value):
        if self.size == len(self.slots):
            raise OverflowError("queue is full")
        index = (self.front + self.size) % len(self.slots)
        self.slots[index] = value
        self.size += 1

    def pop(self):
        if self.size == 0:
            raise IndexError("queue is empty")
        value = self.slots[self.front]
        self.slots[self.front] = None
        self.front = (self.front + 1) % len(self.slots)
        self.size -= 1
        return value


queue = RingQueue(3)
for value in ["A", "B", "C"]:
    queue.push(value)
try:
    queue.push("D")
except OverflowError:
    pass
else:
    raise AssertionError("full queue accepted an item")
assert queue.pop() == "A"
queue.push("D")
assert [queue.pop(), queue.pop(), queue.pop()] == ["B", "C", "D"]
queue.push(None)
assert queue.pop() is None

Use a stack in Valid Parentheses and a deque in Sliding Window Maximum.

Next: Hash maps and sets.