Stacks and Queues: Fundamental Abstract Data Types

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

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.