【DS】4.栈&队列大总结！

迷南。 2024-04-03 09:39 149阅读 0赞

##  ##

#### 文章目录 ####

*  
 *   *  一、栈的相关概念
     *  二、栈的简单模拟实现（顺序与链式）
     *   *  栈的常用操作
         *  顺序栈的模拟实现
         *  链式栈的模拟实现
     *  三、Stack的使用
     *   *  栈的源码方法
         *  栈的方法使用
     *  四、队列的相关概念
     *  五、队列的简单模拟实现
     *   *  队列的常用操作
         *  顺序队列的模拟实现
         *  链式队列的模拟实现
         *  拓展：双端队列
     *  六、Queue的使用
     *   *  Queue的源码
         *  Queue的方法使用

### 一、栈的相关概念 ###

**定义**：栈是一种操作受限的线性表。**只允许在一端进**行插入删除操作。

**特性**：后进先出即LIFO（last in first out）

**栈顶栈底**：可以进行数据插入、删除操作的一端是栈顶，另一端是栈底。

**压栈出栈**：栈的插入操作叫做进栈/入栈/压栈，栈的删除操作叫做出栈。入数据和出数据都在栈顶。

**存储方式**：顺序存储、链式存储。所以按照存储方式分类，栈可以分为顺序栈和链式栈

对应的集合是Stack，底层是数组，继承于Vector集合类。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AvThaF5b-1665041826898)(F:\\typora插图\\image-20221006140915279.png)\]][img-AvThaF5b-1665041826898_F_typora_image-20221006140915279.png]

【相关面试题】**栈、虚拟机栈、栈帧有什么区别呢？**

*  **栈**：是一种先进后出的**数据结构**。
 *  **虚拟机栈**：是JVM的**一块内存空间**。
 *  **栈帧**：是调用函数的过程中，在Java虚拟机上开辟的**一块内存空间**。

### 二、栈的简单模拟实现（顺序与链式） ###

#### 栈的常用操作 ####

1.  入栈push
2.  出栈pop
3.  得到栈顶元素peek
4.  判空empty
5.  判满isFull
6.  打印栈的元素

#### 顺序栈的模拟实现 ####

public class MyStack {
        
        //类比我们前边的ArrayList的模拟实现，我们在顺序栈的实现时，也定义一个数组，一个usedSize
        public int[] elem;
        public int usedSize;
        public MyStack(){
        
            this.elem=new int[10];
        }
        //压栈
        public int push(int val) {
        
            //1.判满，若满则扩容
            if (isFull()) {
        
                Arrays.copyOf(elem, 2 * elem.length);
            }
            //2.存储数据，usedSize++
            this.elem[usedSize++] = val;
            return val;
        }
        //出栈
        public int pop(){
        
            //1.判空
            if(empty()){
        
                throw new EmptyException("当前栈为空！");
            }
            //2.删除，同时usedSize--
            return this.elem[--usedSize];//简单一点
        }
        //偷看一眼
        public int peek(){
        
            //1.判空
            if(empty()){
        
                throw new EmptyException("当前栈为空！");//自定义异常类不再贴代码
            }
            //2.返回对应的值
            return this.elem[usedSize-1];
        }
        //判满
        public boolean isFull(){
        
            return usedSize== elem.length;
        }
        //判空
        public boolean empty(){
        
            return usedSize==0;
        }
        //重写toString方法，方便打印
        @Override
        public String toString() {
        
            return "MyStack{" +
                "elem=" + Arrays.toString(elem) +
                '}';
        }
    
    }

因为栈是只允许在栈顶进行相关操作，所以出栈入栈时间复杂度都是O（1）

#### 链式栈的模拟实现 ####

链表有很多种，那如果我们实现链式栈该用哪种呢？

--------------------

*  单链表

**如果是单链表入栈**，尾插入栈【找尾巴，入栈的时间复杂度是O（N），就算是找到安上一个尾巴节点也需要找到前一个才能从尾巴删除】、头插入栈【时间复杂度是O（1）】；单链表出栈，尾插出栈【时间复杂度还是O（1）】，头插出栈【O（1）】

**所以如果采用单链表模拟实现栈的时候需要采用头插法入栈**

--------------------

*  双向链表

**如果是双向链表实现，尾巴和头部做栈顶都可以，时间复杂度都是O（1）**

--------------------

但相较于顺序栈，链式使用的比较少，所以此处就不再实现，如果后序有需要的时候，再进行实现。

如果做题有需要，可以先看看：[java链式栈][java]

### 三、Stack的使用 ###

#### 栈的源码方法 ####

