Algorithm Summary
A stack is last-in, first-out. A queue is first-in, first-out. The important choice is not only what data to store, but which item the algorithm must process next.
Priority queues
Java's PriorityQueue is a min-heap by default. A comparator can define a max-heap or order compound records.
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
minHeap.offer(5); // insert
minHeap.peek(); // inspect the minimum without removing it
minHeap.poll(); // remove and return the minimum
minHeap.remove(10); // remove a matching value when present
minHeap.size();
minHeap.isEmpty();
minHeap.contains(7);
minHeap.clear();Examples
Implement Queue using Stacks — LC 232
Use an input stack for pushes and an output stack for reads. When the output stack is empty, move every value from input to output; the reversal produces FIFO order. Do not move values again until the output stack is empty.
Implement Stack using Queues — LC 225
One queue is enough. After inserting a new value, rotate every older value from the front to the back so the newest value remains at the front and can be popped first.
Valid Parentheses — LC 20
Stacks naturally handle symmetric matching. Push opening brackets; for every closing bracket, require the matching opening bracket at the top. The string is valid only when every comparison succeeds and the stack is empty at the end.
Sliding Window Maximum — LC 239
Use a decreasing deque of candidate indices. Remove the front index when it leaves the window. Remove smaller values from the back because they can never become the maximum while the new, larger value remains in the window. The front always holds the current maximum.
while (!deque.isEmpty() && deque.peekFirst() <= i - k) deque.pollFirst();
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast();
deque.offerLast(i);Top K Frequent Elements — LC 347
Count frequencies in a map, then maintain a min-heap of at most k map entries ordered by frequency. Removing the smallest whenever the heap grows beyond k leaves the most frequent values.
PriorityQueue<Map.Entry<Integer, Integer>> heap =
new PriorityQueue<>((a, b) -> Integer.compare(a.getValue(), b.getValue()));Min Stack — LC 155
Maintain a second stack that records the minimum corresponding to every depth in the main stack. Push and pop both stacks together, allowing getMin() in O(1) time.