数据结构与算法：栈和队列

栈

定义：

1、 后进先出，先进后出，这就是典型的“栈”结构
2、栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。

使用场景：

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，这时我们就应该首选“栈”这种数据结构。

实现：

栈既可以用数组来实现，也可以用链表来实现。
用数组实现的栈，我们叫作顺序栈，
用链表实现的栈，我们叫作链式栈。

时间和空间复杂度：

不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是 O(1)。
不管是顺序栈还是链式栈，我们存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。

实际应用

1、浏览器的前进后退为典型的栈
两个栈来实现
2、表达式求值。
（编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。高级就入栈，等于或小于，出栈计算）
3、栈在括号匹配中的应用
（我们用栈来保存未匹配的左括号，从左到右依次扫描字符串
当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式。）

WeChat9dcfe8fd5999b2548faa24ee9e3eb6fa.png

队列

定义：

先进者先出，这就是典型的“队列”。
也是一种操作受限的线性表数据结构。

使用场景：

对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。

实现

它既可以用数组来实现，也可以用链表来实现。
用数组实现的叫顺序队列，
用链表实现的叫链式队列

实际应用

阻塞队列、并发队列，底层都还是队列这种数据结构，只不过在之上附加了很多其他功能。阻塞队列就是入队、出队操作可以阻塞，并发队列就是队列的操作多线程安全。