Implementing a Queue Using Two Stacks in PHP

Queues and stacks are fundamental linear data structures; a queue follows FIFO (first‑in‑first‑out) while a stack follows LIFO (last‑in‑first‑out). The article first defines the basic operations of each: enqueue, dequeue, and peek for queues; push, pop, and peek for stacks.

Two‑Stack Queue Principle

The core idea is to use two stacks (S1 and S2). Enqueue pushes the new element onto S1. Dequeue checks S2: if S2 is non‑empty, pop from S2; otherwise, transfer all elements from S1 to S2 (reversing order) and then pop from S2. This ensures FIFO behavior.

PHP Implementation

class QueueWithTwoStacks {
    private $stack1;
    private $stack2;

    public function __construct() {
        $this->stack1 = new SplStack();
        $this->stack2 = new SplStack();
    }

    // enqueue operation
    public function enqueue($item) {
        $this->stack1->push($item);
    }

    // dequeue operation
    public function dequeue() {
        if ($this->stack2->isEmpty()) {
            while (! $this->stack1->isEmpty()) {
                $this->stack2->push($this->stack1->pop());
            }
        }
        if ($this->stack2->isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return $this->stack2->pop();
    }

    // peek front element
    public function peek() {
        if ($this->stack2->isEmpty()) {
            while (! $this->stack1->isEmpty()) {
                $this->stack2->push($this->stack1->pop());
            }
        }
        if ($this->stack2->isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return $this->stack2->top();
    }

    // check if queue is empty
    public function isEmpty() {
        return $this->stack1->isEmpty() && $this->stack2->isEmpty();
    }
}

Usage Example

$queue = new QueueWithTwoStacks();
$queue->enqueue(1);
$queue->enqueue(2);
$queue->enqueue(3);

echo $queue->dequeue(); // outputs 1
echo $queue->dequeue(); // outputs 2

$queue->enqueue(4);

echo $queue->dequeue(); // outputs 3
echo $queue->dequeue(); // outputs 4

Complexity Analysis

Enqueue: O(1) – direct push onto S1.

Dequeue: Best case O(1) when S2 is non‑empty; worst case O(n) when elements must be moved from S1 to S2.

Amortized cost: Each element is moved at most twice (once to S1, once to S2), giving an amortized O(1) per operation.

Practical Applications

Browser history navigation (back/forward).

Undo/redo functionality in text editors.

Task scheduling in thread pools where order matters.

Variants and Extensions

Using two queues to implement a stack (reverse concept).

Min‑queue: augmenting the structure to retrieve the minimum element in O(1).

Concurrent versions for multi‑threaded environments.

Conclusion

Implementing a queue with two stacks is a classic algorithmic exercise that deepens understanding of data‑structure flexibility. While PHP offers native queue classes (e.g., SplQueue), this custom implementation provides insight into underlying mechanics and can be adapted for specialized behavior.