Stacks and Queues

Introduction

Stacks and queues are fundamental data structures that restrict how elements are added and removed. These constraints make them perfect for specific problems and are building blocks for more complex algorithms.

Learning Objectives

By the end of this reading, you will be able to:

• Implement stacks and queues using arrays and linked lists
• Understand LIFO (Last-In-First-Out) and FIFO (First-In-First-Out)
• Apply stacks and queues to solve problems
• Recognize when to use each structure

1. Stacks

A stack is a LIFO (Last-In-First-Out) data structure. The last element added is the first to be removed.

Think of a stack of plates - you add and remove from the top.

Core Operations

Stack Using Array

class ArrayStack:
    def __init__(self):
        self._data = []

    def push(self, value):
        self._data.append(value)

    def pop(self):
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        return self._data.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("Peek from empty stack")
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

    def __len__(self):
        return len(self._data)

Stack Using Linked List

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedStack:
    def __init__(self):
        self._top = None
        self._size = 0

    def push(self, value):
        new_node = Node(value)
        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")
        value = self._top.data
        self._top = self._top.next
        self._size -= 1
        return value

    def peek(self):
        if self.is_empty():
            raise IndexError("Peek from empty stack")
        return self._top.data

    def is_empty(self):
        return self._top is None

    def __len__(self):
        return self._size

Using Python's Built-in

# Python list works as a stack
stack = []
stack.append(1)   # push
stack.append(2)
stack.append(3)
stack.pop()       # 3
stack[-1]         # peek: 2

# collections.deque is slightly more efficient
from collections import deque
stack = deque()
stack.append(1)   # push
stack.pop()       # pop

2. Stack Applications

Balanced Parentheses

def is_balanced(s):
    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

print(is_balanced("({[]})"))  # True
print(is_balanced("([)]"))    # False
print(is_balanced("(("))      # False

Evaluate Postfix Expression

def eval_postfix(expression):
    """
    Evaluate postfix (reverse Polish notation)
    "3 4 + 2 *" = (3 + 4) * 2 = 14
    """
    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(int(a / b))

    return stack.pop()

print(eval_postfix("3 4 + 2 *"))  # 14

Infix to Postfix Conversion

def infix_to_postfix(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    output = []
    stack = []

    for token in expression.split():
        if token.isalnum():  # Operand
            output.append(token)
        elif token == '(':
            stack.append(token)
        elif token == ')':
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()  # Remove '('
        else:  # Operator
            while (stack and stack[-1] != '(' and
                   stack[-1] in precedence and
                   precedence[stack[-1]] >= precedence[token]):
                output.append(stack.pop())
            stack.append(token)

    while stack:
        output.append(stack.pop())

    return ' '.join(output)

print(infix_to_postfix("3 + 4 * 2"))  # "3 4 2 * +"

Function Call Stack

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

# Call stack visualization for factorial(4):
# factorial(4)
#   factorial(3)
#     factorial(2)
#       factorial(1) -> returns 1
#     -> returns 2 * 1 = 2
#   -> returns 3 * 2 = 6
# -> returns 4 * 6 = 24

Undo Functionality

class TextEditor:
    def __init__(self):
        self.text = ""
        self.history = []

    def type(self, chars):
        self.history.append(self.text)  # Save state
        self.text += chars

    def undo(self):
        if self.history:
            self.text = self.history.pop()

editor = TextEditor()
editor.type("Hello")
editor.type(" World")
print(editor.text)  # "Hello World"
editor.undo()
print(editor.text)  # "Hello"

3. Queues

A queue is a FIFO (First-In-First-Out) data structure. The first element added is the first to be removed.

Think of a line at a store - first come, first served.

Core Operations

Queue Using Linked List

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedQueue:
    def __init__(self):
        self.front = None
        self.rear = None
        self._size = 0

    def enqueue(self, value):
        new_node = Node(value)
        self._size += 1

        if self.rear is None:
            self.front = self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Dequeue from empty queue")

        value = self.front.data
        self.front = self.front.next
        self._size -= 1

        if self.front is None:
            self.rear = None

        return value

    def peek(self):
        if self.is_empty():
            raise IndexError("Peek from empty queue")
        return self.front.data

    def is_empty(self):
        return self.front is None

    def __len__(self):
        return self._size

Queue Using Circular Array

class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = [None] * capacity
        self.front = 0
        self.rear = 0
        self._size = 0

    def enqueue(self, value):
        if self._size == self.capacity:
            raise IndexError("Queue is full")

        self.data[self.rear] = value
        self.rear = (self.rear + 1) % self.capacity
        self._size += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Dequeue from empty queue")

        value = self.data[self.front]
        self.data[self.front] = None
        self.front = (self.front + 1) % self.capacity
        self._size -= 1
        return value

    def peek(self):
        if self.is_empty():
            raise IndexError("Peek from empty queue")
        return self.data[self.front]

    def is_empty(self):
        return self._size == 0

    def is_full(self):
        return self._size == self.capacity

    def __len__(self):
        return self._size

Using Python's Built-in

from collections import deque

# deque is optimized for both ends
queue = deque()
queue.append(1)     # enqueue
queue.append(2)
queue.append(3)
queue.popleft()     # dequeue: 1
queue[0]            # peek: 2

# For thread-safe queue
from queue import Queue
q = Queue()
q.put(1)            # enqueue
q.get()             # dequeue (blocks if empty)

4. Queue Applications

Breadth-First Search

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return result

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

Level Order Tree Traversal

def level_order(root):
    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

Task Scheduling (Round Robin)

def round_robin(processes, time_quantum):
    """
    Simulate round-robin CPU scheduling
    processes: list of (name, burst_time)
    """
    queue = deque(processes)
    time = 0
    log = []

    while queue:
        name, remaining = queue.popleft()
        run_time = min(remaining, time_quantum)

        log.append(f"t={time}: Process {name} runs for {run_time}")
        time += run_time
        remaining -= run_time

        if remaining > 0:
            queue.append((name, remaining))
        else:
            log.append(f"t={time}: Process {name} completed")

    return log

processes = [('A', 10), ('B', 5), ('C', 8)]
for entry in round_robin(processes, 3):
    print(entry)

5. Deque (Double-Ended Queue)

A deque supports insertion and removal at both ends.

class Deque:
    def __init__(self):
        self._data = []

    def add_front(self, value):
        self._data.insert(0, value)  # O(n) with array

    def add_rear(self, value):
        self._data.append(value)     # O(1)

    def remove_front(self):
        if self.is_empty():
            raise IndexError("Remove from empty deque")
        return self._data.pop(0)     # O(n) with array

    def remove_rear(self):
        if self.is_empty():
            raise IndexError("Remove from empty deque")
        return self._data.pop()      # O(1)

    def peek_front(self):
        if self.is_empty():
            raise IndexError("Peek from empty deque")
        return self._data[0]

    def peek_rear(self):
        if self.is_empty():
            raise IndexError("Peek from empty deque")
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

Note: Python's collections.deque is implemented as a doubly-linked list of blocks, giving O(1) for all operations.

Sliding Window Maximum

from collections import deque

def max_sliding_window(nums, k):
    """
    Find max element in each sliding window of size k.
    Uses monotonic deque: stores indices of potentially maximum elements.
    """
    result = []
    dq = deque()  # Store indices

    for i in range(len(nums)):
        # Remove indices outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove smaller elements (they'll never be max)
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        dq.append(i)

        # Add to result once we have a full window
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

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

6. Priority Queue (Preview)

A priority queue dequeues elements by priority, not insertion order.

import heapq

# Min-heap (lowest priority = highest urgency)
pq = []
heapq.heappush(pq, (3, "Low priority"))
heapq.heappush(pq, (1, "High priority"))
heapq.heappush(pq, (2, "Medium priority"))

while pq:
    priority, task = heapq.heappop(pq)
    print(f"Processing: {task}")

# Output:
# Processing: High priority
# Processing: Medium priority
# Processing: Low priority

Full coverage in Heaps and Priority Queues chapter.

7. Stack vs Queue Comparison

8. Common Problems

Implement Queue Using Stacks

class QueueUsingStacks:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def enqueue(self, value):
        self.stack_in.append(value)

    def dequeue(self):
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())

        if not self.stack_out:
            raise IndexError("Dequeue from empty queue")

        return self.stack_out.pop()

