Introduction
In the vast landscape of data structures, stacks and queues stand out as deceptively simple yet incredibly powerful. They’re not as flashy as trees or graphs, but they’re fundamental building blocks that appear everywhere—from the way your browser’s back button works to how print jobs are processed.
These are Abstract Data Types (ADTs), meaning we define their behavior without specifying implementation. This article explores both, showing how they work and where they appear.
Stacks: Last In, First Out
A stack is like a stack of plates: you add to the top, and you remove from the top. This Last In, First Out (LIFO) behavior is intuitive and appears in many computing contexts.
Core operations:
- push(item): Add item to top of stack
- pop(): Remove and return top item
- peek(): View top item without removing
- isEmpty(): Check if stack is empty
Time complexity: All operations are O(1) with proper implementation.
Stack Implementations
Array-based (Python list):
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop() if self.items else None
def peek(self):
return self.items[-1] if self.items else None
def is_empty(self):
return len(self.items) == 0
Linked list-based: Also O(1), but uses more memory per element. Choice depends on expected size and memory constraints.
Queues: First In, First Out
A queue is like a line at a store: first person in line gets served first. This First In, First Out (FIFO) behavior models many real-world scenarios.
Core operations:
- enqueue(item): Add item to back of queue
- dequeue(): Remove and return front item
- front(): View front item without removing
- isEmpty(): Check if queue is empty
Queue Implementations
Simple implementation using list: Works but can be O(n) for dequeue.
Linked list-based: O(1) for both operations with proper implementation.
Circular buffer: Fixed-size, memory-efficient implementation often used in embedded systems.
from collections import deque
queue = deque()
queue.append(1) # enqueue
queue.popleft() # dequeue
Real-World Applications
Stacks:
- Function call stack: How programming languages manage function calls and local variables
- Undo mechanisms: Text editors use stacks to track changes for undo
- Expression evaluation: Converting and evaluating mathematical expressions
- Back navigation: Browser history works as a stack of visited pages
- Parenthesis matching: Validating balanced brackets in code
- Tower of Hanoi: Classic puzzle solution
Queues:
- Print spooling: Print jobs wait in queue
- Task scheduling: Operating systems schedule tasks from queues
- Breadth-first search: Graph traversal uses queues
- Message queues: Kafka, RabbitMQ handle asynchronous communication
- Customer service: Call centers and support tickets
- CPU scheduling: Processes wait in ready queues
Stack Applications in Detail
Balanced Parentheses
A classic problem: check if brackets are balanced (every opening has a closing of the same type, in correct order).
def is_balanced(s):
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for char in s:
if char in '({[':
stack.append(char)
elif char in ')}]':
if not stack or stack.pop() != pairs[char]:
return False
return len(stack) == 0
Infix to Postfix Conversion
Mathematical expressions can be converted to postfix (Reverse Polish Notation) for easier evaluation. Stacks handle operator precedence and parentheses.
Queue Applications in Detail
Breadth-First Search
BFS explores graphs level by level using a queue:
def bfs(graph, start):
visited = {start}
queue = [start]
while queue:
node = queue.pop(0)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
Priority Queues
When elements have priorities, a priority queue ensures highest (or lowest) priority elements are dequeued first. Often implemented with heaps.
Data Structure Relationships
Stacks and queues are related to other structures:
- Deques (double-ended queues): Support insertion/removal from both ends
- Priority queues: Elements have associated priorities
- Deques can implement stacks and queues: Just use different ends
Array vs Linked List Implementations
Stack: Array vs Linked List
Array-based stack (Python list):
- Pros: Memory efficient (contiguous), excellent cache locality, O(1) amortized push
- Cons: Occasional O(n) resize cost, fixed capacity without resizing
Linked list-based stack:
- Pros: No resize cost, O(1) worst-case push
- Cons: Higher memory per element (pointer overhead), poor cache locality
class StackLinkedList:
class _Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
def __init__(self):
self._head = None
self._size = 0
def push(self, item):
self._head = self._Node(item, self._head)
self._size += 1
def pop(self):
if self.is_empty():
raise IndexError("pop from empty stack")
value = self._head.value
self._head = self._head.next
self._size -= 1
return value
def peek(self):
if self.is_empty():
raise IndexError("peek from empty stack")
return self._head.value
def is_empty(self):
return self._head is None
def __len__(self):
return self._size
Queue: Array vs Linked List
class QueueLinkedList:
class _Node:
def __init__(self, value):
self.value = value
self.next = None
def __init__(self):
self._head = None
self._tail = None
self._size = 0
def enqueue(self, item):
node = self._Node(item)
if self._tail:
self._tail.next = node
self._tail = node
if not self._head:
self._head = node
self._size += 1
def dequeue(self):
if self.is_empty():
raise IndexError("dequeue from empty queue")
value = self._head.value
self._head = self._head.next
if not self._head:
self._tail = None
self._size -= 1
return value
def front(self):
if self.is_empty():
raise IndexError("front from empty queue")
return self._head.value
def is_empty(self):
return self._head is None
def __len__(self):
return self._size
Circular Queues
A circular buffer (ring buffer) uses a fixed-size array with wrap-around indices:
class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity
self.buffer = [None] * capacity
self.head = 0
self.tail = 0
self.size = 0
def enqueue(self, item):
if self.is_full():
raise OverflowError("Queue is full")
self.buffer[self.tail] = item
self.tail = (self.tail + 1) % self.capacity
self.size += 1
def dequeue(self):
if self.is_empty():
raise IndexError("dequeue from empty queue")
item = self.buffer[self.head]
self.head = (self.head + 1) % self.capacity
self.size -= 1
return item
def front(self):
if self.is_empty():
raise IndexError("front from empty queue")
return self.buffer[self.head]
def is_empty(self):
return self.size == 0
def is_full(self):
return self.size == self.capacity
def __len__(self):
return self.size
Circular queues are widely used in:
- Embedded systems: Fixed-size hardware buffers
- Audio/video streaming: Playback buffers (jitter buffers)
- Network packet processing: NIC ring buffers
- Logging: Fixed-size log buffers (e.g., Kafka, systemd journal)
Deque (Double-Ended Queue)
Python’s collections.deque is a highly optimized deque implementation:
from collections import deque
d = deque()
# Stack operations
d.append(10) # push right
d.pop() # pop right
# Queue operations
d.append(10) # enqueue right
d.popleft() # dequeue left
# Deque-specific
d.appendleft(5) # push left
d.popright() # pop right (same as pop())
d.rotate(1) # rotate all elements right by 1
d.extend([1,2]) # extend right
d.extendleft([3,4]) # extend left (note: reverses order)
# Fixed-size deque (drops oldest on overflow)
d = deque(maxlen=5)
for i in range(10):
d.append(i)
# d now contains [5, 6, 7, 8, 9]
All deque operations are O(1). The implementation uses a doubly-linked list of fixed-size blocks, combining the cache performance of arrays with the flexibility of linked lists.
Monotonic Stack / Queue Patterns
Monotonic Stack
A monotonic stack maintains elements in sorted order (increasing or decreasing). It is used for problems involving “next greater/smaller element.”
def next_greater_element(nums):
"""Find next greater element for each position."""
n = len(nums)
result = [-1] * n
stack = [] # stores indices, values decreasing
for i in range(n):
while stack and nums[stack[-1]] < nums[i]:
result[stack.pop()] = nums[i]
stack.append(i)
return result
def largest_rectangle_area(heights):
"""Find largest rectangle in histogram."""
stack = []
max_area = 0
heights = heights + [0] # sentinel
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
Monotonic Queue
A monotonic queue maintains elements in sorted order for sliding window problems:
from collections import deque
def max_sliding_window(nums, k):
"""Maximum in each sliding window of size k."""
result = []
dq = deque() # stores indices, values decreasing
for i, n in enumerate(nums):
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if dq[0] == i - k:
dq.popleft()
if i >= k - 1:
result.append(nums[dq[0]])
return result
Expression Evaluation with Stacks
Infix to Postfix (Shunting Yard)
def infix_to_postfix(expression):
precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
output = []
operators = []
for token in expression.split():
if token.isdigit():
output.append(token)
elif token == '(':
operators.append(token)
elif token == ')':
while operators and operators[-1] != '(':
output.append(operators.pop())
operators.pop() # remove '('
else:
while (operators and operators[-1] != '(' and
precedence.get(operators[-1], 0) >= precedence.get(token, 0)):
output.append(operators.pop())
operators.append(token)
while operators:
output.append(operators.pop())
return ' '.join(output)
def evaluate_postfix(expression):
stack = []
for token in expression.split():
if token.isdigit():
stack.append(int(token))
else:
b = stack.pop()
a = stack.pop()
if token == '+': stack.append(a + b)
elif token == '-': stack.append(a - b)
elif token == '*': stack.append(a * b)
elif token == '/': stack.append(a / b)
elif token == '^': stack.append(a ** b)
return stack[0]
BFS with Queue, DFS with Stack
def dfs_iterative(graph, start):
"""DFS using explicit stack (avoids recursion limit)."""
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(node, end=' ')
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
def bfs_iterative(graph, start):
"""BFS using deque for O(1) popleft."""
from collections import deque
visited = {start}
queue = deque([start])
while queue:
node = queue.popleft()
print(node, end=' ')
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
Java Implementations
Java Stack (Legacy) and Deque (Preferred)
import java.util.*;
public class StackExample {
public static void main(String[] args) {
// Legacy Stack (extends Vector - synchronized, slower)
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
int top = stack.pop(); // 2
// Modern Deque (preferred - ArrayDeque)
Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1); // push
deque.addFirst(2);
int first = deque.removeFirst(); // pop - 2
// As a queue
Deque<Integer> queue = new ArrayDeque<>();
queue.addLast(1); // enqueue
queue.addLast(2);
int front = queue.removeFirst(); // dequeue - 1
}
}
Java Queue Interface
import java.util.*;
public class QueueExample {
public static void main(String[] args) {
// LinkedList as Queue
Queue<String> queue = new LinkedList<>();
queue.offer("task1"); // enqueue (returns false if full)
queue.offer("task2");
String head = queue.poll(); // dequeue (returns null if empty)
String peek = queue.peek(); // front (returns null if empty)
// PriorityQueue
Queue<Integer> pq = new PriorityQueue<>(); // min-heap
pq.offer(30);
pq.offer(10);
pq.offer(20);
System.out.println(pq.poll()); // 10 (smallest)
}
}
Real-World Uses with Code Examples
Browser History (Back/Forward)
class BrowserHistory:
def __init__(self, homepage):
self.back_stack = []
self.forward_stack = []
self.current = homepage
def visit(self, url):
self.back_stack.append(self.current)
self.current = url
self.forward_stack.clear() # Clear forward history
def back(self):
if not self.back_stack:
return None
self.forward_stack.append(self.current)
self.current = self.back_stack.pop()
return self.current
def forward(self):
if not self.forward_stack:
return None
self.back_stack.append(self.current)
self.current = self.forward_stack.pop()
return self.current
Task Scheduler (Round Robin Queue)
from collections import deque
class RoundRobinScheduler:
def __init__(self, time_slice):
self.queue = deque()
self.time_slice = time_slice
def add_process(self, pid, burst_time):
self.queue.append((pid, burst_time))
def run(self):
while self.queue:
pid, burst = self.queue.popleft()
if burst > self.time_slice:
print(f"P{pid}: ran for {self.time_slice}ms (remaining {burst - self.time_slice}ms)")
self.queue.append((pid, burst - self.time_slice))
else:
print(f"P{pid}: completed (ran final {burst}ms)")
Undo/Redo in Text Editor
class TextBuffer:
def __init__(self):
self.content = ""
self.undo_stack = []
self.redo_stack = []
def write(self, text):
self.undo_stack.append(self.content)
self.content += text
self.redo_stack.clear()
def undo(self):
if self.undo_stack:
self.redo_stack.append(self.content)
self.content = self.undo_stack.pop()
def redo(self):
if self.redo_stack:
self.undo_stack.append(self.content)
self.content = self.redo_stack.pop()
External Resources
Conclusion
Despite their simplicity, stacks and queues are indispensable. They appear in fundamental algorithms, operating systems, and countless applications. Understanding them is essential for any programmer.
The beauty is in their versatility: the same underlying structure enables everything from function call management to graph traversal to job scheduling. Master these basics, and you’ll see them everywhere.
Comments