Detailed explanation of data structure implementation of PHP queue and stack

The queue follows the "first in, first out" principle and can be implemented using an array or linked list; the stack follows the "last in first out" principle and can also be implemented using an array or linked list. Specific implementation methods include: queue array implementation, queue linked list implementation, stack array implementation, and stack linked list implementation. Practical cases demonstrate the application of queues and stacks in message printing and array reversal.

Detailed explanation of the data structure implementation of PHP queue and stack

Queue and stack are a common linear data structure. They possess unique properties and are widely used in a variety of applications. This article will introduce the data structure implementation of queues and stacks in PHP and provide practical cases.

Queue

The queue follows the "first in, first out" (FIFO) principle. The oldest inserted element in the queue will be removed first. Queues can be implemented using arrays or linked lists.

Array implementation:

class Queue
{
    private $queue = [];

    public function enqueue($item)
    {
        $this->queue[] = $item;
    }

    public function dequeue()
    {
        if (empty($this->queue)) {
            throw new Exception("Queue is empty");
        }
        return array_shift($this->queue);
    }
}

Linked list implementation:

class Node
{
    public $data;
    public $next;

    public function __construct($data)
    {
        $this->data = $data;
        $this->next = null;
    }
}

class Queue
{
    private $head;
    private $tail;

    public function enqueue($item)
    {
        $node = new Node($item);
        if (empty($this->head)) {
            $this->head = $node;
            $this->tail = $node;
        } else {
            $this->tail->next = $node;
            $this->tail = $node;
        }
    }

    public function dequeue()
    {
        if (empty($this->head)) {
            throw new Exception("Queue is empty");
        }
        $item = $this->head->data;
        $this->head = $this->head->next;
        if (empty($this->head)) {
            $this->tail = null;
        }
        return $item;
    }
}

Practical case: Use queue printing Message

$queue = new Queue();
$queue->enqueue("Hello");
$queue->enqueue("World");
while (!$queue->isEmpty()) {
    echo $queue->dequeue() . "<br>";
}

Stack

The stack follows the "last in, first out" (LIFO) principle. The last inserted element in the stack will be removed first. Stacks can be implemented using arrays or linked lists.

Array implementation:

class Stack
{
    private $stack = [];

    public function push($item)
    {
        $this->stack[] = $item;
    }

    public function pop()
    {
        if (empty($this->stack)) {
            throw new Exception("Stack is empty");
        }
        return array_pop($this->stack);
    }
}

Linked list implementation:

class Node
{
    public $data;
    public $next;

    public function __construct($data)
    {
        $this->data = $data;
        $this->next = null;
    }
}

class Stack
{
    private $top;

    public function push($item)
    {
        $node = new Node($item);
        $node->next = $this->top;
        $this->top = $node;
    }

    public function pop()
    {
        if (empty($this->top)) {
            throw new Exception("Stack is empty");
        }
        $item = $this->top->data;
        $this->top = $this->top->next;
        return $item;
    }
}

Practical case: Use stack reverse order An array

$stack = new Stack();
$array = [1, 2, 3, 4, 5];
foreach ($array as $item) {
    $stack->push($item);
}
$reversedArray = [];
while (!$stack->isEmpty()) {
    $reversedArray[] = $stack->pop();
}
print_r($reversedArray);

The above is the detailed content of Detailed explanation of data structure implementation of PHP queue and stack. For more information, please follow other related articles on the PHP Chinese website!