• Overview
• Details
• Exercises

Stacks and queues are fundamental linear data structures that restrict access to elements in specific ways. A stack follows Last-In-First-Out (LIFO) semantics, while a queue follows First-In-First-Out (FIFO). Deques (double-ended queues) generalize both by allowing insertion and deletion at both ends. Monotonic queues are specialized variants that maintain elements in sorted order, enabling efficient sliding window maximum/minimum queries.

These structures are essential building blocks in algorithms, from expression evaluation and backtracking to breadth-first search and task scheduling. Understanding their variants and optimizations is crucial for efficient problem-solving.

Stack

• Operations: push(x), pop(), top(), isEmpty() - all O(1)
• Implementation: Array-based (with capacity doubling) or linked list
• Applications: Function call stack, expression parsing, DFS, undo mechanisms
• Variants: Min-stack (tracks minimum in O(1)), max-stack

Queue

• Operations: enqueue(x), dequeue(), front(), isEmpty() - all O(1)
• Implementation: Circular array or linked list
• Applications: BFS, task scheduling, buffering, producer-consumer
• Variants: Priority queue (heap-based), circular queue

Deque (Double-Ended Queue)

• Operations: pushFront(x), pushBack(x), popFront(), popBack() - all O(1)
• Implementation: Circular buffer or doubly-linked list
• Applications: Sliding window problems, palindrome checking, work-stealing schedulers
• Standard libraries: std::deque (C++), collections.deque (Python)

Monotonic Queue

• Property: Elements maintained in monotonic (increasing or decreasing) order
• Operations: Push with removal of violating elements, pop from front - amortized O(1)
• Key insight: Each element enters and leaves at most once
• Applications: Sliding window maximum/minimum in O(n), stock span problem
• Variants: Monotonic stack for next greater/smaller element problems

Performance Characteristics

• Time complexity: All basic operations O(1) for stack, queue, deque
• Space complexity: O(n) for n elements
• Cache efficiency: Array-based implementations have better locality
• Amortized analysis: Dynamic array resizing costs O(1) amortized per operation

1. Implement a min-stack: Design a stack that supports push, pop, top, and retrieving the minimum element in O(1) time.
2. Valid parentheses: Given a string containing '(', ')', '{', '}', '[', ']', determine if the input string is valid using a stack.
3. Sliding window maximum: Given an array and window size k, find the maximum in each sliding window using a monotonic deque.
4. Implement queue using stacks: Design a queue using only two stacks with amortized O(1) operations.
5. Next greater element: For each element in an array, find the next greater element to its right using a monotonic stack.
6. Design circular deque: Implement a circular double-ended queue with fixed capacity using an array.
7. Stock span problem: Calculate the span of stock prices (consecutive days with price ≤ current) using a monotonic stack.
8. Largest rectangle in histogram: Find the largest rectangular area in a histogram using a monotonic stack approach.