Cheat sheet: Ch 05 Stacks & Queues

Stacks & Queues

dsa.fetehadin.com

Last in, first out. The stack ADT (push, pop, peek, isEmpty, isFull) built on a fixed array with a top index, plus overflow and underflow.

push	O(1)
pop	O(1)
peek / isEmpty / isFull	O(1)
search for a value	O(n): not a stack operation
Space	O(MAX), fixed when the array is declared

✗Writing st[top++] = x with top = -1 (writes to index −1). Use st[++top] = x.
✗Popping without checking isEmpty() (underflow).
✗Pushing without checking isFull() (writes past the array).

5.2 Stacks with a Linked List

The same stack ADT, but the top is the head of a linked list. No fixed capacity, push and pop stay O(1), and the bracket-matching application.

push (insert at head)	O(1)
pop (delete head)	O(1)
peek / isEmpty	O(1)
Space	O(n), one node (data + pointer) per item

✗Using the tail as the top, making pop O(n).
✗Forgetting delete in pop (memory leak).
✗Reading top->data after deleting the node. Save the value first.

5.3 Queues with an Array

First in, first out. Why a naive array queue makes dequeue O(n), how a front index makes it O(1), and the wasted-slot problem that leads to the circular queue.

enqueue (at rear)	O(1)
dequeue, naive (shift left)	O(n)
dequeue, with front index	O(1)
front / isEmpty	O(1)
Space	O(MAX)

✗Confusing front and rear (items enter at the rear, leave at the front).
✗Dequeuing without checking for empty.
✗With a front index, testing rear == -1 for empty. The correct test is front > rear.

5.4 Queues with a Linked List

Keep two pointers, front and rear. Enqueue at the rear and dequeue at the front, both O(1), with no capacity limit.

enqueue (insert after rear)	O(1)
dequeue (delete front)	O(1)
peek / isEmpty	O(1)
Space	O(n)

✗Dequeuing from the tail (needs the previous node, so O(n)).
✗Forgetting rear = nullptr when the queue becomes empty. The next enqueue then writes through a dangling pointer.
✗Enqueue into an empty queue without setting both front and rear.

5.5 Circular Queue

Let front and rear wrap around with the modulo operator, so freed slots are reused. All operations O(1) on a fixed array.

enqueue	O(1)
dequeue	O(1)
front / isEmpty / isFull	O(1)
Space	O(N), and every slot is usable

✗Writing rear++ instead of rear = (rear + 1) % N.
✗Testing front == rear for both empty and full. Without a count (or one spare slot) they look the same.
✗Printing from 0 to rear instead of starting at front and wrapping.

5.6 std::stack, std::queue & std::deque

The standard library versions you will use in real code and on LeetCode, their method names, and the classic traps (pop returns void, empty checks).

stack push / pop / top	O(1)
queue push / pop / front / back	O(1)
deque push/pop at either end	O(1)
deque d[i]	O(1)
Space	O(n)

✗Writing int x = s.pop();. It does not compile; pop() returns void. Read top() first.
✗Calling top() / front() / pop() on an empty container (undefined behaviour). Check empty().
✗Using q.top() on a queue (it is front()), or s.front() on a stack (it is top()).

Stack:: LIFO collection: push and pop at the top only.
LIFO:: Last In, First Out.
Overflow / underflow:: Pushing onto a full stack / popping from an empty one.
Queue:: FIFO collection: enqueue at the rear, dequeue from the front.
FIFO:: First In, First Out.
Circular queue:: Array queue whose indices wrap around with % N so freed slots are reused.
Deque:: Double-ended queue: insert and remove at both ends in O(1).