Stacks and Queues

📖 Introduction

Stacks and queues are deceptively simple data structures that power some of the most important operations in computing. The browser's back button? A stack. Job scheduling in operating systems? Queues. Parsing expressions in compilers? Stacks again.

In my projects, I've used stacks for undo/redo functionality, queues for task processing pipelines, and monotonic stacks for optimizing range queries. Understanding these structures deeply—especially their variations like deques and priority queues—opens up elegant solutions to problems that would otherwise require complex logic.

---

🎯 Stack: Last In, First Out (LIFO)

A stack is a linear data structure where elements are added and removed from the same end (the "top").

Visual Representation

Stack Implementation

from typing import Optional, Generic, TypeVar

T = TypeVar('T')


class Stack(Generic[T]):
    """
    Stack implementation using Python list.
    All operations O(1) amortized.
    """
    
    def __init__(self):
        self._items: list[T] = []
    
    def push(self, item: T) -> None:
        """Add item to top. O(1) amortized."""
        self._items.append(item)
    
    def pop(self) -> T:
        """Remove and return top item. O(1)."""
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        return self._items.pop()
    
    def peek(self) -> T:
        """Return top item without removing. O(1)."""
        if self.is_empty():
            raise IndexError("Peek at empty stack")
        return self._items[-1]
    
    def is_empty(self) -> bool:
        """Check if stack is empty. O(1)."""
        return len(self._items) == 0
    
    def size(self) -> int:
        """Return number of items. O(1)."""
        return len(self._items)
    
    def __len__(self) -> int:
        return self.size()
    
    def __str__(self) -> str:
        return f"Stack({self._items})"


# Usage
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.peek())  # 3
print(stack.pop())   # 3
print(stack.pop())   # 2

Stack Using Linked List

from typing import Optional

class StackNode:
    def __init__(self, val):
        self.val = val
        self.next: Optional['StackNode'] = None


class LinkedStack:
    """
    Stack using linked list.
    O(1) push and pop with no amortization.
    """
    
    def __init__(self):
        self._top: Optional[StackNode] = None
        self._size = 0
    
    def push(self, val) -> None:
        new_node = StackNode(val)
        new_node.next = self._top
        self._top = new_node
        self._size += 1
    
    def pop(self):
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        val = self._top.val
        self._top = self._top.next
        self._size -= 1
        return val
    
    def peek(self):
        if self.is_empty():
            raise IndexError("Peek at empty stack")
        return self._top.val
    
    def is_empty(self) -> bool:
        return self._top is None
    
    def size(self) -> int:
        return self._size

---

📚 Queue: First In, First Out (FIFO)

A queue is a linear data structure where elements are added at one end (rear) and removed from the other (front).

Visual Representation

Queue Implementation with Deque

from collections import deque
from typing import Generic, TypeVar

T = TypeVar('T')


class Queue(Generic[T]):
    """
    Queue implementation using collections.deque.
    O(1) enqueue and dequeue.
    """
    
    def __init__(self):
        self._items: deque[T] = deque()
    
    def enqueue(self, item: T) -> None:
        """Add item to rear. O(1)."""
        self._items.append(item)
    
    def dequeue(self) -> T:
        """Remove and return front item. O(1)."""
        if self.is_empty():
            raise IndexError("Dequeue from empty queue")
        return self._items.popleft()
    
    def front(self) -> T:
        """Return front item without removing. O(1)."""
        if self.is_empty():
            raise IndexError("Front of empty queue")
        return self._items[0]
    
    def rear(self) -> T:
        """Return rear item without removing. O(1)."""
        if self.is_empty():
            raise IndexError("Rear of empty queue")
        return self._items[-1]
    
    def is_empty(self) -> bool:
        return len(self._items) == 0
    
    def size(self) -> int:
        return len(self._items)


# Usage
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.front())    # 1
print(queue.dequeue())  # 1
print(queue.dequeue())  # 2

Circular Queue (Fixed Size)

class CircularQueue:
    """
    Fixed-size circular queue.
    Efficient memory usage with wrap-around.
    """
    
    def __init__(self, capacity: int):
        self._items = [None] * capacity
        self._capacity = capacity
        self._front = 0
        self._rear = -1
        self._size = 0
    
    def enqueue(self, item) -> bool:
        """Add item. Returns False if full."""
        if self.is_full():
            return False
        
        self._rear = (self._rear + 1) % self._capacity
        self._items[self._rear] = item
        self._size += 1
        return True
    
    def dequeue(self):
        """Remove and return front item."""
        if self.is_empty():
            raise IndexError("Dequeue from empty queue")
        
        item = self._items[self._front]
        self._items[self._front] = None  # Help GC
        self._front = (self._front + 1) % self._capacity
        self._size -= 1
        return item
    
    def is_empty(self) -> bool:
        return self._size == 0
    
    def is_full(self) -> bool:
        return self._size == self._capacity