# Amortized O(1) per operation

Implement Stack Using Queues

from collections import deque

class StackUsingQueues:
    def __init__(self):
        self.queue = deque()

    def push(self, value):
        self.queue.append(value)
        # Rotate so new element is at front
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())

    def pop(self):
        if not self.queue:
            raise IndexError("Pop from empty stack")
        return self.queue.popleft()

    def peek(self):
        if not self.queue:
            raise IndexError("Peek from empty stack")
        return self.queue[0]

Min Stack (O(1) getMin)

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, value):
        self.stack.append(value)
        if not self.min_stack or value <= self.min_stack[-1]:
            self.min_stack.append(value)

    def pop(self):
        value = self.stack.pop()
        if value == self.min_stack[-1]:
            self.min_stack.pop()
        return value

    def get_min(self):
        return self.min_stack[-1]

Valid Stack Sequences

def validate_stack_sequences(pushed, popped):
    """
    Can we get 'popped' sequence by pushing 'pushed' and popping?
    """
    stack = []
    j = 0

    for x in pushed:
        stack.append(x)
        while stack and stack[-1] == popped[j]:
            stack.pop()
            j += 1

    return len(stack) == 0

print(validate_stack_sequences([1,2,3,4,5], [4,5,3,2,1]))  # True
print(validate_stack_sequences([1,2,3,4,5], [4,3,5,1,2]))  # False

Exercises

Basic

1. Implement a stack that also tracks the minimum element in O(1) time.

2. Use a stack to reverse a string.

3. Implement a queue using a circular array.

Intermediate

4. Given a string of '(' and ')', return the minimum number of parentheses to add to make it valid.

5. Implement a "Recent Counter" that counts requests in the last 3000 milliseconds using a queue.

6. Evaluate the expression: "( ( 1 + 2 ) * ( 3 + 4 ) )"

Advanced

7. Design a stack that supports push, pop, and retrieving the maximum element, all in O(1).

8. Implement a queue that supports enqueue, dequeue, and getMin in O(1).

9. Given daily temperatures, for each day find how many days until a warmer day (use a stack).

Summary

• Stack: LIFO - push/pop from same end
• Queue: FIFO - enqueue at rear, dequeue from front
• Both support O(1) core operations when implemented well
• Deque: Supports both stack and queue operations
• Stacks are used for: parsing, recursion, undo, DFS
• Queues are used for: scheduling, BFS, buffering
• Can implement one using the other (with some overhead)

Next Reading

Hash Tables →