每日一课 | 栈与队列的定义

一时失言乱红尘 2022-10-19 05:40 176阅读 0赞

![fdca50b309bf073eb9b44a635e6adc5d.png][]

**04.**

栈与队列的定义

大家好，我是营长，上期给大家分享——[ 如何用双向链表实现LRU淘汰机制算法][LRU]

本期分享内容：栈与队列的定义

本期邀请的是**春晨溅雨·4位算法工程师**为我们分享《**数据结构算法面试全解析**》专栏。

**数据结构算法面试**

**栈与队列的定义**

栈和队列有相似点也有不同点，相似点在于他们都是线性数据结构，不同点是一个先进后出，一个是先进先出，本质上就是逆序操作与顺序操作。这两种数据结构在企业的面试中经常出现，不仅有考察相关代码的实现，也会考察这两种数据结构具体的应用。这部分内容将会带大家梳理、掌握栈与队列这两个数据结构。

### **1. 栈** ###

#### **1.1 定义** ####

要明白栈的概念，就需要从“栈”这个字开始解读，《说文》中解释到：栈，棚也。所以本质上，栈就是用来存储货物的地方。引申到计算机科学中，栈的就是暂时存储数据的地方。栈作为一种只能在其中一头插入删除操作的特殊线性表，严格遵循数据先入后出的原则进行操作。基于这样的原则，我们可以很好地理解栈在进行数据的读取、输出的过程中，不需要更改栈底的指针。

栈是一种先进后出（LIFO，Last In First Out）的数据结构，这个数据结构非常好理解就类似于压入子弹的枪膛。因此可以得到栈的一个定义：限定仅在表尾进行插入和删除操作的线性表。这里需要特别注意的是，栈属于线性表。栈可以通过数组或者链表来实现，根据实现的数据结构不同，分别称为顺序栈和链式栈。由此可以引出一些有关栈的概念。

*  栈顶（top）：允许进行数据插入和删除的一端
 *  栈底（bottom）：栈顶的另一端
 *  出栈（pop，弹栈）：删除栈顶的元素
 *  入栈（push，压栈）：在栈顶插入新的元素
 *  空栈：栈中元素个数为零

![3685669f5704f150d07f2de066861235.png][]

在计算机系统中，栈起到了一个跨媒介的交互的作用，也就是存在于 CPU 与内存之间，一般被称之为动态内存区。CPU 运行程序之前，从系统中获取应用程序规定的栈入口线性地读取执行指令，在计算机科学中有一个非常经典的词来形容：管道（pipeline）。除此之外，程序的运行过程本质上就是一个压栈的过程，因此栈还可以用来存储调用函数时产生的断点信息。在操作系统中，压栈操作使得栈顶地址减小，弹栈操作使得栈顶在内存中的地址变大。栈在程序的运行中有着举足轻重的作用。最重要的是栈保存了一个函数调用时所需要的维护信息，这常常称之为堆栈帧，其中包含了程序运行所需的以下信息：

*  函数的返回地址和参数
 *  临时变量：包括函数的非静态局部变量以及编译器自动生成的其他临时变量

#### **1.2 Java Stack 类** ####

介绍完栈的基本概念，现在我们引入 Java 中栈的类，方便同学在后面看由栈实现的相关代码。栈在 Java 中是 Vector 的一个子类，并且这个类实现了标准的后进先出的栈的数据结构以及功能。下面便是 Java 中的默认构造函数：

Stack()

该构造函数不仅继承了父类 Vector 的函数，还增加属于自己的自定义函数：

*  `boolean empty()`：判断 Stack 是否为空，如果`Stack`为空则返回 true，如果栈非空则返回 false
 *  `Object peek()`：返回栈顶元素，但是不会将其删除
 *  `Object pop()`：弹出栈顶元素，同时将该元素从 Stack 中删除
 *  `Object push(Object element)`：对 Stack 进行压栈，同时返回该元素
 *  `int search(Object element)`：搜索 Stack 中的元素，找到之后返回该元素与栈顶位置的便宜，否则返回 1

#### **1.3 栈 Java 代码示例** ####

