9 Stacks & Queues
Stacks & Queues
Controlling flow with LIFO and FIFO. Essential tools for algorithm management.
10 Stacks & Queues: Order in the Chaos
Stacks and Queues are the traffic controllers of data.
My realization: It’s all about order. Do I need the most recent thing (Stack) or the oldest thing (Queue)? Once I asked that, 50% of the confusion vanished.
10.1 Stacks
A stack is a LIFO (Last In, First Out) data structure that supports the following operations: - push(item): Add an item to the top of the stack - pop(): Remove and return the top item - peek(): Return the top item without removing it - is_empty(): Check if the stack is empty - size(): Return the number of items in the stack
10.1.1 Implementation (Python)
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if not self.is_empty():
return self.stack.pop()
return None
def peek(self):
if not self.is_empty():
return self.stack[-1]
return None
def is_empty(self):
return len(self.stack) == 0
def size(self):
return len(self.stack)10.2 Queues
A queue is a FIFO (First In, First Out) data structure that supports: - enqueue(item): Add an item to the back of the queue - dequeue(): Remove and return the front item - peek(): Return the front item without removing it - is_empty(): Check if the queue is empty - size(): Return the number of items in the queue
10.2.1 Implementation (Python)
from collections import deque
class Queue:
def __init__(self):
self.queue = deque()
def enqueue(self, item):
self.queue.append(item)
def dequeue(self):
if not self.is_empty():
return self.queue.popleft()
return None
def peek(self):
if not self.is_empty():
return self.queue[0]
return None
def is_empty(self):
return len(self.queue) == 0
def size(self):
return len(self.queue)10.3 Common Problems
10.3.1 Stack Problems
10.3.2 Queue Problems
10.4 Time Complexity
| Operation | Stack (Array) | Stack (Linked List) | Queue (Array) | Queue (Linked List) |
|---|---|---|---|---|
| Access | O(n) | O(n) | O(n) | O(n) |
| Search | O(n) | O(n) | O(n) | O(n) |
| Insertion | O(1) | O(1) | O(1) | O(1) |
| Deletion | O(1) | O(1) | O(1) | O(1) |
10.5 Common Patterns
- Using stacks for LIFO operations
- Using queues for BFS traversal
- Monotonic stacks for next greater/smaller element problems
- Two-stack queue implementation
- Deque for efficient operations on both ends
10.6 Tips for Interviews
- Always check for empty stack/queue before pop/dequeue
- Consider using a dummy node for certain problems
- For stack problems, think about the order of elements
- For queue problems, consider BFS traversal patterns
- Remember that Python’s
listcan be used as a stack, but for queues, prefercollections.deque