Stacks, Queues, and Deques: Sequential Access Data Structures

Stacks, queues, and deques enforce specific access patterns rather than allowing arbitrary inserts and removes. This constraint is a feature—by limiting what you can do, they make certain operations efficient and predictable. A stack follows Last-In-First-Out (LIFO), a queue follows First-In-First-Out (FIFO), and a deque allows insertion and removal from both ends.

Introduction

Stacks, queues, and deques are restricted-access data structures that enforce specific orderings on insertions and removals. A stack follows Last-In-First-Out (LIFO)—you can only access the most recently added element. A queue follows First-In-First-Out (FIFO)—you can only access the oldest element. A deque (double-ended queue) allows insertion and removal from both ends, combining capabilities of both structures.

These data structures are everywhere in software. Stacks power undo/redo systems, expression evaluation, and depth-first search. Queues handle task scheduling, breadth-first search, and message passing between services. Deques excel at sliding window problems and implementing efficient ring buffers. Understanding their implementation details matters because subtle choices—like whether to implement a stack with an array or linked list—affect cache performance and memory usage in production systems.

You’ll implement each structure from scratch, analyze time complexity of all operations, and see how Python’s collections.deque achieves O(1) performance at both ends through chunk-based memory management. We’ll cover balanced parentheses checking, shortest path finding, and the monotonic deque pattern for sliding window maximum problems.

Stack (LIFO - Last In First Out)

class Stack:
    """Array-based stack with O(1) push, pop, peek."""

    def __init__(self, capacity=10):
        self.capacity = capacity
        self.data = [None] * capacity
        self.size = 0

    def push(self, val):
        """O(1) push - amortized if resizing."""
        if self.size == self.capacity:
            self._resize()
        self.data[self.size] = val
        self.size += 1

    def pop(self):
        """O(1) pop."""
        if self.size == 0:
            raise IndexError("Stack underflow")
        val = self.data[self.size - 1]
        self.size -= 1
        return val

    def peek(self):
        """O(1) view top element."""
        if self.size == 0:
            raise IndexError("Stack is empty")
        return self.data[self.size - 1]

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

    def _resize(self):
        new_data = [None] * (self.capacity * 2)
        for i in range(self.size):
            new_data[i] = self.data[i]
        self.data = new_data
        self.capacity *= 2


class StackLinkedList:
    """Linked list based stack - O(1) all operations, no resize needed."""

    def __init__(self):
        self.top = None
        self.size = 0

    def push(self, val):
        self.top = ListNode(val, self.top)
        self.size += 1

    def pop(self):
        if not self.top:
            raise IndexError("Stack underflow")
        val = self.top.val
        self.top = self.top.next
        self.size -= 1
        return val

    def peek(self):
        if not self.top:
            raise IndexError("Stack is empty")
        return self.top.val

Queue (FIFO - First In First Out)

