AlgoScope

Stack and Queue Algorithms

Two rules about which end you are allowed to touch, and the algorithms that fall out of them.

17 topics6 lessons2 families

A stack lets you reach only the top; a queue lets you reach only the front. Both are restrictions, and the point of a restriction is that it is cheap to honour: push, pop, enqueue and dequeue are O(1) because nothing else in the structure has to move when one item arrives or leaves.

They earn a category because the restriction matches the shape of certain problems. Nested brackets close in reverse order, so a stack tracks them. An expression evaluates innermost first, so a stack holds the operators still waiting for their operands. Depth-first search resumes the most recent branch, so it is a stack, explicit or the call stack. Breadth-first search wants the oldest frontier node first, so it is a queue.

The monotonic versions go one step further: pop from the stack while the top can never be an answer again. Each element is pushed once and popped once, so a scan that looks quadratic, for every element find the next larger one to its right, costs O(n) in total.

After this you can

  • Implement push, pop, enqueue and dequeue, and say why each is O(1)
  • Match brackets, evaluate postfix and convert infix using a stack of operators
  • Replace a nested next-greater scan with one pass of a monotonic stack
  • Keep the maximum of a sliding window in amortized O(1) with a monotonic deque
  • Build a queue out of two stacks and account for where the amortized cost goes
53bottomtop

pop returns 9: the most recently pushed item leaves first.

Open in the player →or start at step 5

In this order

  1. PushPlace an item on top. Nothing else moves, so it is O(1).
  2. PopTake the top item off. Only the top is ever touched.
  3. PeekRead the top item without removing it.
  4. EnqueueAdd an item at the rear. It waits behind everything already there.
  5. DequeueRemove the item at the front, which has waited longest.
  6. Balanced ParenthesesPush openers and pop on closers; balanced when every closer matches the top and the stack ends empty.
  7. Postfix EvaluationPush numbers; an operator pops two, applies itself, and pushes the result.
  8. Expression EvaluationTwo stacks, values and operators, evaluate infix in one pass; brackets fence the operator stack.
  9. Infix to PostfixOperands go straight to the output; operators wait on a stack until a lower-precedence one arrives.
  10. Queue Using Two StacksEnqueue onto an in stack; when the out stack is empty, pour everything across to reverse the order.
  11. Stack-based DFSIterative DFS: push the start, pop, visit, push unvisited neighbours.
  12. Next Greater ElementScan with a monotonic stack; each pop resolves an element's answer.
  13. Previous Greater ElementThe nearest larger value to the left, via a monotonic stack.
  14. Next Smaller ElementThe nearest smaller value to the right.
  15. Largest Rectangle in HistogramKeep a stack of rising bars; popping a bar bounds its rectangle by the nearest shorter bars on both sides.
  16. Sliding Window MaximumA monotonic deque of indices keeps the window maximum at the front in amortized O(1).

Also in this category

Queue Patterns

Where people go wrong

Whatever is still on a monotonic stack has no answer

When a next-greater scan finishes, the elements left on the stack are the ones no larger value ever arrived for. They get the default answer; leftovers on the stack are the expected end state, not a sign the loop went wrong.

Amortized is a claim about the sequence, not the call

A queue built from two stacks may pour n items across on a single dequeue. Each item is poured at most once, so n operations still cost O(n) in total, but any one call can take O(n) and a latency budget has to allow for it.

A queue on a plain array leaks its space

If dequeue only advances the front index, the slots behind it are never reused and the array grows for as long as the program runs. A circular queue wraps the front and rear indices around a fixed buffer instead.

Or a different category

Recursion

The order you need is already the call stack's order, and writing the stack out by hand adds nothing.

Sliding Window

The window carries a running sum or count rather than a maximum, so no deque is needed.

Lessons that teach these