Stack and Queue Interview Questions

Stack Basics

LIFO. Use for: matching (parentheses, brackets), parsing, and "next greater/smaller" type problems.

Classic problems

• Valid parentheses: push opening, pop on close and match.
• Min stack: auxiliary stack or single stack storing pairs (value, min).
• Next greater element: monotonic stack (decreasing).

Monotonic Stack

Maintain a stack that is strictly increasing or decreasing. When you push, pop until the property holds. Used for "next greater," "next smaller," and histogram area.

Queue and BFS

FIFO. Level-order traversal, shortest path in unweighted graph, and "first K" or "recent K" problems.

Examples

• Level order traversal of tree.
• Implement stack using queues (or queue using stacks).

Design Problems

• Implement stack with getMin in O(1).
• Implement queue using two stacks.
• LRU cache (hash map + doubly linked list; not strictly stack/queue but similar feel).

Summary

Stack for "last in, first out" and matching; queue for BFS and order. Use Preplume(/) to practice.