栈是操作受限的线性表，所以相较于ArrayList和LinkedList,Stack的方法少了很多，其中peek的含义是看栈顶的元素但是不弹出，push是压栈，pop是出栈。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8m14ZY3q-1665041826901)(F:\\typora插图\\image-20221006141331011.png)\]][img-8m14ZY3q-1665041826901_F_typora_image-20221006141331011.png]

#### 栈的方法使用 ####

public class TestStack {
        
        public static void main(String[] args) {
        
            Stack<Integer> stack=new Stack<>();
            stack.push(10);
            stack.push(20);
            stack.push(30);
            stack.push(40);
            stack.push(50);
            System.out.println(stack);//打印时还是原来的顺序
            //但是pop的时候就不是这样了
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.empty());
            //peek叫做获取栈顶元素，但是不删除
             System.out.println(stack.peek());
             System.out.println(stack.peek());
        }
    }

### 四、队列的相关概念 ###

**定义**：队列是一种操作受限的线性表，只允许在一端进行数据的插入，另一端进行数据的删除。

> LinkedList可以当成队列使用，当成双向链表使用，当成栈实现

**特性**：先进先出（FIFO）

**对应的集合**：Queue,是一个接口，LinkedList实现了这个接口，所以我们通常创建LinkedList对象，，用Queue的引用来引用这个对象。【需要注意区别的是Stack是一个普通类】

**队头队尾**：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头。一般队头用front表示,队尾用rear表示

**入队出队**：向队列中进行插入数据的操作叫做入队，从队列中删除数据的操作叫做出队。

**存储方式**：顺序存储、链式存储。对应的有顺序队、链式队

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-A3b83es4-1665041826902)(F:\\typora插图\\image-20221006144859567.png)\]][img-A3b83es4-1665041826902_F_typora_image-20221006144859567.png]

### 五、队列的简单模拟实现 ###

#### 队列的常用操作 ####

1.  入队enQueue
2.  出队deQueue
3.  判满isFull
4.  判空isEmpty
5.  得到队头Front
6.  得到队尾Rear
7.  得到队列元素个数size

但是我们看源码会发现，它的入队给的方法是offer/add，出队给的是poll/remove,又offer和poll使用的比较多，所以我们在实现链式队的时候，入队命名为offer，出队命名为poll。循环队列命名和上边的一样。

#### 顺序队列的模拟实现 ####

比较麻烦

数组实现队列该怎么操作呢，可能会造成假溢出的问题【队头一直删元素，一直向后走，最后和队尾都到了最后，但是此时前边还有位置】。

此时最好的办法就是，把数组折成一个圈，形成一个**循环队列**【如下图所示】

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-py07AE0b-1665041826903)(F:\\typora插图\\image-20221006145738406.png)\]][img-py07AE0b-1665041826903_F_typora_image-20221006145738406.png]

那么我们怎么实现这个循环队列呢？我们通过看我们需要实现的操作，可以发现最需要解决的问题就是**入队/出队后队头和队尾的坐标变换问题**以及**判满和判空操作的区分**

对此，我们有两个解决方案：①一个计数器②浪费一个空间

这里我采用第二种解决方案来实现

> 队头队尾元素坐标：
> 
> front=(front+1)%elem.length;
> 
> rear=(rear+1)%elem.length;

> 判空满条件：
> 
> 空：rear==front
> 
> 满：(rear+1)% elem.length==front

class MyCircularQueue {
        
        private int[] elem;
        public int rear;//队尾
        public int front;//队头
        public MyCircularQueue(int k) {
        
            elem=new int[k+1];//因为他实际可能没有浪费空间，而是使用的count来解决的这个问题
        }
    
        public boolean enQueue(int value) {
        
            if(isFull()){
        
                return false;
            }
            elem[rear]=value;//原来位置上的
            rear=(rear+1)% elem.length;//添加过元素才放的
            return true;
        }
    
        public boolean deQueue() {
        
            if(isEmpty()){
        
                return false;
            }
            front=(front+1)% elem.length;//极端情况下是不可以加加的，还是需要用除法的
            return true;
        }
    //等价于瞄一下头元素
        public int Front() {
        
            if(isEmpty()){
        
                return -1;
            }
            return elem[front];
        }
    //等价于瞄一下队尾元素
        public int Rear() {
        
            if(isEmpty()){
        
                return -1;
            }
            //rear的下标还是不可以直接得到，因为可能会越界，因此还是需要求的
            //int index=(rear-1+ elem.length)% elem.length;
            int index=rear==0? elem.length-1 :rear-1;
            return elem[index];
        }
    
        public boolean isEmpty() {
        
            if(rear==front){
        
                return true;
            }
            return false;
        }
    
        public boolean isFull() {
        
            if((rear+1)% elem.length==front){
        
                return true;
            }
            return false;
            //如果满了需要扩容，可以不考虑具体所在位置，是一个正常拷贝，直接从0位置开始就可以了
        }
    }

#### 链式队列的模拟实现 ####

这里的链式队列使用单链表或者双链表都是可行的，相较于单链表，双链表可能更方便一点。Java中的Queue是使用LinkedList实现的，这里我们尝试一下单向链表实现队列。

如果是单链表，不管是通过头插还是尾插，总会有一个入队/出队是O(N)的情况，不可能达到都是O(1)的情况。

如果需要达到我们的要求，出队、入队都是O(1)的情况，我们可以加一个tail引用。

假设是采用尾插法，加一个tail引用，在尾部入队（`tail.next=node;tail=node`），在头部出队(`head=head.next;`)，这样就可以了

public class MyQueue {
        
        class ListNode{
        
            public int val;
            public ListNode next;
            public ListNode(int val){
        
                this.val=val;
            }
    
        }
        public int usedSize;
        public ListNode head;
        public ListNode tail;
        //入队
        public void offer(int val){
        
            ListNode node=new ListNode(val);
            //1.队列为空
            if(head==null){
        
                head=node;
                tail=node;
            }else{
        //不空
                tail.next=node;
                tail=node;
            }
            //2.入队
            this.usedSize++;
        }
        //出队
        public int poll(){
        
            
            if(head==null){
        
                return -1;
            }
            int ret=head.val;
            head=head.next;
            if(head.next==null){
        
                tail=null;
            }
            usedSize--;
            return ret;
        }
        public int peek(){
        
            if(head==null){
        
                return -1;
            }
            return head.val;
        }
        public int size(){
        
            return usedSize;
        }
        public boolean empty(){
        
            return usedSize==0;
        }
        @Override
        public String toString() {
        
            return "MyQueue{" +
                    "head=" + head.val +" " +"tail=" + tail.val +
                    '}';
        }
    }

#### 拓展：双端队列 ####

双端队列是指允许两端都可以进行入队和出队操作的队列，对应的集合是Deque,元素可以头入头出也可尾入尾出，它是一个接口，使用的时候必须创建LinkedList对象。

【但实际开发过程中Deque使用的并不是特别多，所以这里也是只知道有这么一个概念就好】

### 六、Queue的使用 ###

#### Queue的源码 ####

这个集合中一共是6个方法，我们可以理解成2组，每组3个，常用的是poll【出队】、offer【添加一个元素】、peek【获取队头元素，但是不删除】；add和offer功能一样，remove和poll功能一样，element和peek功能一样

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tzQnnR78-1665041826904)(F:\\typora插图\\image-20221004192952089.png)\]][img-tzQnnR78-1665041826904_F_typora_image-20221004192952089.png]

> offer在容量受限的时候不会抛异常，add会抛，靠自己需求
> 
> <table> 
>  <thead> 
>   <tr> 
>    <th></th> 
>    <th>抛异常</th> 
>    <th>返回特殊值</th> 
>   </tr> 
>  </thead> 
>  <tbody> 
>   <tr> 
>    <td>插入</td> 
>    <td>add</td> 
>    <td>offer</td> 
>   </tr> 
>   <tr> 
>    <td>删除</td> 
>    <td>remove</td> 
>    <td>poll</td> 
>   </tr> 
>   <tr> 
>    <td>检查</td> 
>    <td>element</td> 
>    <td>peek</td> 
>   </tr> 
>  </tbody> 
> </table>

#### Queue的方法使用 ####

public class TestQueue {
        
        public static void main(String[] args) {
        
            Queue<Integer> queue=new LinkedList<>();
            queue.offer(1);
            queue.offer(2);
            queue.offer(3);
            queue.offer(4);
            queue.offer(5);
    
            System.out.println(queue);
            System.out.println(queue.peek());
            System.out.println(queue.poll());
        }
    }

[img-AvThaF5b-1665041826898_F_typora_image-20221006140915279.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/c05a948da19b44249dbfc9d96589e730.png
[java]: http://t.csdn.cn/25nGX
[img-8m14ZY3q-1665041826901_F_typora_image-20221006141331011.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b2db4e4ac6b747379fe7d43eda1d0cd7.png
[img-A3b83es4-1665041826902_F_typora_image-20221006144859567.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/99e9d3ce267b47c7be6f2732357786a2.png
[img-py07AE0b-1665041826903_F_typora_image-20221006145738406.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b905a6e878074a2b9e75df3bc0efa1fd.png
[img-tzQnnR78-1665041826904_F_typora_image-20221004192952089.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/83a3e531260a4c0197096d471aaaa1e4.png