Stacks and Queues Guide — LIFO and FIFO Patterns
Stacks and queues are fundamental data structures that restrict how elements are accessed. They model real-world waiting and processing patterns — from browser history to print queues, from function calls to task scheduling. Understanding them is essential for algorithm design and system architecture, as they form the backbone of countless algorithms and software systems.
The power of stacks and queues lies in their simplicity. By restricting access patterns, they make the order of element processing predictable and analyzable. A stack guarantees that the most recent element is processed first, making it ideal for backtracking and undo operations. A queue guarantees that elements are processed in the order they arrived, making it ideal for fair resource sharing and breadth-first exploration.
Stacks
A stack follows the Last-In, First-Out principle, where elements are added to and removed from the top only. Like a stack of plates, the most recently added element is the first one removed. The primary operations are push to add an element to the top, pop to remove and return the top element, and peek to view the top element without removing it. All three operations run in O(1) time.
Array-Based Implementation
Python lists make excellent stacks because appending and popping from the end are both O(1) amortized operations. The dynamic array backing Python’s list ensures that stack operations are efficient and cache-friendly due to contiguous memory allocation. Array-based stacks are almost always preferable to linked-list-based stacks because of their superior cache locality and lower memory overhead for the pointer-free implementation.
Bracket Matching
The bracket matching problem is a classic stack application. The algorithm iterates through the string, pushing opening brackets onto the stack. When a closing bracket is encountered, it checks whether the top of the stack contains the matching opening bracket. If it does, the opening bracket is popped. If not, the expression is invalid. After processing all characters, the expression is valid only if the stack is empty. This O(n) algorithm catches mismatched brackets and unbalanced expressions and is used in code editors, compilers, and configuration file validators.
Expression Evaluation
Compilers use stacks extensively for expression evaluation. The shunting-yard algorithm developed by Edsger Dijkstra converts infix notation to postfix using a stack for operators. Postfix expressions are then evaluated using a stack for operands. When an operator is encountered in postfix, it pops the required number of operands, applies the operation, and pushes the result back. This two-stack approach eliminates the need for parentheses and precedence rules during evaluation.
Key Use Cases
The function call stack stores return addresses and local variables during function calls, enabling nested function calls and recursion. Undo and redo in editors push actions as they occur and pop to undo, maintaining a history of user actions. Expression evaluation in compilers uses stacks for converting infix notation to postfix. Backtracking algorithms for maze solving, the N-Queens problem, and permutation generation use stacks to explore solution spaces systematically.
Queues
A queue follows the First-In, First-Out principle, where elements are added to the back and removed from the front. Like a line at a store, the first person in line is served first. The primary operations are enqueue to add an element to the back, dequeue to remove and return the front element, and peek to view the front element. All three operations run in O(1) time with an efficient implementation.
Circular Buffer Implementation
The most efficient queue implementation uses a circular buffer — an array with front and back pointers that wrap around to the beginning when reaching the end. This avoids the O(n) shifting that would be required by a naive array-based queue. When the buffer is full, it is resized to double its capacity, similar to dynamic array resizing. The circular buffer provides O(1) enqueue and dequeue operations with excellent cache locality.
Key Use Cases
Task scheduling uses queues for print queues, thread pool task queues, and process scheduling in operating systems. BFS traversal uses a queue to manage the frontier of graph exploration, ensuring nodes are visited in order of their distance from the source. Buffering uses queues for IO buffers, streaming data, and message queues that decouple data producers from consumers. Request handling uses queues in web servers to manage incoming requests fairly. Producer-consumer patterns use queues to decouple data production from consumption, enabling parallel processing pipelines.
Deque
A deque supports adding or removing from either end in O(1) time. Python’s collections.deque is an optimized C implementation of a double-ended queue. Deques are used for sliding window algorithms where elements are added to the back and removed from the front, undo with a fixed-size limit where old actions are discarded from the front, and palindrome checking where characters are compared from both ends.
Monotonic Queues
A monotonic queue maintains elements in increasing or decreasing order by removing elements that violate the monotonic property when new elements are added. The deque data structure is ideal for implementing monotonic queues since elements may need to be removed from either end. As new elements are added to the back, elements at the back that are smaller than the new element are removed to maintain decreasing order. Elements at the front are removed when they fall outside the current window.
The sliding window maximum problem is the classic application of monotonic queues. Given an array and a window size k, the algorithm finds the maximum element in every contiguous subarray of size k in O(n) time, which would require O(nk) time with a naive approach. This technique is used in image processing for maximum filters, in financial analysis for rolling maximum calculations that identify breakout patterns, and in real-time monitoring systems that track the highest metric value within sliding time windows.
BlockingQueue and Thread Safety
In concurrent programming, queues often serve as the communication channel between producer and consumer threads. Python’s queue.Queue provides a thread-safe FIFO queue with blocking operations — get blocks until an item is available, and put blocks if the queue is at maximum capacity. The task_done and join methods enable producers to wait until all items have been processed, implementing the producer-consumer pattern cleanly without explicit locks.
Java’s BlockingQueue interface provides similar functionality with implementations including ArrayBlockingQueue for bounded buffer with fairness policy, LinkedBlockingQueue for optionally bounded buffer, and PriorityBlockingQueue for priority-ordered processing. These thread-safe queue implementations are essential building blocks for thread pools, work-stealing algorithms, and event-driven architectures.
Deque Implementations in Practice
Python’s collections.deque is implemented as a doubly linked list of fixed-size blocks, providing the cache benefits of array-based storage with the flexibility of linked lists. Each block holds 64 items, and the deque maintains pointers to the leftmost and rightmost blocks. When a block becomes empty, it is freed, keeping memory usage proportional to the number of elements. This hybrid approach provides O(1) append and pop at both ends while maintaining good cache performance through block-level contiguity.
Java’s ArrayDeque uses a circular array that resizes when full, similar to the circular buffer implementation. It provides O(1) amortized time for add and remove at both ends and outperforms Java’s LinkedList for most use cases due to better cache locality. The ArrayDeque does not support null elements and is not thread-safe, requiring external synchronization for concurrent access.
Monotonic Stack Applications
The monotonic stack pattern extends beyond the sliding window maximum to several important algorithmic problems. The next greater element problem finds the first greater element to the right of each position in an array by maintaining a decreasing stack. When a larger element is encountered, it pops elements from the stack and records them as having found their next greater element. This technique solves in O(n) time what would require O(n squared) with a brute force approach.
The largest rectangle in a histogram problem uses a monotonic stack to find the maximum area rectangle that can be formed within a histogram. The stack maintains increasing bar heights, and when a shorter bar is encountered, the algorithm computes the area for bars popped from the stack using the new bar as the right boundary. This classic problem demonstrates how monotonic stacks can solve complex geometric problems through clever application of the LIFO principle.
Priority Queue
A priority queue dequeues the element with the highest priority first, regardless of insertion order. Unlike FIFO queues, priority determines processing order. The standard implementation uses a binary heap providing O(log n) insert and delete operations with O(1) peek. Use cases include Dijkstra’s shortest path algorithm, Huffman coding for data compression, task scheduling by priority, and event-driven simulation where events are processed in chronological order.
Frequently Asked Questions
What is the difference between a stack and a queue? A stack follows Last-In, First-Out. A queue follows First-In, First-Out. Stacks process the most recent element first; queues process the earliest element first.
When should I use array-based versus linked-list-based implementations? Array-based implementations benefit from cache locality. Linked-list-based implementations avoid resizing overhead. For stacks, array-based is almost always better.
What is the best way to implement a queue in Python? Use collections.deque for general-purpose O(1) append and popleft operations. For thread-safe queues, use queue.Queue.
How do I implement a stack with a queue? Use two queues: push to the primary queue, then rotate all preceding elements to the secondary queue. Each push is O(n), each pop is O(1).
What is a monotonic stack and when is it used? A monotonic stack maintains elements in increasing or decreasing order, used for next greater element, largest rectangle in a histogram, and sliding window maximum.
Arrays and Linked Lists Guide — Hash Tables Guide — Trees and Graphs Guide