class Queue:
    """Array-based circular queue with O(1) enqueue and dequeue."""

    def __init__(self, capacity=10):
        self.capacity = capacity
        self.data = [None] * capacity
        self.front = 0
        self.rear = -1
        self.size = 0

    def enqueue(self, val):
        """O(1) add to rear."""
        if self.size == self.capacity:
            self._resize()
        self.rear = (self.rear + 1) % self.capacity
        self.data[self.rear] = val
        self.size += 1

    def dequeue(self):
        """O(1) remove from front."""
        if self.size == 0:
            raise IndexError("Queue underflow")
        val = self.data[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return val

    def peek(self):
        """O(1) view front element."""
        if self.size == 0:
            raise IndexError("Queue is empty")
        return self.data[self.front]

    def _resize(self):
        new_data = [None] * (self.capacity * 2)
        for i in range(self.size):
            new_data[i] = self.data[(self.front + i) % self.capacity]
        self.data = new_data
        self.front = 0
        self.rear = self.size - 1
        self.capacity *= 2


from collections import deque as PythonDeque

# For most use cases, Python's deque is optimal:
# O(1) append, appendleft, pop, popleft
queue = PythonDeque()
queue.append(1)      # enqueue
queue.append(2)      # enqueue
queue.popleft()      # dequeue -> returns 1

Deque (Double-Ended Queue)

class Deque:
    """Deque supporting O(1) insert/remove at both ends."""

    def __init__(self):
        self.front = []
        self.rear = []

    def push_front(self, val):
        """O(1) insert at front."""
        self.front.append(val)

    def push_back(self, val):
        """O(1) insert at rear."""
        self.rear.append(val)

    def pop_front(self):
        """O(1) remove from front."""
        if not self.front:
            if not self.rear:
                raise IndexError("Deque empty")
            # Move last element of rear to front
            self.rear.reverse()
            self.front = self.rear
            self.rear = []
        return self.front.pop()

    def pop_back(self):
        """O(1) remove from rear."""
        if not self.rear:
            if not self.front:
                raise IndexError("Deque empty")
            self.front.reverse()
            self.rear = self.front
            self.front = []
        return self.rear.pop()

    def peek_front(self):
        if self.front:
            return self.front[-1]
        if self.rear:
            return self.rear[0]
        raise IndexError("Deque empty")

    def peek_back(self):
        if self.rear:
            return self.rear[-1]
        if self.front:
            return self.front[0]
        raise IndexError("Deque empty")


# Sliding Window Maximum using deque
from collections import deque

def max_sliding_window(arr, k):
    """
    Find maximum in each sliding window of size k.
    O(n) time using monotonic deque.
    """
    if not arr or k == 0:
        return []

    result = []
    dq = deque()  # Stores indices

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

        # Remove indices whose values are smaller than current
        # (they'll never be the maximum in this window)
        while dq and arr[dq[-1]] <= arr[i]:
            dq.pop()

        dq.append(i)

        # Start recording results once we have a full window
        if i >= k - 1:
            result.append(arr[dq[0]])

    return result

Monotonic Deque Behavior

graph LR
    subgraph Window1["Window: [1, 3, 2]"]
        direction LR
        W1A["1"] --> W1B["3"] --> W1C["2"]
    end

    subgraph Deque1["Deque (decreasing)"]
        direction LR
        D1A["3"] --> D1B["2"]
    end

    Window1 --> Deque1
    Deque1 --> Max1["max = 3"]

For sliding window [1, 3, 2] with k=3: we add 1 (deque: [1]), then 3 (remove 1, deque: [3]), then 2 (deque: [3, 2]). The front always holds the maximum. When 3 exits the window, 2 becomes the new maximum.

Stack Applications

Problem	Stack Usage
Undo/Redo	Push operations, pop to undo
Expression evaluation	Parentheses matching, postfix conversion
Function call stack	Recursion, call hierarchy
DFS traversal	Explicit stack for iterative depth-first
Nearest greater element	Maintain decreasing stack while traversing

# Balanced parentheses check
def is_balanced(s):
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}

    for char in s:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()

    return len(stack) == 0


# Nearest greater element to the right
def nearest_greater_right(arr):
    result = [-1] * len(arr)
    stack = []  # Stack of indices with decreasing values

    for i in range(len(arr)):
        while stack and arr[stack[-1]] < arr[i]:
            result[stack.pop()] = arr[i]
        stack.append(i)

    return result

Queue Applications

Problem	Queue Usage
BFS traversal	FIFO order for level-order processing
Task scheduling	Round-robin, print queue
Buffering	Network packets, I/O operations
Message queues	Producer-consumer patterns

# BFS shortest path
from collections import deque

def bfs_shortest_path(graph, start, end):
    if start == end:
        return [start]

    queue = deque([(start, [start])])
    visited = {start}

    while queue:
        node, path = queue.popleft()

        for neighbor in graph[node]:
            if neighbor == end:
                return path + [neighbor]
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None  # No path exists

When to Use Each Structure

Structure	Access Pattern	Use When
Stack	LIFO	Undo, recursion, DFS, matching problems
Queue	FIFO	BFS, scheduling, breadth-first traversal
Deque	Both ends	Sliding window max, LRU cache, double-ended operations

Production Failure Scenarios and Mitigations

Stack Overflow from Unbounded Recursion

The call stack has a fixed size. Deep recursion on large inputs causes stack overflow. A recursive binary tree traversal on a tree with depth > 10,000 crashes the process.

Mitigation: Convert recursive algorithms to iterative using explicit stacks. Set a recursion depth guard that throws before overflowing. Profile stack usage under max expected input size.

Queue Overflow Under Load

Bounded queues reject new items when full. Under traffic spikes, producers block or drop messages. A print queue accepting jobs from 1,000 concurrent users with a 100-job capacity loses work.

