Stack & Queue
Quick reference
| Stack push | O(1) amortized (array) / O(1) (DLL) |
| Stack pop / peek | O(1) |
| Queue enqueue/dequeue — naive array (removeFirst shifts) | O(1) enqueue / O(n) dequeue |
| Queue enqueue/dequeue — Doubly Linked List backed | O(1) / O(1) |
| Queue enqueue/dequeue — two stacks | O(1) amortized / O(1) amortized |
A stack is a pile of cafeteria trays. Trays go on top. The only tray that you can take is the one on top. You cannot take one from the middle without first lifting off everything above it. This is Last In, First Out (LIFO). The item that you add most recently is the first item to come off.
A queue is a checkout line. New people join at the back. But the next person to serve is the person who has waited the longest, at the front of the line. This is First In, First Out (FIFO). The item that you add first is the first item to leave.
Both structures use the same two operations: add something and remove something. But the two structures do not agree about which end the removal happens on. A stack removes from the same end that it adds to. So if you push 1, 2, 3 and then pop three times, you get 3, 2, 1. The order is reversed. A queue removes from the opposite end that it adds to. So if you enqueue 1, 2, 3 and then dequeue three times, you get 1, 2, 3. The order stays the same. This one difference (same-end removal or opposite-end removal) is the whole distinction between the two structures.
Two structures, two disciplines
structure Stack:
// built on an array, OR on the head of a Doubly Linked List. Either one works.
items // the top of the stack is items[length - 1], or list.head
structure Queue:
// built on a Doubly Linked List. The head is the front, the tail is the back.
list // -> DoublyLinkedList from Phase 2. It is empty when list.head is NULL.Stack via array — push/pop/peek, O(1) amortized
function push(stack, value):
stack.items.append(value) // grow the array by one slot at the end
function pop(stack):
if stack.items is empty:
error "stack underflow"
return stack.items.removeLast() // shrink the array by one slot at the end
function peek(stack):
if stack.items is empty:
error "stack underflow"
return stack.items[length - 1] // look, do not removeStack via a doubly linked list — push/pop at the head, O(1) worst case
function push(stack, value):
insertAtHead(stack.list, value) // the operation from Phase 2, exactly
function pop(stack):
if stack.list.head is NULL:
error "stack underflow"
value = stack.list.head.value
deleteNode(stack.list, stack.list.head) // O(1), no walk needed
return valueQueue via a doubly linked list — enqueue at tail, dequeue at head, both O(1)
function enqueue(queue, value):
insertAtTail(queue.list, value) // the operation from Phase 2. O(1) thanks to the tail pointer.
function dequeue(queue):
if queue.list.head is NULL:
error "queue underflow"
value = queue.list.head.value
deleteNode(queue.list, queue.list.head) // O(1), no walk needed
return valueQueue via two stacks — O(1) amortized per operation, no linked list needed
structure TwoStackQueue:
inStack // takes every enqueue
outStack // supplies every dequeue
function enqueue(queue, value):
push(queue.inStack, value)
function dequeue(queue):
if queue.outStack is empty:
while queue.inStack is not empty: // pour everything across, one time
push(queue.outStack, pop(queue.inStack))
if queue.outStack is empty: // still empty after the pour: inStack was empty too
error "queue underflow"
return pop(queue.outStack)Stack push, pop, and peek are O(1), with no exception: no walk and no search, in any build. The queue is where the choice of structure matters. The removeFirst of a plain array moves every remaining element down one slot, which is O(n) for each dequeue. If you use the Phase 2 doubly linked list instead, or the two-stack trick, dequeue drops to O(1).
| Operation | Time | Space | Why |
|---|---|---|---|
| Stack push | O(1) amortized (array) / O(1) (DLL) | O(1) | Array: one write, and the occasional resize-and-copy averages out. DLL: rewrite a few pointers around the new head, with no resize ever. |
| Stack pop / peek | O(1) | O(1) | Only the top is touched: the last slot of the array or the head of the list. There is no walk in either build. |
| Queue enqueue/dequeue — naive array (removeFirst shifts) | O(1) enqueue / O(n) dequeue | O(1) | To remove the front slot leaves a gap. Every remaining element must move down one index to close it. |
| Queue enqueue/dequeue — Doubly Linked List backed | O(1) / O(1) | O(1) | insertAtTail and deleteNode(head) from Phase 2. The tail pointer and the prev/next of the node mean that neither end needs a walk. |
| Queue enqueue/dequeue — two stacks | O(1) amortized / O(1) amortized | O(1) extra (two stacks that hold the elements of the queue) | Each value is pushed onto inStack one time and poured to outStack a maximum of one time. The total pour work across n operations is O(n), so O(1) per operation on average, even though one dequeue can sometimes cost O(n) during a pour. |
Underflow — pop or dequeue from empty
If you pop or dequeue without a check for empty first, you dereference a value that is not there. This is a crash, or worse, a silent return of garbage. Every pop and dequeue must check for empty before it touches anything. This is the same discipline as a check that head is NULL before a delete from an empty linked list.
Fixed-size array stack overflowing, or a resizing one hiding an O(n) cost
A stack built on a fixed-size array can overflow with no error (a write past the allocated end) if push never checks the capacity first. A resizing array stack avoids this, but only because it sometimes copies every element into a bigger array. That one push is O(n), not O(1). It is still O(1) amortized over many pushes. But to treat every push as cheap is wrong if you reason about the worst-case latency for one specific operation, not the long-run average.
Naive array queue degrading to O(n) per operation
It is tempting to use the same array that worked for a stack. But a queue removes from the opposite end that it adds to. To remove index 0 from an array means a move of every other element down by one to close the gap. If you do this on every dequeue, a queue that looks O(1) is really O(n) for each operation, and O(n²) over a full run. The fix is the DLL-backed queue or the two-stack trick above, not a plain array with removeFirst.
Two-stack queue implemented wrong — pouring when outStack isn't empty
The order of outStack (oldest on top) stays correct only if a fresh pour never disturbs it while it still holds older, not-yet-dequeued values. If you pour into it while it is not empty, the older values that were already in the correct order on top get buried under a fresh reversed batch. This corrupts the FIFO order. A later dequeue can return a value that was enqueued more recently than one that is still underneath. The guard "pour only when outStack is empty" is not an optimization. It is what makes the algorithm correct.
Sign in to mark problems done — progress syncs across devices.