# Example: Circular buffer for streaming data
buffer = CircularQueue(3)
buffer.enqueue(1)
buffer.enqueue(2)
buffer.enqueue(3)
print(buffer.is_full())  # True
buffer.dequeue()         # Remove 1
buffer.enqueue(4)        # Now: [2, 3, 4]

---

🔄 Deque: Double-Ended Queue

A deque (pronounced "deck") allows O(1) operations at both ends.

from collections import deque

# Python's deque is highly optimized
d = deque()

# Operations at both ends - all O(1)
d.append(1)       # Add to right
d.appendleft(0)   # Add to left
d.pop()           # Remove from right
d.popleft()       # Remove from left

# Rotation
d.extend([1, 2, 3, 4, 5])
d.rotate(2)       # [4, 5, 1, 2, 3] - rotate right
d.rotate(-2)      # [1, 2, 3, 4, 5] - rotate left

# Bounded deque (oldest items dropped when full)
bounded = deque(maxlen=3)
bounded.extend([1, 2, 3])
bounded.append(4)  # [2, 3, 4] - 1 is dropped

Implementing Deque

class Deque:
    """
    Deque using doubly linked list.
    All operations O(1).
    """
    
    class _Node:
        def __init__(self, val):
            self.val = val
            self.prev = None
            self.next = None
    
    def __init__(self):
        # Sentinel nodes
        self._head = self._Node(None)
        self._tail = self._Node(None)
        self._head.next = self._tail
        self._tail.prev = self._head
        self._size = 0
    
    def push_front(self, val) -> None:
        """Add to front. O(1)."""
        node = self._Node(val)
        node.next = self._head.next
        node.prev = self._head
        self._head.next.prev = node
        self._head.next = node
        self._size += 1
    
    def push_back(self, val) -> None:
        """Add to back. O(1)."""
        node = self._Node(val)
        node.prev = self._tail.prev
        node.next = self._tail
        self._tail.prev.next = node
        self._tail.prev = node
        self._size += 1
    
    def pop_front(self):
        """Remove from front. O(1)."""
        if self.is_empty():
            raise IndexError("Pop from empty deque")
        node = self._head.next
        self._head.next = node.next
        node.next.prev = self._head
        self._size -= 1
        return node.val
    
    def pop_back(self):
        """Remove from back. O(1)."""
        if self.is_empty():
            raise IndexError("Pop from empty deque")
        node = self._tail.prev
        self._tail.prev = node.prev
        node.prev.next = self._tail
        self._size -= 1
        return node.val
    
    def is_empty(self) -> bool:
        return self._size == 0

---

📊 Stack Applications

Valid Parentheses

def is_valid_parentheses(s: str) -> bool:
    """
    Check if parentheses are balanced.
    Time: O(n), Space: O(n)
    """
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in '({[':
            stack.append(char)
        elif char in ')}]':
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
    
    return len(stack) == 0


# Examples
print(is_valid_parentheses("()[]{}"))    # True
print(is_valid_parentheses("([)]"))      # False
print(is_valid_parentheses("{[]}"))      # True

Evaluate Reverse Polish Notation

def eval_rpn(tokens: list[str]) -> int:
    """
    Evaluate expression in Reverse Polish Notation.
    Time: O(n), Space: O(n)
    """
    stack = []
    operators = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b),  # Truncate toward zero
    }
    
    for token in tokens:
        if token in operators:
            b = stack.pop()
            a = stack.pop()
            stack.append(operators[token](a, b))
        else:
            stack.append(int(token))
    
    return stack[0]


# Example: ["2", "1", "+", "3", "*"] = (2 + 1) * 3 = 9
print(eval_rpn(["2", "1", "+", "3", "*"]))

Min Stack

class MinStack:
    """
    Stack with O(1) getMin operation.
    """
    
    def __init__(self):
        self._stack = []      # (value, min_so_far)
    
    def push(self, val: int) -> None:
        current_min = min(val, self._stack[-1][1]) if self._stack else val
        self._stack.append((val, current_min))
    
    def pop(self) -> None:
        self._stack.pop()
    
    def top(self) -> int:
        return self._stack[-1][0]
    
    def get_min(self) -> int:
        return self._stack[-1][1]


# Alternative: Two stacks approach
class MinStack2:
    def __init__(self):
        self._stack = []
        self._min_stack = []
    
    def push(self, val: int) -> None:
        self._stack.append(val)
        if not self._min_stack or val <= self._min_stack[-1]:
            self._min_stack.append(val)
    
    def pop(self) -> None:
        val = self._stack.pop()
        if val == self._min_stack[-1]:
            self._min_stack.pop()
    
    def top(self) -> int:
        return self._stack[-1]
    
    def get_min(self) -> int:
        return self._min_stack[-1]

