关于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 (堆栈)

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 (队列)

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;