图解数据结构

1.栈

1.1栈的定义

栈（stack）是限定在表尾进行插入和删除的操作的线性表。

我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）,不包含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。

栈的插入操作，叫做进栈，也称压栈、入栈。

栈的删除操作，叫做出栈，也称弹栈。

1.2栈的顺序存储结构及实现

既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化。

用数组实现，下标为0的一端作为栈底比较好，因为首元素都存在栈底。

栈的结构定义：

定义一个top变量来指示栈顶元素在数组中的位置，若存储栈的长度为SackSize,则栈顶位置top必须小于SackSize。当栈存在一个元素时，top等于0，因此通常把空栈的判定条件为top=-1。

1.3栈的顺序存储结构——进栈操作

代码实现：

测试代码：

运行结果：

1.4栈的顺序存储结构——出栈操作

代码实现：

测试代码：

运行结果：

验证了栈是后进先出的结构。

1.5栈的链式存储结构及实现

栈的链式存储结构，简称为栈链。由于单链表有头指针，而栈顶指针也是必须的，那么便可以让它俩合二为一。以为就是说栈顶放在单链表的头部。

对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间。但是对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL。

栈链的结构代码如下：

1.6栈的链式存储结构——进栈操作

代码实现：

测试代码：

运行结果：

动画模拟：

1.7栈的链式存储结构——出栈操作

代码实现：

测试代码：

运行结果：

动画模拟：

2.队列

2.1队列的定义

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

2.2队列的顺序存储结构

我们假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组。

现在进行入队操作，就是在队尾插入一个元素，不需要移动任何元素，因此时间复杂度是O[1]。

出队操作是在队头，那么队列中所有的元素都要向前移动一个位置，确保下标为0的位置不为空，时间复杂度是O[n]，这是个问题。

如果不限定出队操作时所有的元素都要向前移动，也就是说队头不一定必须在下标为0 的位置，出队的性能就会大大增加。

但是这样又会出现另一个问题——假溢出，就是假设队列前面的位置是空着的，但是从队尾入队已经满了。

循环队列可以解决这一个问题，后面满了，就从头再开始，也就是头尾相接的循环，这种头尾相接的顺序存储结构称为循环队列。

但是循环队列还是会面临着数组溢出的问题。

2.3队列的链式存储结构及实现

队列的链式存储结构，其实就是线性表的单链表，只不过它能尾进头出而已，简称链队列。

队头指针指向链队列的头节点，而队尾指针指向终端节点：

空队列时都指向头节点：

链队列的结构如下：

2.4队列的链式存储结构——入队操作

入队操作，在队尾插入新元素。

代码实现：

测试代码：

运行结果：

动画模拟：

2.4队列的链式存储结构——出队操作

代码实现：

测试代码：

运行结果：

动画模拟：

-----END-----