数据结构-PHP通过 Array 类对象实现 "队列"
码农天地 -
这篇文章是展示如何使用PHP语言实现队列(Queue)这种数据结构，Queue也是一种线性结构，相比 Array 而言，Queue 对应的操作是 Array 的子集，只能从一端(队尾)添加元素，也只能从另外一端（队首）取出元素，是一种 First In First Out(FIFO)，即 先进先出 的结构。
<?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;
}
}这里是一个 队列 类，它的继承了数组类的方法，通过数组的增删查封装的一个 队列 类，实现了 入队(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();
}
}这里是 队列 类一个实现接口，里面定义了一些函数，这样 QueueStrcut 继承它之后，必须重构里面的所有方法：
<?php
interface Queue
{
public function enqueue($e): void;//入队
public function dequeue();//出队
public function getFront();//获取前端元素
public function getSize();//获取队列大小
public function isEmpty();//判断队列是否为空
}这是一个调用和打印输出结果的展示文件：
<?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>"; 特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。
php介绍
PHP即“超文本预处理器”，是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言，与C语言类似，是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习，使用广泛，主要适用于Web开发领域。
Tags 标签
php算法程序员扩展阅读
隐藏apache版本信息
2018-09-30 10:56:15 []CentOS 6.5安装php5.6
2018-09-30 11:36:53 []PHP版ZIP压缩解压类库
2018-12-22 13:11:00 []CentOS7.2安装 PHP7.3.4 操作详细教程
2020-06-28 19:09:43 []PHP 设置脚本超时时间、PHP脚本内存限制设置
2020-06-28 19:09:43 []PHP 函数filesize获取文件大小错误，一直不变
2020-06-28 19:09:43 []Linux php: command not found
2020-02-05 01:30:13 []php 缓冲区 buffer 原理
2020-06-28 19:09:43 []PHP中三种设置脚本最大执行时间的方法
2020-06-28 19:17:34 []加个好友，技术交流
