一、考点

常见数据结构

1） Array

• 数组，最简单而且应用最广泛的数据结构之一。

• 特性：使用连续的内存来存储、数组中的所有元素必须是相同的类型或类型的衍生（同质数数据结构）、元素可以通过下标直接访问。

2）LinkedList

• 链表，线性表的一种，最基本、最简单，也是最常用的数据结构。
• 特性：元素之间的关系是一对一的关系（除了第一个和最后一个元素，其他元素都是首尾相接）、顺序存储结构 和 链式存储结构 两种存储方式。

3）Stack

• 栈，和队列相似，一个带有数据存储特性的数据结构。
• 特性：存储数据是先进后出、栈只有一个出口，只能从栈顶部增加和移除元素。

4）Heap

• 堆，一般情况下，堆叫二叉堆，近似完全二叉树的数据结构。
• 特性：子节点的键值或者索引总是小于它的父节点、每个节点的左右子树又是一个二叉堆、根节点最大的堆叫最大堆或者大根堆、最小的叫最小堆或者小根堆。

5）list

• 线性表，由零个或多个数据元素组成的有限序列。
• 特性：线性表是一个序列、0个元素构成的线性表是空表、第一个元素无先驱、最后一个元素无后继、其他元素都只有一个先驱和后继、有长度，长度是元素个数，长度有限。

6）doubly-linked-list

• 双向链表
• 特性：每个元素都是一个对象，每个对象有一个关键字 key 和 两个指针 (next 和 prev，即向前移动和向后移动)。

7）queue

• 队列
• 特性：先进先出（FIFO）、并发中使用、可以安全将对象从一个任务传给另一个任务。

8）set

• 集合
• 特性：保存不重复元素。

9）map

• 字典
• 特性：关联数组、也可以被叫做字典或者键值对。

10）graph

• 图
• 特性：通常使用 邻接矩阵 和 邻接表 表示、前者易实现但是对于稀疏矩阵会浪费较多空间、后者使用链表的方式存储信息但是对于图搜索时间复杂度较高。

二、解题方法

先理解每种数据结构的特征，有时会遇到让用PHPdiam实现其中的数据结构，遇到此类题，先要理解该种数据结构的特征是什么，然后再实现，通常可以使用PHP的数组来模拟。

三、真题

用PHP实现一个双向队列

• 双向链表：从头部插入/移出，从尾部插入/移出。

• 用PHP模拟一个数组，在这里用到PHP关于数组的几个函数：

array_shift(); // 从头部移出
array_unshift(); // 从头部插入
array_pop(); // 从尾部移出
array_push(); // 从尾部插入

• 写四个方法，来实现
  • return array_shift();
  • return array_unshift();
  • return array_pop()：
  • return array_push()。