import java.util.*;
    
    public class StackDemo {
    
       static void showpush(Stack st, int a) {
          st.push(new Integer(a));
          System.out.println("push(" + a + ")");
          System.out.println("stack: " + st);
       }
    
       static void showpop(Stack st) {
          System.out.print("pop -> ");
          Integer a = (Integer) st.pop();
          System.out.println(a);
          System.out.println("stack: " + st);
       }
    
       public static void main(String args[]) {
          Stack st = new Stack();
          System.out.println("stack: " + st);
          showpush(st, 12);
          showpush(st, 24);
          showpush(st, 55);
          showpop(st);
          showpop(st);
          showpop(st);
          try {
             showpop(st);
          } catch (EmptyStackException e) {
             System.out.println("empty stack");
          }
       }
    }
    /*
    运行结果：
    stack: [ ]
    push(12)
    stack: [12]
    push(24)
    stack: [12, 24]
    push(55)
    stack: [12, 24, 55]
    pop -> 55
    stack: [12, 24]
    pop -> 42
    stack: [12]
    pop -> 12
    stack: [ ]
    pop -> empty stack
    */

### **2. 队列** ###

队列同样也属于线性结构，队列是先进先出（FIFO，First In First Out）的线性表。和栈一样，队列也有数组和链表两种实现方式。用数组实现的队列称为顺序队列，采用链表实现的队列称为链式队列。在计算机系统中，Queue 用来存放 等待处理元素 的集合，这种场景一般用于缓冲、并发访问。

#### **2.1 定义** ####

队列最像的情景就是排队存钱，和栈一样，队列是一种操作受限制的线性表。

*  队头（front）：只允许队列进行删除操作的一端
 *  队尾（rear）：只允许队列进行插入操作的一端
 *  入队（enqueue）：在队列后端中插入一个队列元素称为入队
 *  出队（dequeue）：在队列前端删除一个队列元素称为出队
 *  空队列：队列中没有元素

![0d9331824d595351b1db34e3e6c2adf7.png][]

在具体的业务场景中，如果是对一些处理时间极短的即时消息处理是用不到队列的，可以通过直接阻塞式的函数调用就可以解决。然而一些在大数据处理的应用场景下，一些消息处理会非常耗时，一般新的消息传输过来，系统基本处于阻塞状态，影响用户体验。在这种场景下引入队列，把现在放在队列中，然后再使用新的线程进行处理，这样就能完美解决消息堵塞的问题了。

#### **2.2 Java Queue 接口** ####

Java 中并没有指定的 Queue 类，而是一个队列的接口，其中 Deque、LinkedList、PriorityQueue、BlockingQueue 等类都实现了它。而这些集合都是继承自 Collection 接口，当然除了继承了父类的方法外，Queue 还添加了一些新的操作：添加、删除、查询等。Queue 提供的 add、offer 方法初衷是希望子类能够禁止添加元素为 null，这样可以避免在查询时返回 null 究竟是正确还是错误。Queue 的大部分接口都实现了这个要求，其中 LinkedList 这个实现类没有这样的要求。

这里需要注意的是：这些操作通常都包含两种实现形式，其中一种是操作失败返回特殊值、另一种是直接抛出异常。

*  add：队列增加新元素，如果队列已满，抛出 IIIegaISlabEepeplian 异常。
 *  remove：移除并返回队头元素，如果队列为空，抛出一个 NoSuchElementException 异常。
 *  element：返回队头元素，如果队列为空，抛出一个 NoSuchElementException 异常。
 *  offer：队列添加新元素并返回 true，如果队列满，返回 false。
 *  poll：移除并返问队头元素，如果队列为空，返回 null。
 *  peek：返回队头元素，如果队列为空，则返回 null。
 *  put：添加新元素，如果队列满，则阻塞。
 *  take：移除并返回队头元素，如果队列为空，则阻塞。

#### **2.3 队列 Java 代码示例** ####