Mitigation: Choose bounded vs unbounded based on requirements. Use dead-letter queues for rejected messages. Monitor queue utilization and scale consumers horizontally. Set alerts at 80% capacity.

Deadlock from Lock Ordering in Concurrent Queues

Multiple queues with shared resources create circular dependencies. Thread A holds Queue 1 and waits for Queue 2; Thread B holds Queue 2 and waits for Queue 1.

Mitigation: Enforce consistent lock ordering across all threads (always acquire Queue 1 before Queue 2). Use lock-free data structures when possible. Add deadlock detection in test environments.

Priority Inversion in Priority Queues

Low-priority tasks hold resources needed by high-priority tasks. A background sync task (low priority) holds a lock; a user-facing request (high priority) waits indefinitely.

Mitigation: Implement priority inheritance — temporarily elevate the low-priority task’s priority when it holds a contended lock. Use separate queues per priority level with weighted scheduling.

Trade-Off Table

Property	Stack	Queue	Deque
Push/Insert	O(1)	O(1)	O(1) at both ends
Pop/Remove	O(1)	O(1)	O(1) at both ends
Peek	O(1) front only	O(1) front only	O(1) at both ends
Search	O(n)	O(n)	O(n)
Memory Layout	Contiguous (array) or heap (linked list)	Contiguous via circular buffer	Usually linked chunks or two arrays
Thread Safety	Single-threaded unless synchronized	Single-threaded unless synchronized	Single-threaded unless synchronized
Best Use Case	Undo history, DFS, recursion	BFS, task scheduling, message passing	Sliding window, LRU cache, double-ended operations
Cache Performance	Excellent (contiguous)	Good (circular buffer)	Moderate (often linked)
Overflow Risk	Resize doubles memory	Resize or reject	Resize or reject

Observability Checklist

• Monitor queue depth in real-time; alert at 80% of capacity
• Track overflow/rejection counts per queue
• Measure enqueue and dequeue latency — spikes indicate backpressure
• Log stack trace on stack overflow exceptions with input size context
• Monitor consumer lag: time between enqueue and dequeue
• Track resize events — frequent resizes suggest capacity misprediction
• Alert on dequeue rate dropping to zero (consumer stall)
• Log dead-letter queue item counts for bounded queues
• Trace queue operations across service boundaries using correlation IDs
• Set up dashboards for depth, latency p50/p95/p99, and overflow rate

Security Notes

Stack Buffer Overflow Propagation

Malicious input oversized for a fixed stack buffer corrupts return addresses. Attackers inject shellcode into stack-allocated buffers. Production C/C++ services with manually managed buffers face this risk.

Mitigation: Use memory-safe languages or sanitizers (ASan, MSan). Enable stack canaries. Validate input length before write. Prefer heap allocation with bounds checking.

Resource Exhaustion via Unbounded Queues

An attacker floods a service with messages that accumulate in an unbounded queue. Memory grows until the process or container OOMs.

Mitigation: Use bounded queues with explicit overflow handling (reject, dead-letter, or block with timeout). Authenticate producers. Rate-limit ingress. Monitor memory per queue.

Denial of Service via Queue Flooding

High-volume producers overwhelm consumers. A single misconfigured client sends 10,000 messages/second; the consumer processes 100/second. Backpressure builds until service degrades for all users.

Mitigation: Enforce per-client rate limits at the queue ingress point. Use priority queues to ensure critical traffic gets through. Set consumer scaling policies that react to queue depth.

Race Conditions in Lock-Free Queue Implementations

Concurrent producers and consumers on a shared queue without proper synchronization cause torn reads/writes, item duplication, or use-after-free bugs. Lock-free does not mean wait-free.

Mitigation: Prefer battle-tested queue implementations (Java ConcurrentLinkedQueue, Go channels, Python queue module). Review memory ordering semantics. Stress-test with tools like ThreadSanitizer.

Quick Recap Checklist

• Stack: push/pop O(1), use for LIFO, DFS, undo operations
• Queue: enqueue/dequeue O(1), use for BFS, FIFO scheduling
• Deque: O(1) at both ends, use for sliding window problems
• Monotonic deque maintains decreasing/increasing values for efficiency
• Python’s collections.deque is optimized for both stack and queue operations

