共计 4425 个字符，预计需要花费 12 分钟才能阅读完成。
这篇文章是展现如何应用 PHP 语言实现 队列 (Queue) 这种数据结构，Queue也是一种线性构造，相比 Array 而言，Queue 对应的操作是 Array 的子集，只能从一端 (队尾) 增加元素，也只能从另外一端（队首）取出元素，是一种 First In First Out(FIFO)，即 先进先出 的构造。
1.ArrayStruct 类
<?php
/**
* 数据结构 - 数组的实现
* Class ArrayStruct
*/
class ArrayStruct
{
// 用于存放数据
protected $data = [];
// 用于标记数组大小
protected $size = 0;
// 用于标记数组的容量
protected $capacity = 10;
/**
* 构造函数 定义数组容量
* ArrayStruct constructor.
* @param int $capacity
*/
public function __construct(int $capacity = 10) {$this->capacity = $capacity;}
/**
* 获取数组元素个数
* @return int
*/
public function getSize(): int {return $this->size;}
/**
* 获取数组的容量
* @return int
*/
public function getCapacity(): int {return $this->capacity;}
/**
* 判断数组是否为空
* @return bool
*/
public function isEmpty(): bool {return $this->size == 0;}
/**
* 向数组指定地位插入元素
* @param int $index
* @param $e
* @throws Exception
*/
public function add(int $index, $e): void {if ($this->size == $this->capacity) {$this->resize(2); // 扩充到原来的 2 倍
}
if ($index < 0 || $index > $this->size) {
echo "增加地位超出数组大小";
exit;
}
// 为了不便了解，[1,2,4,5,6], 假如 $index = 3; $e = 100, 插入之后[1,2,4,100,5,6]
for ($i = $this->size; $i >= $index; $i--) {$this->data[$i] = $this->data[$i - 1];
}
$this->data[$index] = $e;
$this->size++;
}
/**
* 向数组开端增加元素
* @param $e
* @throws Exception
*/
public function addLast($e): void {$this->add($this->size, $e);
}
/**
* 向数组结尾插入元素
* @param $e
* @throws Exception
*/
public function addFirst($e): void {$this->add(0, $e);
}
/**
* 获取 index 地位数组元素
* @param int $index
* @return mixed
*/
public function get(int $index) {if ($index < 0 || $index > $this->size) {
echo "index 值超出元素的地位范畴，";
exit;
}
return $this->data[$index];
}
/**
* 获取数组开端元素
* @return mixed
*/
public function getLast() {return $this->get($this->size - 1);
}
/**
* 获取数组结尾元素
* @return mixed
*/
public function getFirst() {return $this->get(0);
}
/**
* 判断数组中是否存在某个元素
* @param $e
* @return bool
*/
public function contains($e): bool {for ($i = 1; $i < $this->size; $i++) {if ($this->data[$i] == $e) {return true;}
}
return false;
}
/**
* 查某个元素在数组的地位索引值，若不存在则返回 -1
* @param $e
* @return int
*/
public function find($e): int {for ($i = 0; $i < $this->size; $i++) {if ($this->data[$i] == $e) {return $i;}
}
return -1;
}
/**
* 删除数组指定地位元素，返回删除元素的值
* @param $index
* @return mixed
*/
public function remove($index) {if ($index < 0 || $index > $this->size) {
echo "index 值超出元素的地位范畴，";
exit;
}
$e = $this->data[$index];
for ($i = $index; $i < $this->size - 1; $i++) {$this->data[$i] = $this->data[$i + 1];
}
$this->size--;
$this->data[$this->size] = null; //loitering objects ! =memory
/** 若以后数组大小，小于容量的一半，则重新分配一半的数组空间大小 **/
if ($this->size <= $this->capacity / 4 && $this->capacity % 2 == 0) {$this->resize(0.5);
}
return $e;
}
/**
* 删除数组首个元素，返回删除元素的值
*/
public function removeFirst() {return $this->remove(0);
}
/**
* 删除数组首个元素，返回删除元素的值
*/
public function removeLast() {return $this->remove($this->size - 1);
}
/**
* 删除数组中特定元素
* @param $e
*/
public function removeElement($e) {for ($i = 0; $i < $this->size; $i++) {if ($this->data[$i] == $e) {$this->remove($i);
$this->removeElement($e);
break;
}
}
}
/**
* 数组扩容，若是其余语言，如 JAVA 这里须要从新开拓空间
* @param $factor
*/
protected function resize($factor) {$this->capacity = $factor * $this->capacity;}
/**
* 将数组转化为字符串
* @return string
*/
public function toString(): string {
$str = "[";
for ($i = 0; $i < $this->size; $i++) {$value_str = is_numeric($this->data[$i]) ? $this->data[$i] : "'{$this->data[$i]}'";
$str .= $i . "=>" . $value_str . ",";
}
$str = trim($str, ",");
$str .= "]";
return $str;
}
}Tips：这是一个封装好的数组类，可用于数组的插入、删除、查找。
2.QueueStruct 类
这里是一个 队列 类，它的继承了数组类的办法，通过数组的增删查封装的一个 队列 类，实现了 入队 (enqueue)、 出队 (dequeue)、 查看队首(getFront)：
<?php
require 'ArrayStruct.php';
require 'Queue.php';
class QueueStruct implements Queue
{
protected $array = null;
public function __construct(int $capacity = 0) {$this->array = new ArrayStruct($capacity);
}
/**
* 入队
* @param $e
* @throws Exception
*/
public function enqueue($e): void {$this->array->addLast($e);
}
/**
* 出队
*/
public function dequeue() {return $this->array->removeFirst();
}
/**
* 获取队前元素
*/
public function getFront() {return $this->array->getFirst();
}
/**
* 获取队列大小
* @return int
*/
public function getSize(): int {return $this->array->getSize();
}
/**
* 判断队列是否为空
* @return bool
*/
public function isEmpty(): bool {return $this->array->isEmpty();
}
/**
* 打印队列内容
* @return bool
*/
public function toString(): string {return $this->array->toString();
}
}3.interface Queue
这里是 队列 类一个实现接口，外面定义了一些函数，这样 QueueStrcut 继承它之后，必须重构外面的所有办法：
<?php
interface Queue
{public function enqueue($e): void;// 入队
public function dequeue();// 出队
public function getFront();// 获取前端元素
public function getSize();// 获取队列大小
public function isEmpty();// 判断队列是否为空}4.output_queue.php
这是一个调用和打印输出后果的展现文件：
<?php
require 'QueueStruct.php';
$queue = new QueueStruct();
$queue->enqueue("rr");
$queue->enqueue("tt");
$queue->enqueue("yy");
$queue->enqueue("uu");
$queue->enqueue("ii");
$queue->enqueue("oo");
echo $queue->toString(); // 打印 [0 => 'rr',1 => 'tt',2 => 'yy',3 => 'uu',4 => 'ii',5 => 'oo']
echo "<br>";
echo $queue->dequeue(); // 出队 打印 rr
echo "<br>";
echo $queue->dequeue(); // 出队 打印 tt
echo "<br>";
正文完
