「数据结构与算法」栈（Stack）与 队列（Queue）

Posted on | In

栈（Stack）和队列（Queue），严格意义上来说，也属于线性表，是一种操作受限的线性表数据结构。
使用栈结构存储数据，讲究“先进后出”，即最先进栈的数据，最后出栈；
使用队列存储数据，讲究“先进先出”，即最先进队列的数据，也最先出队列。

1. 栈

栈（Stack）是一种只能从一端存取数据且遵循“先进后出”原则（First In Last Out，简称FILO）的线性存储结构。
通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。
栈只支持两个基本操作：入栈push()和出栈pop()。

1.1 栈的实现

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

1.2 栈的应用

  1. 栈在函数调用中的应用
    • 操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将其中的临时变量作为栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。
  2. 栈在表达式求值中的应用（比如：34+13*9+44-12/3）
    • 利用两个栈，其中一个用来保存操作数，另一个用来保存运算符。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较，若比运算符栈顶元素优先级高，就将当前运算符压入栈，若比运算符栈顶元素的优先级低或者相同，从运算符栈中取出栈顶运算符，从操作数栈顶取出2个操作数，然后进行计算，把计算完的结果压入操作数栈，继续比较。
  3. 栈在括号匹配中的应用（比如：{}{[()]()}）
    • 用栈保存为匹配的左括号，从左到右一次扫描字符串，当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号，如果能匹配上，则继续扫描剩下的字符串。如果扫描过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。
    • 当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明未匹配的左括号为非法格式。
  4. 实现浏览器的前进后退功能
    • 我们使用两个栈X和Y，我们把首次浏览的页面依次压如栈X，当点击后退按钮时，再依次从栈X中出栈，并将出栈的数据一次放入Y栈。当点击前进按钮时，我们依次从栈Y中取出数据，放入栈X中。当栈X中没有数据时，说明没有页面可以继续后退浏览了。当Y栈没有数据，那就说明没有页面可以点击前进浏览了。

1.3 为什么函数调用要用“栈”来保存临时变量？

  • 因为函数调用的执行顺序符合后进者先出，先进者后出的特点。比如函数中的局部变量的生命周期的长短是先定义的生命周期长，后定义的生命周期短；还有函数中调用函数也是这样，先开始执行的函数只有等到内部调用的其他函数执行完毕，该函数才能执行结束。
  • 正是由于函数调用的这些特点，根据数据结构是特定应用场景的抽象的原则，我们优先考虑栈结构。

2. 队列

队列（queue）是一种遵循“先进先出”原则（First In First Out，简称FIFO）的线性存储结构。
与栈结构不同的是，队列的两端都“开口”，要求数据只能从一端进，从另一端出；通常，称进数据的一端为“队尾”，出数据的一端为“队头”。
最基本的操作也是两个：入队enqueue()，放一个数据到队列尾部；出队dequeue()，从队列头部取一个元素。
所以，队列跟栈一样，也是一种操作受限的线性表数据结构。

2.1 队列的实现

  • 队列存储结构的实现有以下两种方式：
    • 顺序队列：在顺序表的基础上实现的队列结构。
    • 链队列：在链表的基础上实现的队列结构。
  • 跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
  • 基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。
  • 而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。

2.2 队列的应用

  1. 循环队列
    • 循环队列还是基于数组实现的。原本数组是有头有尾的，是一条直线。我们把首尾相连，扳成了一个环，形成逻辑上的环状空间。
  2. 阻塞队列
    • 在队列的基础上增加阻塞操作，就成了阻塞队列。
    • 阻塞队列就是在队列为空的时候，从队头取数据会被阻塞，因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后在返回。
    • 从上面的定义可以看出这就是一个“生产者-消费者模型”。这种基于阻塞队列实现的“生产者-消费者模型”可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了，这时生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续生产。不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据处理效率，比如配置几个消费者，来应对一个生产者。
  3. 并发队列
    • 在多线程的情况下，会有多个线程同时操作队列，这时就会存在线程安全问题。能够有效解决线程安全问题的队列就称为并发队列。
    • 并发队列简单的实现就是在enqueue()、dequeue()方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或取操作。
    • 实际上，基于数组的循环队列利用CAS原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
  4. 线程池资源枯竭是的处理
    • 在资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。