PHP标准库(SPL)学习之数据结构总结与回顾

SPL的数据结构总共有9个类,分别如下

SplDoublyLinkedList — spl双向链表
SplStack — spl栈
SplQueue — spl队列
SplHeap — spl堆
SplMaxHeap — spl最大堆
SplMinHeap — spl最小堆
SplPriorityQueue — spl优先队列
SplFixedArray — spl固定数组
SplObjectStorage — spl对象存储

SplDoublyLinkedList

双向链表是一种重要的线性存储结构，对于双向链表中的每个节点，不仅仅存储自己的信息，还要保存前驱和后继节点的地址。

在使用中需要注意迭代方向与迭代行为.

/**
 * 迭代方向
 * SplDoublyLinkedList::IT_MODE_FIFO First_Input_First_Output 先入先出(队列)
 * SplDoublyLinkedList::IT_MODE_LIFO Last_Input_First_Output 后入先出(堆栈)
 *
 * 迭代行为
 * SplDoublyLinkedList::IT_MODE_DELETE 迭代后删除数据
 * SplDoublyLinkedList::IT_MODE_KEEP  迭代后保存数据
 */
$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO);

SplStack

栈(Stack)是一种特殊的线性表，因为它只能在线性表的一端进行插入或删除元素(即进栈和出栈)

在使用中需要注意,如果设置迭代的模式不存在,代码会抛出RuntimeException异常,所以注意捕获异常.

try{
    /**
     * 可见栈和双链表的区别就是IteratorMode改变了而已，栈的IteratorMode只能为：
     * （1）SplDoublyLinkedList::IT_MODE_LIFO | SplDoublyLinkedList::IT_MODE_KEEP  （默认值,迭代后数据保存）
     * （2）SplDoublyLinkedList::IT_MODE_LIFO | SplDoublyLinkedList::IT_MODE_DELETE （迭代后数据删除）
     */
    $stack->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO | SplDoublyLinkedList::IT_MODE_KEEP );
}catch (RuntimeException $e){
    echo $e->getMessage().PHP_EOL;
}

SplQueue

队列的特性是先进先出(FIFO)。

$queue->enqueue('a'); //入列
$queue->enqueue('a'); //出列

SplPriorityQueue

优先队列是基于堆实现的。

/**
 * 设置元素出队模式
 * SplPriorityQueue::EXTR_DATA 仅提取值
 * SplPriorityQueue::EXTR_PRIORITY 仅提取优先级
 * SplPriorityQueue::EXTR_BOTH 提取数组包含值和优先级
 */
$pq->setExtractFlags(SplPriorityQueue::EXTR_DATA);

SplHeap

堆(Heap)就是为了实现优先队列而设计的一种数据结构，它是通过构造二叉堆(二叉树的一种)实现。根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。二叉堆还常用于排序(堆排序)。

其中SplHeap是一个抽象类,需要写一个继承SplHeap的类并实现compare()方法,其中SplHeap的compare()方法就可以实现最大堆最小堆

SplMaxHeap,SplMinHeap

SplMaxHeap类提供堆的主要功能，保持最大值在顶部。最小堆则相反

SplFixedArray

SplFixedArray类提供了数组的主要功能。 SplFixedArray和普通PHP数组之间的主要区别是SplFixedArray是固定长度的，并且只允许范围内的整数作为索引。优点是它允许更快的阵列实现。

SplObjectStorage

SplObjectStorage类提供从对象到数据的映射，或通过忽略数据来提供对象集。在涉及需要唯一地标识对象的许多情况下，这种双重目的是有用的。

下面是这9个SPL数据结构的练习代码

<?php
//SplDoublyLinkedList
$doublylinkedlist = new SplDoublyLinkedList();

$doublylinkedlist->push([['sadasdas'], ['asdasd']]);

$doublylinkedlist->push([['sadasdas'], ['asdasd']]);

$doublylinkedlist->rewind();
$doublylinkedlist->current();


$doublylinkedlist->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO);

$doublylinkedlist->rewind();

while($doublylinkedlist->valid()) {
    $doublylinkedlist->current();
    $doublylinkedlist->next();
}

//SplHeap
class MyHeap extends SplHeap
{
    public function compare($value1, $value2)
    {
        return ($value1 - $value2);
    }
}
$heap = new MyHeap();
$heap->insert(600);
$heap->insert(800);
$heap->insert(100);
$heap->insert(400);

$heap->rewind();
while ($heap->valid())
{
    $heap->current();
    $heap->next();
}

//SplMaxHeap
$maxHeap = new SplMaxHeap();
$maxHeap->insert(600);
$maxHeap->insert(800);
$maxHeap->insert(100);
$maxHeap->insert(400);
$maxHeap->rewind();
while ($maxHeap->valid()) {
    $maxHeap->current();
    $maxHeap->next();
}

//SplMinHeap
$minHeap = new SplMinHeap();
$minHeap->insert(600);
$minHeap->insert(100);
$minHeap->insert(800);
$minHeap->insert(400);
$minHeap->rewind();
while ($minHeap->valid()) {
    $minHeap->current();
    $minHeap->next();
}

//SplQueue
$queue = new SplQueue();
$queue->enqueue(['sdfsdfsd11111']);
$queue->enqueue(['sdfsdfsd22222']);
$queue->enqueue(['sdfsdfsd33333']);
$queue->dequeue();

$queue->setIteratorMode(SplDoublyLinkedList::IT_MODE_DELETE);

$queue->rewind();
while ($queue->valid()) {
    $queue->current();
    $queue->next();
}

//SplStack
$stack = new SplStack();
$stack->push(['dsfsdf1111']);
$stack->push(['dsfsdf2222']);
$stack->push(['dsfsdf3333']);
$stack->push(['dsfsdf4444']);

$stack->rewind();
while ($stack->valid()){
    $stack->current();
    $stack->next();
}

//SplFixedArray
$fixedArray = new SplFixedArray(100);
$fixedArray->offsetSet(0, ['sdfsdfsdfsd']);
$fixedArray->offsetGet(0);

$fixedArray->setSize(2);

$fixedArray->rewind();
while ($fixedArray->valid()){
    $fixedArray->current();
    $fixedArray->next();
}

//SplObjectStorage
$objectStorage = new SplObjectStorage();
$objectStorage->attach($fixedArray);
$objectStorage->attach($maxHeap);
$objectStorage->attach($minHeap);

$objectStorage->detach($fixedArray);
var_dump($objectStorage->contains($fixedArray));

//SplPriorityQueue
$priorityQueue = new SplPriorityQueue();
$priorityQueue->insert(12121, 1);
$priorityQueue->insert(12122, 2);
$priorityQueue->insert(12123, 3);

$priorityQueue->rewind();
while ($priorityQueue->valid()){
    echo $priorityQueue->current().PHP_EOL;
    $priorityQueue->next();
}

Ta的专栏