数据结构与算法：4栈和对列

我不是女神ヾ 2023-07-22 09:27 7阅读 0赞

### 文章目录 ###

*   *   *  栈
         *   *  栈的特性：
             *   *  后进者先出，先进者后出
                 *  Java数组实现一个固定大小的栈：
                 *  支持动态扩容的顺序栈
             *  栈的应用：
             *   *  函数调用栈：
                 *  表达式求值中的栈
                 *  栈在括号匹配中的应用
                 *  浏览器前进后退的实现
         *  队列
         *   *   *  循环对列
                 *  阻塞对列
                 *  线程池该如何处理？

### 栈 ###

#### 栈的特性： ####

##### 后进者先出，先进者后出 #####

栈就像摞在圆筒里的一摞盘子。放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。**后进者先出，先进者后出，这就是典型的“栈”结构。**

**栈是一种“操作受限”的线性表**，只允许在一端插入和删除数据。栈主要包含两个操作，入栈和出栈，也就是在栈顶插入一个数据和从栈顶删除一个数据。

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

用数组实现的栈，叫作**顺序栈**，用链表实现的栈，叫作**链式栈**。

##### Java数组实现一个固定大小的栈： #####

// 基于数组实现的顺序栈
    public class ArrayStack { 
      private String[] items;  // 数组
      private int count;       // 栈中元素个数
      private int n;           // 栈的大小
     
      // 初始化数组，申请一个大小为 n 的数组空间
      public ArrayStack(int n) { 
        this.items = new String[n];
        this.n = n;
        this.count = 0;
      }
     
      // 入栈操作
      public boolean push(String item) { 
        // 数组空间不够了，直接返回 false，入栈失败。
        if (count == n) return false;
        // 将 item 放到下标为 count 的位置，并且 count 加一
        items[count] = item;
        ++count;
        return true;
      }
      
      // 出栈操作
      public String pop() { 
        // 栈为空，则直接返回 null
        if (count == 0) return null;
        // 返回下标为 count-1 的数组元素，并且栈中元素个数 count 减一
        String tmp = items[count-1];
        --count;
        return tmp;
      }
    }

时间复杂度和空间复杂度都是 O(1)。注意：空间复杂度，存储数据需要一个大小为 n 的数组，并不是说空间复杂度就是 O(n)。因为，这 n 个空间是必须的，无法省掉。空间复杂度 特指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

##### 支持动态扩容的顺序栈 #####

原理就是数组扩容。对于入栈操作来说，最好情况时间复杂度是 O(1)，最坏情况时间复杂度是 O(n)。

大部分情况下，入栈操作的时间复杂度 O 都是 O(1)，只有在个别时刻（扩容）才会退化为 O(n)，所以把耗时多的入栈操作的时间均摊到其他入栈操作上，平均情况下的耗时就接近 O(1)。再次印证：均摊时间复杂度一般都等于最好情况时间复杂度。

#### 栈的应用： ####

##### 函数调用栈： #####

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

int main() { 
       int a = 1; 
       int ret = 0;
       int res = 0;
       ret = add(3, 5);
       res = a + ret;
       printf("%d", res);
       reuturn 0;
    }
     
    int add(int x, int y) { 
       int sum = 0;
       sum = x + y;
       return sum;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2libGFkZQ_size_16_color_FFFFFF_t_70_pic_center]

##### 表达式求值中的栈 #####

编译器如何利用栈来实现**表达式求值**。

编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。从左向右遍历表达式，当遇到数字，直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。

如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

例如3+5\*8-6 这个表达式的计算过程。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2libGFkZQ_size_16_color_FFFFFF_t_70_pic_center 1]

##### 栈在括号匹配中的应用 #####

