Stacks, Queues & Monotonic Sequences
Constrained linear structures: call stack simulation, circular array ring buffers, expression bracket balancing, and linear O(N) monotonic stacks for next greater element.
1. Invariants of LIFO and FIFO Data Structures
Stacks and Queues are constrained linear data structures with strict element insertion and removal semantics.
The Stack Invariant (LIFO - Last-In, First-Out):
Elements are added and removed strictly from one boundary called the Top. The last element pushed is guaranteed to be the first element popped. Stacks form the basis of CPU function call frames, backtracking, and expression parsing (Dijkstra's Shunting Yard algorithm).
The Queue Invariant (FIFO - First-In, First-Out):
Elements are inserted at the Tail (Enqueue) and removed strictly from the Head (Dequeue). Queues model fair asynchronous scheduling, web server thread pools, and Breadth-First Search (BFS) graph traversals.
1def is_valid_parentheses(s: str) -> bool:2 """Validates balanced bracket sequence using a LIFO stack in O(N) time and O(N) space."""3 mapping = {')': '(', '}': '{', ']': '['}4 stack = []56 for char in s:7 if char in mapping:8 # Closing bracket: top must match9 top_element = stack.pop() if stack else '#'10 if mapping[char] != top_element:11 return False12 else:13 # Opening bracket: push onto stack14 stack.append(char)1516 return len(stack) == 01718# Tests19print('"{[()]}" -> Valid:', is_valid_parentheses("{[()]}"))20print('"([)]" -> Valid:', is_valid_parentheses("([)]"))
"{[()]}" -> Valid: True
"([)]" -> Valid: False2. Circular Queue (Ring Buffer) Memory Layout
Implementing a queue with a naive dynamic array causes O(N) dequeue operations due to shifting elements.
A Ring Buffer (Circular Queue) eliminates shifts by wrapping head and tail pointers using modulo arithmetic: next_index = (current_index + 1) % Capacity. Both enqueue and dequeue execute in deterministic O(1) time with zero memory churn.
Stack vs Queue vs Deque Complexity Comparison
| Data Structure | Push / Enqueue | Pop / Dequeue | Peek / Front | Memory Overhead |
|---|---|---|---|---|
| Stack (Array-backed) | O(1) Amortized | O(1) | O(1) | Contiguous (Minimal) |
| Queue (Ring Buffer) | O(1) | O(1) | O(1) | Fixed Array (Zero GC) |
| Queue (Linked List) | O(1) | O(1) | O(1) | 24 bytes/node pointer overhead |
| Double-Ended Queue (Deque) | O(1) Front & Back | O(1) Front & Back | O(1) | Chunked Array Pages |
Quick Syntax & Reference Sheet
| Concept / Rule | Syntax / Usage |
|---|---|
| Stack Operations | stack.append(x) # push O(1)
stack.pop() # pop O(1)
stack[-1] # peek O(1) |
| Ring Buffer Modulo Arithmetic | tail = (tail + 1) % CAPACITY
head = (head + 1) % CAPACITY |
Common Pitfalls & Developer Mistakes
Popping from an Empty Stack or Dequeuing from Empty Queue
Why it happens:
Using a Naive Python List as a Queue via `list.pop(0)`
Why it happens: