Skip to content

Stacks, Queues, and Deques

These abstractions restrict where elements enter and leave a sequence.

  • A stack is last-in, first-out: push, peek, and pop.
  • A queue is first-in, first-out: enqueue, peek, and dequeue.
  • A deque supports insertion and removal at both ends.

Java collections

ArrayDeque implements both Deque and Queue and is a strong general-purpose choice for stacks and queues. It does not permit null elements.

Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
String top = stack.pop(); // "second"

Queue<String> queue = new ArrayDeque<>();
queue.add("first");
queue.add("second");
String head = queue.remove(); // "first"

Operations at either end are amortized O(1) for an array-backed deque. Interfaces also offer pairs such as remove/poll and element/peek: the first in each pair may throw on an empty container, while the second reports absence. Consult the Java API contract for exact behavior.

Applications

  • stacks: expression parsing, DFS, backtracking, call-stack simulation;
  • queues: BFS, buffering, task scheduling;
  • deques: sliding-window algorithms and work-stealing schedulers.

Exercises

  1. Check balanced brackets with a stack.
  2. Implement a queue using two stacks and analyze amortized cost.
  3. Compute sliding-window maxima using a monotonic deque.