Current Location: Home> Latest Articles> Efficient Queue Implementation in PHP Using Two Stacks

Efficient Queue Implementation in PHP Using Two Stacks

gitbox 2025-07-23

Introduction

A queue is a commonly used data structure that follows the First-In-First-Out (FIFO) principle. Although PHP arrays can be used to implement queues, direct manipulation of arrays can lead to inefficiencies. This article explains how to use two stack structures to implement efficient queue operations and improve performance.

Basic Concept of Stack

A stack is a Last-In-First-Out (LIFO) data structure, with two main operations: push (to add an element) and pop (to remove the top element). Pushing adds an element to the top of the stack, while popping removes the top element.

Idea of Implementing Queue Using Two Stacks

Using two stacks, one as the input stack for enqueue operations and the other as the output stack for dequeue operations. When the output stack is empty, elements from the input stack are popped one by one and pushed into the output stack, achieving the FIFO behavior of a queue.

Enqueue Operation

The enqueue operation is straightforward: simply push the element onto the input stack.

class Queue {
    private $inputStack = [];
    private $outputStack = [];

    public function enqueue($item) {
        array_push($this->inputStack, $item);
    }
}

Dequeue Operation

The dequeue operation first checks if the output stack is empty. If it is, all elements from the input stack are popped and pushed into the output stack. Then, elements are popped from the output stack. If the output stack is not empty, elements are popped directly from it.

public function dequeue() {
    if (empty($this->outputStack)) {
        while (!empty($this->inputStack)) {
            array_push($this->outputStack, array_pop($this->inputStack));
        }
    }
    if (!empty($this->outputStack)) {
        return array_pop($this->outputStack);
    }
    return null;
}

Example Code

Here is a sample code demonstrating basic queue operations using two stacks:

$queue = new Queue();
$queue->enqueue(1);
$queue->enqueue(2);
$queue->enqueue(3);
echo $queue->dequeue(); // Outputs 1
echo $queue->dequeue(); // Outputs 2
echo $queue->dequeue(); // Outputs 3

Conclusion

Using two stacks to implement a queue can effectively avoid the performance issues caused by frequent array element shifting. The enqueue operation is simple and efficient, while the dequeue operation ensures the FIFO property by transferring elements between stacks. Although it requires extra stack space, this method significantly improves the execution efficiency of queue operations, especially when handling large amounts of data.

Related