Daily Temperatures (Monotonic Stack)

def daily_temperatures(temperatures: list[int]) -> list[int]:
    """
    For each day, find how many days until warmer temperature.
    Time: O(n), Space: O(n)
    """
    n = len(temperatures)
    result = [0] * n
    stack = []  # Stack of indices
    
    for i in range(n):
        # Pop all days colder than current
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_idx = stack.pop()
            result[prev_idx] = i - prev_idx
        
        stack.append(i)
    
    return result


# Example
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))  # [1, 1, 4, 2, 1, 1, 0, 0]

---

📈 Monotonic Stack

A monotonic stack maintains elements in sorted order (either increasing or decreasing).

Next Greater Element

def next_greater_element(nums: list[int]) -> list[int]:
    """
    For each element, find next greater element.
    Time: O(n), Space: O(n)
    """
    n = len(nums)
    result = [-1] * n
    stack = []  # Decreasing stack of indices
    
    for i in range(n):
        # Pop elements smaller than current
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        
        stack.append(i)
    
    return result


# Example
print(next_greater_element([2, 1, 2, 4, 3]))  # [4, 2, 4, -1, -1]

Largest Rectangle in Histogram

def largest_rectangle_histogram(heights: list[int]) -> int:
    """
    Find largest rectangle in histogram.
    Time: O(n), Space: O(n)
    """
    stack = []  # Stack of indices, increasing heights
    max_area = 0
    
    for i, h in enumerate(heights):
        start = i
        
        while stack and stack[-1][1] > h:
            idx, height = stack.pop()
            max_area = max(max_area, height * (i - idx))
            start = idx
        
        stack.append((start, h))
    
    # Process remaining bars
    for idx, height in stack:
        max_area = max(max_area, height * (len(heights) - idx))
    
    return max_area


# Example
print(largest_rectangle_histogram([2, 1, 5, 6, 2, 3]))  # 10

Trapping Rain Water

def trap_rain_water(heights: list[int]) -> int:
    """
    Calculate trapped rain water.
    Time: O(n), Space: O(n) using stack
    """
    stack = []  # Stack of indices, decreasing heights
    water = 0
    
    for i, h in enumerate(heights):
        while stack and h > heights[stack[-1]]:
            bottom = stack.pop()
            
            if not stack:
                break
            
            distance = i - stack[-1] - 1
            bounded_height = min(h, heights[stack[-1]]) - heights[bottom]
            water += distance * bounded_height
        
        stack.append(i)
    
    return water


# Two pointer approach - O(1) space
def trap_rain_water_optimal(heights: list[int]) -> int:
    if not heights:
        return 0
    
    left, right = 0, len(heights) - 1
    left_max, right_max = 0, 0
    water = 0
    
    while left < right:
        if heights[left] < heights[right]:
            if heights[left] >= left_max:
                left_max = heights[left]
            else:
                water += left_max - heights[left]
            left += 1
        else:
            if heights[right] >= right_max:
                right_max = heights[right]
            else:
                water += right_max - heights[right]
            right -= 1
    
    return water

---

📊 Queue Applications

BFS (Level Order Traversal)

