数据结构总结3：栈和队列

后续会有补充和更改 

栈和队列

栈和队列也属于线性表 

栈

一种特殊的线性表，只允许在固定的一端进行插入和删除元素。该端称为栈顶，另一端称为栈底。

栈中的数据遵循后进先出（LIFO）的原则

压栈/进栈/入栈：数据插入到栈中的操作。入数据在栈顶

出栈：栈中数据的删除操作。出数据也在栈顶 

栈的实现

 栈的实现一般可以使用数组或者链表来实现，相对而言数组的结构实现更优一些，因为栈的插入和删除都是在栈顶，也就是数组的尾部，而数组在尾上插入数据的代价比较小。

如果要用链式栈，用头部做栈顶更优一些

那么栈的实现是用数组好还是链表好呢？

用数组更好，因为栈基本上就是尾插尾删，而数组尾插尾删的效率很高，链表也是可以的，而且链表需要用双向的，如果用单向的话，尾插好说，但是尾删不好用

实际中一般不用定长的静态栈结构，所以主要学会实现动态增长的栈

栈不要轻易遍历，因为它是一边进一边出，遍历栈意味着把栈腾空

队列

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。队列具有先进先出（FIFO）的特性

队列和栈的某些性质相反

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

队列的实现：

        队列也可以用数组和链表的结构实现，使用链表的结构实现更优一些，如果用数组，想队头出数据只能将其覆盖，效率比较低。

        另外，实际中我们有时还会使用一种队列叫循环队列。如生产者消费者模型中可能就会使用循环队列。环形队列可以使用数组实现，也可以使用环形链表实现。

队列的应用场景：

        1.排队。要保持绝对公平性的地方，用它。

        2.广度优先遍历。BFS、DFS。