Repository navigation
006 — Queues and Deques
If a stack is a pile of trays, a queue is the line of people waiting to grab one. Where a stack rewards whoever showed up last, a queue is fair: whoever got there first gets served first.
Picture the line at a coffee shop. New customers join at the back of the line. The barista serves whoever's at the front. Nobody gets to cut to the middle, and nobody gets served out of order.
- ☕ First person in line = first person served. First In, First Out — FIFO.
- 🚶 Join at the back, leave from the front — two different ends for two different operations.
Now imagine that same coffee shop adds a second door — a "VIP" door right at the front of the line, where people can also join at the front (skip-the-line) or leave from the back (give up and walk out). A line with two usable ends, front and back, both for joining and leaving, is a deque ("double-ended queue"). A plain queue only ever touches one end for joining and the other for leaving; a deque lets you do either operation at either end.
A queue supports enqueue (add to the back) and dequeue (remove from the front). A deque generalizes this: pushFront, pushBack, popFront, popBack — all in O(1).
Here's the trap: Array looks like a natural queue, but it isn't a good one. removeFirst() on an array is O(n) — removing from the front means shifting every remaining element left by one, just like the array chapter warned. Swift's standard library also doesn't ship a Deque type — Apple's separate swift-collections package adds one (Deque<T>), but it isn't part of the core stdlib you get for free. Because of that gap, and because interviews want to see you reason about why the naive approach is slow, the hand-rolled versions below are the implementation here.
Reach for a queue when:
- You're doing a breadth-first traversal (BFS) — process everything at the current "layer" before moving to the next.
- You're modeling anything with fairness/ordering guarantees: task scheduling, request buffering, print queues.
Reach for a deque when:
- You need a sliding window that grows/shrinks from both ends (e.g., "maximum in every window of size k" uses a monotonic deque).
- You need queue and stack behavior interchangeably.
Queue — one door in, one door out:
enqueue ──▶ ──▶ dequeue
┌────┐ ┌────┐ ┌────┐ ┌────┐
│ 42 │◀───│ 7 │◀───│ 25 │◀───│ 10 │
└────┘ └────┘ └────┘ └────┘
front back
(leaves here) (joins here)
Deque — both ends open for joining or leaving:
pushFront/popFront pushBack/popBack
◀────▶ ┌────┐┌────┐┌────┐ ◀────▶
│ 25 ││ 7 ││ 42 │
└────┘└────┘└────┘
front back
No stdlib equivalent gives O(1) on both ends out of the box, so both types below are built from scratch.
A classic interview pattern: back a queue with two stacks. New items go on inStack. Dequeuing pops from outStack; if outStack is empty, dump all of inStack into it first (reversing the order so the oldest item ends up on top).
struct Queue<T> {
private var inStack: [T] = []
private var outStack: [T] = []
var isEmpty: Bool { inStack.isEmpty && outStack.isEmpty }
mutating func enqueue(_ value: T) {
inStack.append(value) // O(1)
}
mutating func dequeue() -> T? {
if outStack.isEmpty {
// Move everything over, reversing order, so the
// oldest-enqueued item ends up on top of outStack.
while let value = inStack.popLast() {
outStack.append(value)
}
}
return outStack.popLast() // O(1) once outStack is loaded
}
func peek() -> T? {
outStack.last ?? inStack.first
}
}private final class DequeNode<T> {
var value: T
var prev: DequeNode<T>?
var next: DequeNode<T>?
init(_ value: T) { self.value = value }
}
final class Deque<T> {
private var head: DequeNode<T>?
private var tail: DequeNode<T>?
private(set) var count = 0
var isEmpty: Bool { count == 0 }
func pushFront(_ value: T) {
let node = DequeNode(value)
node.next = head
head?.prev = node
head = node
if tail == nil { tail = node }
count += 1
}
func pushBack(_ value: T) {
let node = DequeNode(value)
node.prev = tail
tail?.next = node
tail = node
if head == nil { head = node }
count += 1
}
@discardableResult
func popFront() -> T? {
guard let node = head else { return nil }
head = node.next
head?.prev = nil
if head == nil { tail = nil }
count -= 1
return node.value
}
@discardableResult
func popBack() -> T? {
guard let node = tail else { return nil }
tail = node.prev
tail?.next = nil
if tail == nil { head = nil }
count -= 1
return node.value
}
}Every operation only ever touches head, tail, or their immediate neighbors — no walking the list — so all four are O(1).
| Operation | Big-O | Why |
|---|---|---|
Enqueue (Queue) |
O(1) |
Push onto inStack — no shifting. See Big-O Notation. |
Dequeue (Queue) |
O(1) amortized |
Each element is moved from inStack to outStack exactly once over its lifetime, so the cost of that move is spread across all operations. |
pushFront / pushBack (Deque) |
O(1) |
Only relinks head/tail and one neighbor — a doubly linked list needs no traversal. |
popFront / popBack (Deque) |
O(1) |
Same reasoning — direct pointer updates. |
Array.removeFirst() (why we avoid it) |
O(n) |
Every remaining element must shift left by one — this is the naive-queue trap. |
| Search (either) | O(n) |
No shortcuts — worst case you check every element. |
A queue is a coffee-shop line — join at the back, get served from the front; a deque is that same line with a second door, so you can join or leave from either end.
In the two-stack Queue, a single call to dequeue() can, in the worst case, pop every element out of inStack and push it onto outStack — an O(n) operation. Explain why the overall dequeue operation is still considered amortized O(1), referencing how many times any single element actually gets moved between the two stacks over its entire lifetime in the queue.