from collections import deque
from typing import Optional, List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def level_order_traversal(root: Optional[TreeNode]) -> List[List[int]]:
    """
    BFS using queue for level-order traversal.
    Time: O(n), Space: O(n)
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

Sliding Window Maximum

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    """
    Find maximum in each sliding window of size k.
    Time: O(n), Space: O(k)
    
    Uses monotonic decreasing deque.
    """
    if not nums or k == 0:
        return []
    
    result = []
    dq = deque()  # Store indices, values are decreasing
    
    for i in range(len(nums)):
        # Remove indices outside current window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # Remove smaller elements (they can never be max)
        while dq and nums[i] > nums[dq[-1]]:
            dq.pop()
        
        dq.append(i)
        
        # Add to result once we have full window
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result


# Example
print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

Task Scheduler

from collections import Counter, deque
import heapq

def least_interval(tasks: list[str], n: int) -> int:
    """
    Minimum time to complete tasks with cooldown n.
    Time: O(t log 26) where t is total tasks
    """
    count = Counter(tasks)
    max_heap = [-c for c in count.values()]
    heapq.heapify(max_heap)
    
    time = 0
    cooldown = deque()  # (available_time, count)
    
    while max_heap or cooldown:
        time += 1
        
        if max_heap:
            remaining = heapq.heappop(max_heap) + 1  # Decrement (negative)
            if remaining < 0:
                cooldown.append((time + n, remaining))
        
        if cooldown and cooldown[0][0] == time:
            _, count = cooldown.popleft()
            heapq.heappush(max_heap, count)
    
    return time

---

⭐ Priority Queue

A priority queue returns elements in priority order, not insertion order.

import heapq

# Python's heapq is a min-heap
pq = []
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 2)

print(heapq.heappop(pq))  # 1 (smallest first)
print(heapq.heappop(pq))  # 2


# For max-heap, negate values
max_pq = []
heapq.heappush(max_pq, -3)
heapq.heappush(max_pq, -1)
heapq.heappush(max_pq, -2)

print(-heapq.heappop(max_pq))  # 3 (largest first)


# Priority queue with custom objects
class Task:
    def __init__(self, priority: int, name: str):
        self.priority = priority
        self.name = name
    
    def __lt__(self, other):
        return self.priority < other.priority


task_queue = []
heapq.heappush(task_queue, Task(3, "Low priority"))
heapq.heappush(task_queue, Task(1, "High priority"))
heapq.heappush(task_queue, Task(2, "Medium priority"))

print(heapq.heappop(task_queue).name)  # "High priority"

Kth Largest Element

import heapq

def find_kth_largest(nums: list[int], k: int) -> int:
    """
    Find kth largest element.
    Time: O(n log k), Space: O(k)
    """
    # Maintain min-heap of size k
    min_heap = []
    
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    
    return min_heap[0]


# Alternative using heapq.nlargest
def find_kth_largest_builtin(nums: list[int], k: int) -> int:
    return heapq.nlargest(k, nums)[-1]

Merge K Sorted Lists

import heapq
from typing import Optional, List

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def merge_k_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    """
    Merge k sorted linked lists.
    Time: O(N log k), Space: O(k)
    """
    # Create wrapper for comparison
    class NodeWrapper:
        def __init__(self, node):
            self.node = node
        
        def __lt__(self, other):
            return self.node.val < other.node.val
    
    dummy = ListNode(0)
    current = dummy
    heap = []
    
    # Initialize heap with first node of each list
    for lst in lists:
        if lst:
            heapq.heappush(heap, NodeWrapper(lst))
    
    while heap:
        wrapper = heapq.heappop(heap)
        node = wrapper.node
        
        current.next = node
        current = current.next
        
        if node.next:
            heapq.heappush(heap, NodeWrapper(node.next))
    
    return dummy.next

---

📝 Practice Exercises

Exercise 1: Implement Queue Using Stacks

class MyQueue:
    """
    Implement queue using two stacks.
    Amortized O(1) for all operations.
    """
    
    def __init__(self):
        pass
    
    def push(self, x: int) -> None:
        pass
    
    def pop(self) -> int:
        pass
    
    def peek(self) -> int:
        pass
    
    def empty(self) -> bool:
        pass

Solution

class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []
    
    def push(self, x: int) -> None:
        self.in_stack.append(x)
    
    def pop(self) -> int:
        self._transfer()
        return self.out_stack.pop()
    
    def peek(self) -> int:
        self._transfer()
        return self.out_stack[-1]
    
    def empty(self) -> bool:
        return not self.in_stack and not self.out_stack
    
    def _transfer(self) -> None:
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

Exercise 2: Implement Stack Using Queues

from collections import deque

class MyStack:
    """
    Implement stack using queue(s).
    """
    
    def __init__(self):
        pass
    
    def push(self, x: int) -> None:
        pass
    
    def pop(self) -> int:
        pass
    
    def top(self) -> int:
        pass
    
    def empty(self) -> bool:
        pass

Solution

class MyStack:
    def __init__(self):
        self.queue = deque()
    
    def push(self, x: int) -> None:
        self.queue.append(x)
        # Rotate to make new element at front
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())
    
    def pop(self) -> int:
        return self.queue.popleft()
    
    def top(self) -> int:
        return self.queue[0]
    
    def empty(self) -> bool:
        return len(self.queue) == 0

Exercise 3: Simplify Path

def simplify_path(path: str) -> str:
    """
    Simplify Unix-style file path.
    "/a/./b/../../c/" -> "/c"
    """
    pass

Solution

def simplify_path(path: str) -> str:
    stack = []
    
    for part in path.split('/'):
        if part == '..':
            if stack:
                stack.pop()
        elif part and part != '.':
            stack.append(part)
    
    return '/' + '/'.join(stack)

---

🔑 Key Takeaways

1. Stack = LIFO; Queue = FIFO

2. Deque provides O(1) at both ends—use collections.deque

3. Monotonic stacks solve "next greater/smaller" problems

4. Priority queues (heaps) give O(log n) min/max access

5. BFS uses queues; DFS uses stacks

6. Two stacks can implement a queue, and vice versa

---

🚀 What's Next?

In the next article, we'll explore hash tables:

• Hash function design

• Collision resolution strategies

• Python dict internals

• Common hash table problems

Next: Article 7 - Hash Tables

---

📚 References

• Python collections.deque documentation

• Python heapq documentation

• "Cracking the Coding Interview" - Stacks and Queues