Module 3.3 ⏱ 35 min read ⚡ Advanced Linear Data Structures

Queues, Deques & Circular Buffers

Master First-In-First-Out architectures, implement queues using two stacks, and leverage double-ended queues for sliding window optimizations.

1. FIFO Mechanics & Implementation Strategies

A queue follows a First-In-First-Out (FIFO) access pattern where elements are inserted at the back (enqueue) and removed from the front (dequeue). While simple array-based implementations suffer from linear time removal shifts when popping from index zero, circular buffers and linked-list structures achieve true $O(1)$ constant-time operations.

Circular Buffers: Fixed-size arrays that wrap around using modulo arithmetic (`(head + 1) % capacity`), avoiding memory reallocation overhead and ensuring high cache efficiency in stream processing.

2. Queue Implementation Using Two Stacks

You can simulate a queue using two stacks: an `input` stack for incoming pushes and an `output` stack for pops and peeks. When the output stack is empty, elements from the input stack are transferred over, reversing their order and restoring correct FIFO behavior with amortized $O(1)$ complexity.

3. Sliding Window Maximum Using Deque

A double-ended queue (deque) allows efficient insertion and deletion at both ends in $O(1)$ time. By maintaining a monotonically decreasing deque of indices, you can solve sliding window maximum problems in linear $O(n)$ time by trimming out-of-bound elements and smaller redundant values.

// C++ Solution: Implement Queue using Two Stacks
#include <stack>

class MyQueue {
    std::stack<int> input;
    std::stack<int> output;
public:
    MyQueue() {}
    
    void push(int x) {
        input.push(x);
    }
    
    int pop() {
        peek();
        int val = output.top();
        output.pop();
        return val;
    }
    
    int peek() {
        if (output.empty()) {
            while (!input.empty()) {
                output.push(input.top());
                input.pop();
            }
        }
        return output.top();
    }
    
    bool empty() {
        return input.empty() && output.empty();
    }
};
            

# Python Solution: Implement Queue using Two Stacks
class MyQueue:
    def __init__(self):
        self.input = []
        self.output = []

    def push(self, x: int) -> None:
        self.input.append(x)

    def pop(self) -> int:
        self.peek()
        return self.output.pop()

    def peek(self) -> int:
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())
        return self.output[-1]

    def empty(self) -> bool:
        return not self.input and not self.output
            

// Java Solution: Implement Queue using Two Stacks
import java.util.Stack;

class MyQueue {
    private Stack<Integer> input;
    private Stack<Integer> output;

    public MyQueue() {
        input = new Stack<>();
        output = new Stack<>();
    }
    
    public void push(int x) {
        input.push(x);
    }
    
    public int pop() {
        peek();
        return output.pop();
    }
    
    public int peek() {
        if (output.isEmpty()) {
            while (!input.isEmpty()) {
                output.push(input.pop());
            }
        }
        return output.peek();
    }
    
    public boolean empty() {
        return input.isEmpty() && output.isEmpty();
    }
}
            

4. Homework & Quiz Overview

To lock in your mastery, complete the implementation exercises for building a queue using two stacks and designing a memory-efficient circular queue.

Quick Check: Test Your Intuition

What is the amortized time complexity of the `pop` or `peek` operation in a queue implemented using two stacks?