PHP常见的5种数据结构

PHP有着非常强大的SPL标准库，从而提供了一套标准的数据结构，分别有数组、链表、栈、队列、递归、最大堆、最小堆、优先列队、阵列、映射。

chu  shu

数组(Array)是一种线性表的数据结构，它用一段连续的内存空间，来存储具有相同类型的值。但是由于在PHP的底层定义中，数组是通过散列表实现的，所以这段定义并不适用。PHP的数组可以存储任意数据类型的数据，所以相对于Java来说效率较高。在Java的数组中，每次定义都要先声明属于组的类型，在查找数组时，效率是O(1)，但是在插入和删除时，算法复杂度是O(n),因为在插入操作时，要先找到插入的位置，然后将该位置及往后的元素都往后移一位。删除同理。但是PHP却不受此约束。

栈是一种特殊的线性表，因为它限定只能在线性表的一端进行插入或删除元素(即进栈和出栈)。并且满足先进后出的特点。我们把允许插入和删除的一端叫做栈顶，另一个端叫做栈底，不含任何数据的栈叫做空栈。栈支持通过数组/链表实现，通过数组实现的通常叫做顺序栈，通过链表实现的叫做链栈。

递归，简单来讲就是在函数定义中调用函数自身，将一个大的问题拆分成多个小问题，逐一击破后最后归并结果。判断一个问题是否可以通过递归来解决，主要看它是否满足以下三个条件： 

a、一个问题的解可以分解为几个子问题的解

b、这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样

c、存在递归终止条件 

（注意:递归一定要有终止条件，否则会导致函数被无限调用最终致使内存溢出）。

队列和栈类似，队列也是一种特殊的线性表结构，只不过队列是在一端插入，另一端删除，就跟我们平常排队一样，从队尾入队，在队头出去，所以队列的特性是先入先出，允许插入的一端叫队尾，允许删除的一端叫队头。队列也可以通过数组和链表实现，通过数组实现的叫顺序队列，通过链表实现的叫做链式队列，栈只需要一个栈顶指针就可以了，因为只允许在栈顶插入删除，但是队列需要两个指针，一个指向队头，一个指向队尾。

链表和数组不同，链表并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，一般节点有两个属性（data和next）。

链表有多种类型，最简单的是单链表：

单链表：是最原始的链表。单链表有两个节点比较特殊，头结点和尾节点。头结点记录链表的基地址，通过它可以遍历得到整条链表。尾节点的指针不是指向节点，而是指向空地址NUll，表示这是最后一个节点。单向链表插入和删除的时间复杂度是O(1),而查询的时间复杂度是O(n)

疑问：当进行插入和删除操作时要先查询相应节点，查询的时间复杂度是O(n),为什么插入和删除的的复杂度是O(1)呢？可以将插入删除看作是单纯的插入删除，不包含查询在里面。当做两个不同的操作来看待。

在单链表的基础上扩展有了循环链表，循环链表是将尾节点的next指向了头结点，从而实现了收尾相连。可以解决(约瑟夫环)问题。

双向链表：与单向链表的区别是除了有一个指向下一个节点的指针外，还有一个用于指向上一个节点的指针。从而实现通过O(1)复杂度找到上一个节点。使得双向链表在插入删除比单向链表更高效。以删除为例，在删除节点时，我们还要获取其前驱节点，让前驱节点的指针指向被删除节点的下一个节点。在单向链表中，获取前驱节点的复杂度是O(n)，但是双向链表O(1)直接获取前驱节点。所以双向链表插入和删除的时间复杂度才是真正的O(1)。

最后一种就是双向循环链表，就是双向链表和单向链表的结合。

MEET/YOUSELF