队列遵循“先进先出”原则,可使用数组或链表实现;堆栈遵循“后进先出”原则,同样可使用数组或链表实现。具体实现方式包括:队列数组实现、队列链表实现、堆栈数组实现、堆栈链表实现。实战案例演示了队列和堆栈在消息打印和数组逆序中的应用。
队列和堆栈是一种常见的线性数据结构。它们拥有独特的特性,并在各种应用中广泛使用。本文将介绍 PHP 中队列和堆栈的数据结构实现,并提供实战案例。
队列遵循“先进先出”(FIFO)原则。队列中最早插入的元素将首先被移除。可以使用数组或链表来实现队列。
数组实现:
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); } }
链表实现:
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; } }
实战案例: 使用队列打印消息
$queue = new Queue(); $queue->enqueue("Hello"); $queue->enqueue("World"); while (!$queue->isEmpty()) { echo $queue->dequeue() . "<br>"; }
堆栈遵循“后进先出”(LIFO)原则。堆栈中最后插入的元素将首先被移除。可以使用数组或链表来实现堆栈。
数组实现:
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); } }
链表实现:
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; } }
实战案例: 使用堆栈逆序一个数组
$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);
以上是PHP 队列和堆栈的数据结构实现详解的详细内容。更多信息请关注PHP中文网其他相关文章!