import java.util.LinkedList;
    import java.util.Queue;
    
    class QueuekDemo {
        public static void main(String[] a) {
            Queue<String> queue = new LinkedList<>();
            queue.offer("1");//插入一个元素
            queue.offer("2");
            queue.offer("3");
            //打印元素个数
            System.out.println("queue.size()  " + queue.size());//queue.size()  3
            //遍历打印所有的元素,按照插入的顺序打印
            for (String string : queue) {
                System.out.println(string);
            }
            System.out.println("queue.size()  " + queue.size());//queue.size()  3   上面只是简单循环，没改变队列
    
            String getOneFrom1 = queue.element();
            System.out.println("getOneFrom1  " + getOneFrom1);//getOneFrom1  1          因为使用前端而不移出该元素
            System.out.println("queue.size()  " + queue.size());//queue.size()  3       队列变啦才怪
    
            String getOneFrom2 = queue.peek();
            System.out.println("getOneFrom2  " + getOneFrom2);//getOneFrom2  1          因为使用前端而不移出该元素
            System.out.println("queue.size()  " + queue.size());//queue.size()  3       队列变啦才怪
    
            String getOneFrom3 = queue.poll();
            System.out.println("getOneFrom3  " + getOneFrom3);//getOneFrom3  1          获取并移出元素
            System.out.println("queue.size()  " + queue.size());//queue.size()  2       队列变啦
        }
    }

### **3. 牛刀小试** ###

#### **3.1 腾讯 2018 年实习面试** ####

**问：**线程的基本组成是什么？

**答：**寄存器堆栈。

#### **3.2 今日头条 2019 年后端开发实习面试** ####

**问：**OS 中的堆栈是什么？

**答：**

*  栈（操作系统）：由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈，栈使用的是一级缓存， 他们通常都是被调用时处于存储空间中，调用完毕立即释放。
 *  堆（操作系统）：一般由程序员分配释放， 若程序员不释放，程序结束时可能由 OS 回收，分配方式倒是类似于链表。堆则是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定（并不是一旦成为孤儿对象就能被回收）。所以调用这些对象的速度要相对来得低一些。
 *  堆（数据结构）：堆可以被看成是一棵树，如：堆排序。
 *  栈（数据结构）：一种后进先出的数据结构。

#### **3.3 阿里 2019 年提前批 C++ 开发** ####

**问：**堆栈用什么数据结构实现比较好？

**答：**

*  静态数组：特点是要求结构的长度固定，而且长度在编译时候就得确定。其优点是结构简单，实现起来方便而不容易出错。而缺点就是不够灵活以及固定长度不容易控制，适用于知道明确长度的场合。
 *  动态数组：特点是长度可以在运行时候才确定以及可以更改原来数组的长度。优点是灵活，缺点是由此会增加程序的复杂性。
 *  链式结构：特点是无长度上线，需要的时候再申请分配内存空间，可最大程度上实现灵活性。缺点是链式结构的链接字段需要消耗一定的内存，在链式结构中访问一个特定元素的效率不如数组。

今日内容有get吗，欢迎各位留言讨论！

**下期预****告：**栈与队列的存储结构与实现

以上专栏均来自CSDN GitChat专栏**《数据结构算法面试全解析》，**作者**春晨溅雨****·4****位算法工程师**，专栏详情可识别下方二维码查看哦！

**了解更多详情**

**可识别下方二维码**

![4c1cd28fc34f8bfda96fbe57df6950cc.png][]

[fdca50b309bf073eb9b44a635e6adc5d.png]: /images/20221005/d77ca3e70dd3406f9b324490c00c15fa.png
[LRU]: http://mp.weixin.qq.com/s?__biz=MzU5MjEwMTE2OQ%3D%3D&chksm=fe266048c951e95ea3f648f8a8b8441bd824b9fb75f1c491f2bb6a4df8750bc67e47647f2193&idx=2&mid=2247502358&scene=21&sn=25293a9f2063621a4a7e1ad97a18fd4f#wechat_redirect
[3685669f5704f150d07f2de066861235.png]: /images/20221005/ed7e1caf93f143f8b27a0127b61c7182.png
[0d9331824d595351b1db34e3e6c2adf7.png]: /images/20221005/eca26a13357d4321adced390041631eb.png
[4c1cd28fc34f8bfda96fbe57df6950cc.png]: /images/20221005/b9602623ec354ad090804d0b4743e9f5.png