Deque Memory Model: Chunk-Based Implementation

While the two-array deque in the implementation section demonstrates the concept, production-grade deques (like Python’s collections.deque) use a chunk-based design for predictable O(1) performance at both ends.

# Conceptual model of a chunk-based deque
# Each block holds up to BLOCK_SIZE elements
BLOCK_SIZE = 64  # Typical value

class ChunkDeque:
    """Simplified conceptual model of Python's collections.deque."""

    def __init__(self):
        self._blocks = []       # List of fixed-size arrays
        self._left_block = 0    # Index of first block
        self._left_pos = 0      # Position within first block
        self._right_block = 0
        self._right_pos = -1
        self._size = 0

    def append(self, val):
        """Add to right end."""
        if self._right_pos == BLOCK_SIZE - 1:
            # Need a new block
            self._blocks.append([None] * BLOCK_SIZE)
            self._right_block += 1
            self._right_pos = 0
        else:
            self._right_pos += 1
        self._blocks[self._right_block][self._right_pos] = val
        self._size += 1

    def appendleft(self, val):
        """Add to left end."""
        if self._left_pos == 0:
            # Insert a block at the front
            self._blocks.insert(0, [None] * BLOCK_SIZE)
            self._right_block += 1  # Shift right index
            self._left_pos = 0
        else:
            self._left_pos -= 1
        self._blocks[self._left_block][self._left_pos] = val
        self._size += 1

    def pop(self):
        """Remove from right end."""
        val = self._blocks[self._right_block][self._right_pos]
        self._blocks[self._right_block][self._right_pos] = None
        self._size -= 1
        if self._right_pos == 0 and self._size > 0:
            # Block is empty, free it
            self._blocks.pop()
            self._right_block -= 1
            self._right_pos = BLOCK_SIZE - 1
        else:
            self._right_pos -= 1
        return val

    def popleft(self):
        """Remove from left end."""
        val = self._blocks[self._left_block][self._left_pos]
        self._blocks[self._left_block][self._left_pos] = None
        self._size -= 1
        self._left_pos += 1
        if self._left_pos == BLOCK_SIZE and self._size > 0:
            self._blocks.pop(0)
            self._right_block -= 1
            self._left_pos = 0
        return val

Key advantages of the chunk-based approach:

Property	Benefit
No full-structure resizing	Unlike dynamic arrays, never need to copy all elements
Bounded per-operation cost	Each append/pop touches at most one block
Cache-friendly	Elements within a block are contiguous
Memory efficient	Empty blocks are freed immediately
Predictable growth	Block allocation is O(1) amortized

This design is the reason Python’s collections.deque is the recommended choice for both stack and queue use cases in production Python code.

Interview Questions

Further Reading

Books

• Introduction to Algorithms (CLRS) — Chapters 10: “Elementary Data Structures” covers stacks, queues, linked lists, and their analysis.
• Algorithm Design Manual (Skiena) — Chapter 3: “Data Structures” includes practical applications and interview-style problems.
• Python Cookbook (Beazley & Jones) — Chapter 1 contains idiomatic deque patterns for real-world Python.

Online Resources

• CPython collections.deque source — Reference implementation in C, showing block management and growth strategy.
• Python’s deque documentation — Official API reference with usage examples.

Practice Problems by Topic

Topic	Problem	Platform
Stack	Valid Parentheses	LeetCode 20
Stack	Min Stack	LeetCode 155
Stack	Evaluate Reverse Polish Notation	LeetCode 150
Queue	Implement Stack Using Queues	LeetCode 225
Queue	Design Circular Queue	LeetCode 622
Deque	Sliding Window Maximum	LeetCode 239
Deque	Design Circular Deque	LeetCode 641
Monotonic Stack	Daily Temperatures	LeetCode 739
Monotonic Stack	Largest Rectangle in Histogram	LeetCode 84

Related Data Structures to Explore

• Priority Queue (Heap) — For tasks where items have urgency levels and the highest-priority item should be dequeued first.
• LRU Cache — Combines a doubly-linked list with a hash map; often implemented using a deque pattern.
• Monotonic Queue — A deque variant that maintains sorted order; used in sliding window and range query optimizations.
• Ring Buffer — A fixed-size circular queue used extensively in low-level systems (audio, networking, kernel I/O).

Conclusion