aloalgoStacks & Queues Summary
A quick reference for stack and queue techniques and problems to practice. Stacks and queues are two of the most fundamental abstract data types in computer science. They differ in how elements are added and removed: a stack follows Last-In-First-Out (LIFO) order, while a queue follows First-In-First-Out (FIFO) order.Despite their simplicity, stacks and queues are the building blocks for many important algorithms. Stacks power function call management, expression evaluation, undo operations, and the monotonic stack pattern for "next greater element" problems. Queues enable breadth-first search, level-order tree traversal, and task scheduling. Understanding when to use each one is essential for interview success.Key Concepts
The table below summarizes the core data structures and their most common applications. All operations on stacks and queues run in O(1) amortized time, making them extremely efficient.| Concept | Description |
|---|---|
| Stack (LIFO) | Last-In-First-Out, use list in Python |
| Queue (FIFO) | First-In-First-Out, use deque in Python |
| Monotonic Stack | Stack maintaining sorted order for next greater/smaller |
| BFS | Level-by-level traversal using queue |
| DFS | Depth-first traversal using stack |
Implementation in Python
In Python, use a regular list as a stack with append() to push and pop() to remove from the top. For queues, use collections.deque with append() to enqueue and popleft() to dequeue. Avoid using a list as a queue because popping from the front of a list is O(n) due to element shifting, while deque provides O(1) operations on both ends.The Monotonic Stack Pattern
A monotonic stack is a stack that maintains its elements in sorted order (either increasing or decreasing). It is the key technique for solving "next greater element" and "next smaller element" problems in O(n) time. The idea is to iterate through the array and pop elements from the stack whenever the current element violates the monotonic property. Each popped element has found its "next greater" or "next smaller" element.This pattern appears in problems like Daily Temperatures, Next Greater Element, Largest Rectangle in Histogram, and Trapping Rain Water. If a problem asks about the "nearest larger" or "nearest smaller" element for each position, a monotonic stack is almost certainly the right approach.Chapters
- Introduction to Stacks and Queues - Basic operations and differences
- Stack Applications and Patterns - Parentheses, expressions, monotonic stack
- Queue Applications and Patterns - BFS, level order, shortest path
Practice Problems
Easy
Medium
Hard
Was this helpful?
Company
Practice
© 2026 aloalgo. All rights reserved.