数据结构与算法（2）——栈和队列

前言：题图无关，只是好看，接下来就来复习一下栈和队列的相关知识

前序文章：

数据结构与算法(1)——数组与链表（https://www.jianshu.com/p/7b93b3570875）

栈

什么是栈

栈是一种用于存储数据的简单数据结构（与链表类似）。数据入栈的次序是栈的关键。可以把一桶桶装的薯片看作是一个栈的例子，当薯片做好之后，它们会依次被添加到桶里，每一片都会是当前的最上面一片，而每次我们取的时候也是取的最上面的那一片，规定你不能破坏桶也不能把底部捅穿，所以第一个放入桶的薯片只能最后一个从桶里取出；

定义：栈（Stack）是一个有序线性表，只能在表的一端（称为栈顶，top）执行插入和删除操作。最后插入的元素将第一个被删除，所以栈也称为后进先出（Last In First Out，LIFO）或先进后出（First In Last Out）线性表；

两个改变栈的操作都有专用名称。一个称为入栈（push），表示在栈中插入一个元素；另一个称为出栈（pop），表示从栈中删除一个元素。试图对一个空栈执行栈操作称为下溢（underflow）；试图对一个满栈执行栈操作称为溢出（overflow）。通常，溢出和下溢均认为是异常；

栈的应用

无处不在的Undo操作（撤销）；

程序调用的系统栈；

括号/符号匹配；

等等等等….

栈抽象数据类型

下面给出栈抽象数据类型中的操作，为了简单起见，假设数据类型为整型；

栈的主要操作

：将data（数据）插入栈；

：删除并返回最后一个插入栈的元素；

栈的辅助操作

：返回最后一个插入栈的元素，但不删除；

：返回存储在栈中元素的个数；

：判断栈中是否有元素；

：判断栈中是否存满元素；

动态数组简单实现栈结构

我们结合之前创建的Array类，我们能够很好的创建属于我们自己的动态数组实现的栈结构，对于用户来说，我们只需要完成我们的相关操作，并且知道我能够不断地往里添加元素而不出错就行了，所以我们先来定义一个通用的栈接口：

然后我们往之前的动态数组中添加两个用户友好的方法：

然后实现自己的动态数组为底层的栈结构就轻松多了：

简单复杂度分析

从代码中可以看出，几乎所有的时间复杂度都为O(1)级别，比较特别的是和操作可能涉及到底层数组的扩容或缩容的操作，所以是均摊下来的复杂度；

队列

什么是队列

队列是一种用于存储数据的数据结构（与链表和栈类似），数据到达的次序是队列的关键；在日常生活中队列是指从序列的开始按照顺序等待服务的一队人或物；

定义：队列是一种只能在一端插入（队尾），在另一端删除（队首）的有序线性表。队列中第一个插入的元素也是第一个被删除的元素，所以队列是一种先进先出（FIFO,First In First Out）或后进后出（LiLO,Last In Last Out）线性表；

与栈类似，两个改变队列的操作各有专用名称；在队列中插入一个元素，称为入队（EnQueue），从队列中删除一个元素，称为出队（DeQueue）；试图对一个空队列执行出队操作称为下溢（underflow），试图对一个满队列执行入队操作称为溢出（overflow）；通常认为溢出和下溢是异常。

队列的一些应用举例

操作系统根据（具有相同优先级的）任务到达的顺序调度任务（例如打印队列）；

模拟现实世界中的队列，如售票柜台前的队伍，或者任何需要先来先服务的场景；

多道程序设计；

异步数据传输（文件输入输出、管道、套接字）；

等等等等…

动态数组简单实现队列结构

我们仍然定义一个Queue接口来说明我们队列中常用的一些方法：

借由我们之前自己实现的动态数组，那么我们的队列就很简单了：

简单的复杂度分析

：O(1)（均摊）

：O(n)

：O(1)

：O(1)

：O(1)

实现自己的循环队列

循环队列的实现其实就是维护了一个front和一个tail分别指向头和尾，然后需要特别注意的呢是判定队满和队空的条件：

队空：，这没啥好说的；

队满：，这里其实是有意浪费了一个空间，不然就判定不了到底是队空还是队满了，因为条件都一样…

简单复杂度分析

：O(1)（均摊）

：O(1)（均摊）

：O(1)

：O(1)

：O(1)

简单数组队列和循环队列的简单比较

我们来简单对比一下两个队列的性能吧，这里直接上代码：

我这里的测试结果是这样的，大家也就可见一斑啦：

其实ArrayQueue慢主要是因为出栈时每次都需要把整个结构往前挪一下

简单总结

栈和队列的应用远不止上面学习到的那些，实现方式也有很多种，现在也只是暂时学到这里，通过刷LeetCode也加深了我对于这两种数据结构的认识，不过自己还需要去熟悉了解一下计算机系统关于栈的应用这方面的知识，因为栈这种结构本身就很适合用来保存CPU现场之类的工作，还是抓紧时间吧，过两天还考试，这两天就先复习啦…