关于php:SPL-数据结构双向链表堆栈队列

在 php 中，spl 扩大提供了一些罕用的数据结构供咱们应用。只是因为 php 中存在万能的数组，所以对于数据结构的意识以及相干数据结构的应用会比拟少。以下整顿梳理了 spl 中提供的一些数据结构以及应用阐明，使咱们对于相干数据结构以及根本应用有肯定认知。
这一篇中将介绍双向链表，堆栈和队列。

以下为百度百科中对于双向链表的解释


双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，别离指向间接后继和间接前驱。所以，从双向链表中的任意一个结点开始，都能够很不便地拜访它的前驱结点和后继结点。个别咱们都结构双向循环链表。

php spl 中，提供了 SplDoublyLinkedList 用于实现双向列表，上面代码列出一些罕用的性能

$list = new SplDoublyLinkedList();
$list->push('a');
$list->push('b');
$list->push('c');
$list->push('d');

echo "链表长度：" . count($list) . PHP_EOL;

$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO);
echo "FIFO :\n";
for ($list->rewind(); $list->valid(); $list->next()) {echo $list->current() . "\n";
}

$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO);
echo "FILO :\n";
for ($list->rewind(); $list->valid(); $list->next()) {echo $list->current() . "\n";
}

// 双向链表罕用办法
echo "链表头部元素：" . $list->bottom() . PHP_EOL;
echo "链表尾部元素：" . $list->pop() . PHP_EOL;

$list->push("在链表尾部 push 一个元素");

// 从链表尾部 pop 出一个元素
echo "pop 链表中的元素：" . $list->pop() . PHP_EOL;

// 在链表头部插入元素
$list->unshift("first");
// 在链表头部删除元素
$list->shift();

// 以后节点元素为 null
echo "以后节点元素：" . $list->current() . PHP_EOL;
$list->rewind();    // 重置以后指针 重置到链表尾部
echo "重置后节点元素:" . $list->current() . PHP_EOL;

// 留神 pre next 获取到的值 和 以后的 linkList mode 关联
$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO);
$list->prev();
echo "以后节点元素：" . $list->current() . PHP_EOL;
$list->next();
echo "以后节点元素：" . $list->current() . PHP_EOL;

Stack 是一种常见的数据结构。特点是只能在一端 (称为栈顶 top) 对数据进行插入和删除。也就是咱们常见的 LIFO(Last In First Out)。spl 中提供 SplStack 类实现堆栈。SplStack 基于双向列表实现，继承自 SplDoublyLinkedList 类

$obj = new SplStack();
$obj->push(1);
$obj->push('two');
$obj->push(3);

echo "pop:" . $obj->pop() . PHP_EOL;
echo "pop:" . $obj->pop() . PHP_EOL;
echo "pop:" . $obj->pop() . PHP_EOL;

// 持续 pop 会报错
//echo "pop:".$obj->pop().PHP_EOL;

$obj->push(111);
$obj->push('222');
$obj->push(333);

$obj->rewind();
while ($obj->valid()) {echo $obj->current(), "\n";
    $obj->next();}

Queue 应该是咱们开发中应用最多的一种数据结构。咱们所所熟知的音讯队列往往就是基于队列实现。队列有时候也被称为线性表。最大的特点就是先进先出 FIFO. spl 中的 SplQueue 类就是实现队列这种数据结构。底层同样是基于双向列表实现。

$obj = new SplQueue();
$obj->enqueue('a');
$obj->enqueue('b');
$obj->enqueue('c');

// 出队
echo "出队：" . $obj->dequeue() . PHP_EOL;
echo "出队：" . $obj->dequeue() . PHP_EOL;
echo "出队：" . $obj->dequeue() . PHP_EOL;

// 当队列中存在元素在出队时会报错 RuntimeException:
//echo "出队：".$obj->dequeue().PHP_EOL;

关于php:SPL-数据结构双向链表堆栈队列

双向链表

Stack (堆栈)

Queue (队列)