栈和队列

发表于

栈

:thinking:开篇思考:栈是如何实现浏览器的前进后退功能？

关于”栈”

栈结构

  • 后进者先出，先进者后出
  • 栈属于一种操作受限的线性表，只能允许在一端去插入和删除数据，所以当某个数据集合只涉及一端插入与删除数据，并且满足后进先出，先进后出的特性，就可以选择使用”栈”

关于”栈”的实现

  1. 使用链表实现的”栈”，称为链式栈
  2. 使用数组实现的”栈”，称为顺序栈

关于栈操作的时间与空间复杂度

时间复杂度：O(1)
  • 入栈与出栈只会涉及到个别数据的操作，所以时间复杂度为O(1)
空间复杂度：O(1)

支持动态扩容的顺序栈

在进行入栈操作时，当栈满时，就会扩容，这时会进行内存的申请与数据的搬移，这个时候入栈操作的时间复杂度就变成了O(n)

平均时间复杂度分析

  • 当栈大小为K，并且需要扩容时，将大小扩容为容量的2倍，这时需要做K个数据的搬移操作，然后入栈。但是在接下来的K-1次入栈操作都不需要重新申请内存与搬移数据，只需要简单的入栈即可，所以就可以将每次扩容栈的操作均摊成K-1次入栈，这-样每个入栈操作只需要一个数据的搬移和一个入栈操作。因此可以得出，入栈的均摊时间复杂度为O(1)

最坏情况O(n)，平均情况O(1)，最好情况O(1)

  • 一般情况下，均摊时间复杂度都等于最好时间复杂度

栈的应用

栈在函数调用中的应用

函数调用栈：操作系统为每个线程分配一块独立内存，而块内存就是按照”栈“结构来存储函数调用时的临时变量。每当进入一个函数时，就会将临时变量作为栈帧入栈，当被调用函数执行完后，返回之后，将这个函数对应的栈帧出栈。

栈在表达式求值中的应用

表达式求值：例如：29+30*2+29-19/3

  • 实现计算器功能，其实是通过两个栈，一个栈用来存储操作数，一个栈用来存储运算符。从左往右遍历表达式，当遇到数字将数字压入操作数栈，遇到运算符就与运算符的栈顶元素进行比较，如果比运算符栈顶元素优先级高，就直接入栈；如果优先级相同或者更低，就从运算符栈中去栈顶运算符，从操作数栈顶取两个操作数，然后进行计算，再将计算的结果重新压入操作数栈，继续比较运算符。

栈在括号匹配中应用

利用栈检查表达式中的括号是否匹配：合法格式：{[{([])}]} 非法格式：{[}()]

  • 从左向右依次遍历表达式，当遍历到左括号时，将其压入栈中，当遇到右括号时，从栈顶取出一个左括号。如果能够匹配，则继续扫描剩余字符串。如果在扫描过程中遇到不能匹配的右括号，或者栈中没有数据则说明格式不合法。

开篇解答：关于浏览器的前进，后退功能

​ :artificial_satellite: 这里使用两个栈，X与Y，我们分别浏览网页a，b，c；当第一次浏览a时，将a压入X栈，当点击后退键时，将a出栈，并将出栈的数据依次放入Y中，当我们依次点击a，b，c后，全部压入X中，当我们点击后退键时，会将X栈顶数据弹出，并压入到Y中，这样就实现了浏览器的前进后退功能。

​ :jack_o_lantern: 注意，如果你通过b网页跳转到d网页时，存在Y中的页面c就无法再通过前进，后退键重复查看了，这时就需要清空Y。

思考题

:thinking: 为什么函数调用要用“栈”来保存临时变量呢？其他数据结构不可以吗？
:thinking: JVM内存管理中有个“堆栈”概念。栈内存用来村春局部变量和方法调用，堆内存用来存储Java中的对象。那JVM里边的“栈”和这里的“栈”是一个概念吗，如果不是，那它为什么叫做“栈”呢？

队列

:thinking: 当我们向一个固定大小的线程池中请求一个线程时，如果线程中没有空闲资源了，这个时候线程池如何处理这个请求？是拒绝还是排队请求？各种策略又是怎么实现的？

关于队列

队列结构

  • 先进先出，后进后出
  • 与栈一样，是一种操作受限的线性表数据结构

顺序队列

链式队列

循环队列：可以解绝顺序队列中的数据搬移问题

  • 如何判断循环队列为null和队满的情况？

  • 如上图所示，tail=3，head=4，n=8，就有公式（3+1）%8=4。总结下来，当循环队列满时，就有（tail+1）/n=head，当队列满时，就会浪费一个数组的存储空间

    实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class CircularQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head 表示队头下标，tail 表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为 capacity 的数组
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 队列满了
    if ((tail + 1) % n == head) return false;
    items[tail] = item;
    // 更新tail
    tail = (tail + 1) % n;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果 head == tail 表示队列为空
    if (head == tail) return null;
    String ret = items[head];
    // 更新head
    head = (head + 1) % n;
    return ret;
  }
}

阻塞队列与并发队列

阻塞队列：在队列为空的时候，从队头取数据会被阻塞，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会阻塞，直到队列中有空闲的位置后再插入数据，然后再返回。

  • 可以使用阻塞队列实现“生产者-消费者模型”，在多线程模式下就会存在线程安全问题

并发队列：线程安全队列，利用CAS原子操作，实现高效的并发队列。

开篇解答

非阻塞式处理：直接拒绝任务请求

阻塞式处理：将请求排队，等到有空闲线程时，取出队列的请求继续处理

  • 基与链表的实现方式：可以支持无限排队的无界队列（unbounded queue），但是如果有过多请求排队等待时，就会导致响应时间过长。对于针对响应时间比较敏感的系统，基于链表实现的无线等待线程池不合适
  • 基于数组的实现方式：有界队列（bounded queue），队列的大小有限，当线程池中排队请求超过队列大小时，请求会被拒绝，适合对响应时间敏感的系统。

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

课后思考

:thinking: 除了线程池这种池结构会用到队列排队请求，还有哪些类似的池结构或者场景中会用到队列的排队请求呢？
  • Java concurrent并发包利用ArrayBlockingQueue来实现ReentrantLock