假设表达式中只包含三种括号，圆括号 ()、方括号 \[\] 和花括号\{\}，并且它们可以任意嵌套。比如，\{\[\{\}\]\}或 \[\{()\}(\[\])\] 等都为合法格式，而\{\[\}()\] 或 \[(\{)\] 为不合法的格式。给出一个包含三种括号的表达式字符串，如何检查它是否合法呢？

public boolean isValid(String str) { 
        if (TextUtils.isEmpty(str)) { 
            return true;
        }
        Map<Character, Character> map = new HashMap<>(3);
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');
        Stack<Character> stack = new Stack<>();
        for (int i = 0, len = str.length(); i < len; i++) { 
            char c = str.charAt(i);
            //若为左括号，先入栈
            if (map.containsValue(c)) { 
                stack.push(c);
            } else if (map.containsKey(c)) { //若为右括号
                if(stack.isEmpty()){ //栈内无长度，即有右无左，则不合法
                    return false;
                }
                if(stack.peek()==map.get(c)){ //栈顶匹配，就弹出
                    stack.pop();
                }else { 
                    return false;
                }
            }
        }
        //遍历结束-栈空-则合法。
        return stack.isEmpty();
    }

##### 浏览器前进后退的实现 #####

使用两个栈，X 和 Y，把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈 X 中出栈，并将出栈的数据依次放入栈 Y。当点击前进按钮时，依次从栈 Y 中取出数据，放入栈 X 中。当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了。

次压入栈 X，当点击后退按钮时，再依次从栈 X 中出栈，并将出栈的数据依次放入栈 Y。当点击前进按钮时，依次从栈 Y 中取出数据，放入栈 X 中。当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了。

a、b、c依次入栈X，从c后退到b，此时从b新开页面d，则需要清空Y栈（c被清除）。从b按前进 只能是d，不再是c。

### 队列 ###

CPU 资源是有限的，任务的处理速度与线程个数并不是线性正相关。相反，过多的线程反而会导致 CPU 频繁切换，处理性能下降。所以，线程池的大小一般都是综合考虑要处理任务的特点和硬件环境，来事先设置的。

**当我们向固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线程池如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又是怎么实现的呢？**——队列（queue）。**先进者先出，这就是典型的“队列”**。队列跟栈一样，也是一种**操作受限的线性表数据结构**。比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。

与栈类似，数组实现的叫做顺序对列，链表实现的叫做链式队列。

队列比栈麻烦一点，需要两个指针，head和tail，固定长度数组，随着入队出队二者分别后移。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2libGFkZQ_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2libGFkZQ_size_16_color_FFFFFF_t_70_pic_center 3]  
怎么解决tail = 7 ,head>0 明明有空间，却无法入队的问题？ 数据搬移。

// 数组：items，数组大小：n
        private int n = 0;
        private String[] items = new String[n];
        // head 表示队头下标，tail 表示队尾下标
        private int head = 0;
        private int tail = 0;
        
        // 入队操作，将 item 放入队尾
        public boolean enqueue(String item) { 
            // tail == n 表示队列末尾没有空间了
            if (tail == n) { 
                // tail ==n && head==0，表示整个队列都占满了
                if (head == 0) return false;
                // 数据搬移
                for (int i = head; i < tail; ++i) { 
                    items[i - head] = items[i];
                }
                // 搬移完之后重置 head 和 tail
                tail -= head;
                head = 0;
            }
    
            items[tail] = item;
            ++tail;
            return true;
        }
    
        // 出队
        public String dequeue() { 
            // 如果 head == tail 表示队列为空
            if (head == tail) return null;
            String ret = items[head];
            ++head;
            return ret;
        }

当队列的 tail 指针移动到数组的最右边后，如果有新的数据入队，我们可以将 head 到 tail 之间的数据，整体搬移到数组中 0 到 tail-head 的位置。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2libGFkZQ_size_16_color_FFFFFF_t_70_pic_center 4]  
尽管这么做均摊复杂度O(1)。可否避免数据搬移呢？

##### 循环对列 #####

把上图7和0连接起来形成闭环。tail = 7时，直接存到0，这样就避免了数据搬移，代码实现上，关键点：**确定好队空和队满的判定条件**。对空条件依然是 head == tail，队满如何判断？

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dKvWgUx8-1586081793593)(C:\\Users\\lagou\\Desktop\\数据结构之美笔记\\循环队满.jpg)\]][img-dKvWgUx8-1586081793593_C_Users_lagou_Desktop_.jpg]

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 + 1) % n;
        return true;
      }
     
      // 出队
      public String dequeue() { 
        // 如果 head == tail 表示队列为空
        if (head == tail) return null;
        String ret = items[head];
        head = (head + 1) % n;
        return ret;
      }
    }

##### 阻塞对列 #####

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

可以使用阻塞队列，轻松实现一个“生产者 - 消费者模型”！

这种基于阻塞队列实现的“生产者 - 消费者模型”，可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。

而且不仅如此，基于阻塞队列，还可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。可以多配置几个“消费者”，来应对一个“生产者”。或者多个生产者供应一个消费者。

线程安全的队列我们叫作**并发队列**。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

##### 线程池该如何处理？ #####

我们一般有两种处理策略。第一种是非阻塞的处理方式，直接拒绝任务请求；另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。那如何存储排队的请求呢？

我们希望公平地处理每个排队的请求，先进者先服务，所以队列这种数据结构很适合来存储排队请求。我们前面说过，队列有基于链表和基于数组这两种实现方式。这两种实现方式对于排队请求又有什么区别呢？

基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。

而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。

除了前面讲到队列应用在线程池请求排队的场景之外，队列可以应用在任何有限资源池中，用于排队请求，比如数据库连接池等。**实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2libGFkZQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/7451b3aaef894fc983bf6296a3a80440.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2libGFkZQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230528/369359b70c844382a73d88feaa7fb697.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2libGFkZQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230528/2d227ac406c04a8d981b75102fab6fca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2libGFkZQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20230528/c5616c65d41e43c08eee1a9aa1d4e058.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2libGFkZQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20230528/0452543408254d3db156ebda5912d9c1.png
[img-dKvWgUx8-1586081793593_C_Users_lagou_Desktop_.jpg]: /images/20230528/0aa5a537f1c946029632f710733f95bf.png