Explication détaillée de la mise en œuvre de la structure de données de la file d'attente et de la pile PHP

La file d'attente suit le principe « premier entré, premier sorti » et peut être implémentée à l'aide d'un tableau ou d'une liste chaînée ; la pile suit le principe « dernier entré, premier sorti » et peut également être implémentée à l'aide d'un tableau ou d'une liste chaînée. Les procédés de mise en œuvre spécifiques comprennent : la mise en œuvre d'un tableau de files d'attente, la mise en œuvre d'une liste chaînée de file d'attente, la mise en œuvre d'un tableau de pile et la mise en œuvre d'une liste chaînée de pile. Des cas pratiques démontrent l'application des files d'attente et des piles dans l'impression de messages et l'inversion de tableaux.

Explication détaillée de l'implémentation de la structure de données de la file d'attente et de la pile PHP

La file d'attente et la pile sont une structure de données linéaire commune. Ils possèdent des propriétés uniques et sont largement utilisés dans diverses applications. Cet article présentera l'implémentation de la structure de données des files d'attente et des piles en PHP et fournira des cas pratiques.

Queue

Queue suit le principe du "premier entré, premier sorti" (FIFO). L'élément inséré le plus ancien dans la file d'attente sera supprimé en premier. Les files d'attente peuvent être implémentées à l'aide de tableaux ou de listes chaînées.

Implémentation du tableau :

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);
    }
}

Implémentation de la liste chaînée :

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;
    }
}

Cas pratique : Utilisation de la file d'attente pour imprimer les messages

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

Stack

La pile suit le principe "dernier entré, premier sorti" (LIFO) . Le dernier élément inséré dans la pile sera supprimé en premier. Les piles peuvent être implémentées à l'aide de tableaux ou de listes chaînées.

Implémentation d'un tableau :

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);
    }
}

Implémentation d'une liste chaînée :

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;
    }
}

Cas pratique : Utiliser la pile pour inverser un tableau

$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);

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!