• 【数据结构篇】线性表2 —— 栈和队列

    前言：上一篇我们介绍了顺序表和链表

    （https://blog.csdn.net/iiiiiihuang/article/details/132615465?spm=1001.2014.3001.5501），

    这一篇我们将介绍栈和队列，栈和队列都是基于顺序表和链表来实现的

    目录

    栈（Stack）

    什么是栈 ？

    栈的方法 和 使用

    栈的模拟实现 

    先初始化一下栈 

    往栈里插入元素 （push)

    栈是否为空(empty)

    弹出栈顶元素（删除）(pop)

    获取栈顶元素 (peek)

    模拟实现完整代码 

    栈的应用场景

     1. 改变元素的序列

    2. 将递归转化为循环

    补充 ：

    队列（Queue） 

    什么是队列 ？

    队列的方法 

    队列模拟实现 

    初始化 

    offer 

    poll

    peek

    完整代码（链式队列） 

    循环队列 

    认识循环队列 

    如何把数组看作是一个循环呢？（rear 从 7 --> 0) 

    设计一个循环队列 （https://leetcode.cn/problems/design-circular-queue/）

    初始化 

    判断队列是否是空的，和是否是满的 

    入队 

     出队

    得到队头元素

    得到队尾元素

    完整代码： （循环队列）

    双端队列 (Deque)

    （面试题） 1. 用队列实现栈   2. 用栈实现队列

     1. 用队列实现栈

    代码实现：

    入栈

    出栈 

    获取栈顶元素 

     判断栈空

    完整代码 

     2. 用栈实现队列 

    我直接上代码了： 

     

    栈（Stack）

    什么是栈 ？

    栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

    后进先出原则：先进的后出，后进的先出  。我们举一个生活中的例子

    比如这有个圆筒，一端封闭，一端开口，然后往圆筒里放乒乓球：

        

    你想拿乒乓球，先拿到的肯定是后放的，那如果你想要拿到最底下的，你肯定得把上面的都拿走才行。也就是 栈的后进先出原则 （先进的后出，后进的先出）

    栈的方法 和 使用

     栈的方法很少，只有这些： 

    使用 （没什么好说的😁😁）

    栈的模拟实现 

     栈这种数据结构可以用数组来实现，也可以用链表来实现，这里我们用数组实现。

    先初始化一下栈 

    往栈里插入元素 （push)

    和顺序表异曲同工，先看看满没满，满了要扩容，再入栈 

    栈是否为空(empty)

    弹出栈顶元素（删除）(pop)

    就很简单 （顺序表那搞懂，这些方法很简单的）

     

    获取栈顶元素 (peek)

     

    模拟实现完整代码 

    1. import java.util.ArrayList;
    2. import java.util.Arrays;
    3.  
    4. /**
    5.  * @Author: iiiiiihuang
    6.  */
    7. public class MyStack {
    8.     private int[] elem;
    9.     private int usedSize;
    10.     private static final int DEFAULT_CAPACITY = 10;//默认容积
    11.     public MyStack() {
    12.         this.elem = new int[DEFAULT_CAPACITY];
    13.     }
    14.  
    15.     /**
    16.      * 往栈里插入元素
    17.      * @param val
    18.      */
    19.     public void push(int val) {
    20.         isFull();
    21.         this.elem[usedSize] = val;
    22.         usedSize++;
    23.     }
    24.     private void isFull() {
    25.         if(usedSize == this.elem.length) {
    26.             this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);
    27.         }
    28.     }
    29.  
    30.     /**
    31.      * 弹出栈顶元素
    32.      * @return
    33.      */
    34.     public int pop() {
    35.         if(empty()) {
    36.             throw new EmptyException("栈为空");
    37.         }
    38.         int pop = this.elem[usedSize - 1];
    39.         usedSize--;
    40.         return pop;
    41.     }
    42.  
    43.     /**
    44.      * 获取栈顶元素
    45.      * @return
    46.      */
    47.     public int peek() {
    48.         if(empty()) {
    49.             System.out.println("栈为空");
    50.             return 0;
    51.         }
    52.         int peek = this.elem[usedSize - 1];
    53.         return peek;
    54.     }
    55.  
    56.     /**
    57.      * 栈是否为空
    58.      * @return
    59.      */
    60.     public boolean empty() {
    61.         return usedSize == 0;
    62.     }
    63. }

    栈的应用场景

     1. 改变元素的序列

    我们去牛客上找两道题做做 

    根据我们上面介绍，栈 遵循 先进后出原则， 我们可以得出答案，不可能的出栈顺序是 D 选项

    因为F，E出来了，下一个出来的必须是 D，这种情况下C不可能比D先出。 

    2. 将递归转化为循环
     

    比如逆序打印链表： 

      1.递归方法 

     2.循环方法 

    运行结果 

     

    补充 ：

    用数组实现栈，出栈，入栈，都是O(1),

    那用链表如何实现栈呢？

    1.假设用单链表（单向）实现栈： 

      尾插： 

          入栈：尾插法 入栈是 O(n)

          出栈：因为栈后进的先出，这就相当于删除链表的尾巴节点，时间复杂度还是O(n);

     头插： 

          入栈：头插法 O(1)

          出栈：相等于删除头节点，时间复杂度O(1)

    2.假设用双向链表实现栈：  （前后都能找到）

    尾插： 

          入栈：尾插法 入栈是 O(1)

          出栈：时间复杂度还是O(1)，

     头插： 

          入栈：头插法 O(1)

          出栈：时间复杂度O(1)

    上述我们可知，用链表实现栈时，双向链表实现栈是最好的，不管从那边入栈，出栈 时间复杂度都是O(1)。

    那使用链式栈时就可以这样使用：如果这是个栈，那peek的内容就是 4. 

    是 4. 

    那为啥会这样，你看LinkedList,里本来就有栈里的一些方法，push..... 

    push 用的是头插法 

    所以如果是顺序栈，你可以用Stack, 如果是链式栈，你就用LinkedList 

    队列（Queue） 

    什么是队列 ？

     队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)

    入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头

    举例说明： 

    假如有一条单行隧道，车辆必须从入口进 （入队列），从出口出（出队列）。那先驶出隧道的车辆肯定是先进去的，后驶出的肯定是后进去的，这就是 队列的先进先出原则

    通过上述介绍，我们发现我们可以把 双向链表当成是一个 队列 ，(单链表也行，双链表更简单)

    队尾进，队头出，时间复杂度O(1)

     ps:Queue 普通队列，Deque 双端队列（两边都可以进出），LinkedList 可以当作普通队列，双端队列，链表，栈（究极打工人😭😭😭）

    队列的方法 

    在Java中，Queue是个接口，底层是通过链表实现的。 

    队列方法少的嘞 

    offer (入队列) 

    peek 

    poll 

    ......... 

    add，remove ，element (和peek一个意思）是一组 

    offer,  poll,  peek 是一组

    队列模拟实现 

    队列的实现使用 顺序结构 和 链式结构 都行，但链式结构更简单一点。

    我们这里拿双链表去写 (前面的链表学会了，这里很简单的，信手拈来）

    初始化 

     

    offer 

     

    调试一看 插进去了 

    poll

    peek

    完整代码（链式队列） 

    1. /**
    2.  * @Author: iiiiiihuang
    3.  */
    4. public class MyQueue {
    5.     static class ListNode {
    6.         private int val;
    7.         private ListNode prev;
    8.         private ListNode next;
    9.         public ListNode(int val) {
    10.             this.val = val;
    11.         }
    12.     }
    13.     private ListNode front;//头
    14.     private ListNode rear;//尾
    15.     private int usedSize;//计数
    16.  
    17.     /**
    18.      * 插入--- 头插法
    19.      * @param val
    20.      */
    21.     public void offer(int val) {
    22.         ListNode node = new ListNode(val);
    23.         if(front == null) {
    24.             front = node;
    25.             rear = node;
    26.         } else {
    27.             node.next = front;
    28.             front.prev = node;
    29.             node = front;
    30.         }
    31.         usedSize++;
    32.     }
    33.  
    34.     /**
    35.      * 删除 -- 尾删
    36.      * @return
    37.      */
    38.     public int poll() {
    39.         if(front == null) {
    40.             throw new EmptyException("队列为空");
    41.         }
    42.         if(front == rear) {
    43.             int poll = front.val;
    44.             front = null;
    45.             rear = null;
    46.             usedSize--;
    47.             return poll;
    48.         }
    49.         int poll = rear.val;
    50.         rear = rear.prev;
    51.         rear.next = null;
    52.         usedSize--;
    53.         return poll;
    54.     }
    55.  
    56.     /**
    57.      * 获取队头
    58.      * @return
    59.      */
    60.     public int peek() {
    61.         if(front == null) {
    62.             throw new EmptyException("队列为空");
    63.         }
    64.         return rear.val;
    65.     }
    66. }

    循环队列
     

    实际中我们有时还会使用一种队列叫循环队列。
    环形队列通常使用数组实现。 

    认识循环队列 

    。。。。。 

    这就有意思了 ，

    front 和 rear 第一次在一起的时候 队列 是空的，第二次 在一起的时候是队列是满的

    那这怎么判断呢，其实有很多方法去判断

     1.计数  usedSize == len

     2.标记，flag

     3.浪费一个空间来区分（常用） 

     浪费一个空间，就类似下面这样

     

    如何把数组看作是一个循环呢？（rear 从 7 --> 0) 

    就是把 rear ++  换成 （rear + 1 ）% len  （余数肯定都是小于 len的（len 数组长度）），rear++ 会越界的 (看不懂自己带数据算算)

    设计一个循环队列 （https://leetcode.cn/problems/design-circular-queue/）

    根据这个来 

     

    初始化 

    判断队列是否是空的，和是否是满的 

     

    入队 

     

     出队

     

    得到队头元素

     

    得到队尾元素

     

    不能直接rear - 1哦

     那现在我们放到力扣里运行一下（链接在上边）

     错了 ！！！ 为什么，我们看看我什么

    数组容量是 3 ，预期结果成功 插入了 3个，而我们的程序，只能插入两个，因为我们的浪费掉了一个空间 。

    所以我们应该多给一个空间： 

     

    在运行一下 ，通过了，当然你要是觉得这样奇怪，你也可以用 usedSize,很多方法啦😎😎

    完整代码： （循环队列）
    1. class MyCircularQueue {
    2.  
    3.     private int[] elem;
    4.     private int front;//头
    5.     private int rear;//尾
    6.     public MyCircularQueue(int k) {
    7.         this.elem = new int[k + 1];
    8.     }
    9.     
    10.     public boolean enQueue(int value) {
    11.         if(isFull()) {
    12.             return false;
    13.         }
    14.         elem[rear] = value;
    15.         rear = (rear + 1) % elem.length;
    16.         return true;
    17.     }
    18.     
    19.     public boolean deQueue() {
    20.         if(isEmpty()) {
    21.             return false;
    22.         }
    23.         front = (front + 1) % elem.length;
    24.         return true;
    25.     }
    26.     
    27.     public int Front() {
    28.         if(isEmpty()) {
    29.             return -1;
    30.         }
    31.         int ret = elem[front];
    32.         return ret;
    33.     }
    34.     
    35.     public int Rear() {
    36.          if(isEmpty()) {
    37.             return -1;
    38.         }
    39.         int index = (rear == 0) ? elem.length - 1 : rear - 1;//不能直接rear - 1哦
    40.         return elem[index];
    41.     }
    42.     
    43.     public boolean isEmpty() {
    44.         return front == rear;
    45.     }
    46.     
    47.     public boolean isFull() {
    48.         if((rear + 1) % this.elem.length == front) {
    49.             return true;
    50.         }
    51.         return false;
    52.     }
    53. }

    双端队列 (Deque)
     

     双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double   ended queue” 的简称。
    那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

    Deque是一个接口，使用时必须创建LinkedList的对象 。

     在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口

    1. Deque stack = new ArrayDeque<>();//双端队列的线性实现（数组）
    2. Deque queue = new LinkedList<>();//双端队列的链式实现 

    （面试题） 1. 用队列实现栈   2. 用栈实现队列

     1. 用队列实现栈

    225. 用队列实现栈 - 力扣（LeetCode）

    1.首先一个栈是不够用的，它俩的出栈原则不一样，栈先进后出，队列先进先出，一个队列实现不了呀 ，对不上。

    2.所以我们需要两个队列，当 2 个队列都为空的时候，说明模拟栈为空。

    3.当要出栈的时候，（出 45 ），我们要把 12，23，34，入到第二个队列里去，然后再把第一个队列里的 45 出队列 ，

    结论就是，”出栈“的时候出不为空的 队列，出队列size - 1 个（俩队列轮流），最后那一个就是我们要 ”出栈“的元素

     4.“入栈” 的时候入到不为空的队列

     思路有了，我们开始写代码：

    代码实现：

    入栈

    出栈 

     用for 循环的时候注意一下，不要写成 i < queue.size() - 1,因为queue.size()一直在变。你先记录一下

    获取栈顶元素 

     我们可以定义一个临时量，来存放栈顶元素

    里面的元素一直被覆盖，那最后出队列的元素，就覆盖了之前的全部元素，就是栈顶元素。 

     注意：这里可别写成 queue1.offer(queue2.poll), 跳两回啦。

     判断栈空

    完美通过 

    完整代码 

    1. import java.util.LinkedList;
    2. import java.util.Queue;
    3.  
    4. /**
    5.  * @Author: iiiiiihuang
    6.  */
    7. public class MyStack {
    8.     private Queue queue1;
    9.     private Queue queue2;
    10.     public MyStack() {
    11.         queue1 = new LinkedList<>();
    12.         queue2 = new LinkedList<>();
    13.     }
    14.  
    15.     /**
    16.      * 入栈操作
    17.      * @param x
    18.      */
    19.     public void push(int x) {
    20.         if(!queue1.isEmpty()){
    21.             queue1.offer(x);
    22.         } else if(!queue2.isEmpty()) {
    23.             queue2.offer(x);
    24.         }else {
    25.             queue1.offer(x);
    26.         }
    27.     }
    28.  
    29.     /**
    30.      * 出栈
    31.      * @return
    32.      */
    33.     public int pop() {
    34.         //先判断栈空不空
    35.         if(empty()) {
    36.             return -1;
    37.         }
    38.         if(!queue1.isEmpty()) {
    39.             int len = queue1.size() - 1;
    40.             while (len > 0) {
    41.                 int tmp = queue1.poll();
    42.                 queue2.offer(tmp);
    43.                 len--;
    44.             }
    45.             return queue1.poll();
    46.         } else {
    47.             int len = queue2.size() - 1;
    48.             while (len > 0) {
    49.                 int tmp = queue2.poll();
    50.                 queue1.offer(tmp);
    51.                 len--;
    52.             }
    53.             return queue2.poll();
    54.         }
    55.     }
    56.  
    57.     /**
    58.      * 获取栈顶元素
    59.      * @return
    60.      */
    61.     public int top() {
    62.         int tmp = -1;
    63.         if(empty()) {
    64.             return -1;
    65.         }
    66.         if(!queue1.isEmpty()) {
    67.             int len = queue1.size();
    68.             while (len > 0) {
    69.                 tmp = queue1.poll();
    70.                 queue2.offer(tmp);
    71.                 len--;
    72.             }
    73.             return tmp;
    74.         } else {
    75.             int len = queue2.size();
    76.             while (len > 0) {
    77.                 tmp = queue2.poll();
    78.                 queue1.offer(tmp);
    79.                 len--;
    80.             }
    81.             return tmp;
    82.         }
    83.     }
    84.  
    85.     public boolean empty() {
    86.         return queue1.isEmpty() && queue2.isEmpty();
    87.     }
    88. }

     2. 用栈实现队列 

    232. 用栈实现队列 - 力扣（LeetCode）

    思路差不多 

    1.两个栈实现，同理 

    2.入队的时候 把所有元素 全部放到第一个栈当中

    3.出队的时候 把所有的元素 全部倒到第二个栈当中，然后出第二个栈顶元素就行了.（记得判空）

    我直接上代码了： 

    1. import java.util.Stack;
    2.  
    3. /**
    4.  * @Author: iiiiiihuang
    5.  */
    6. public class MyQueue {
    7.     private Stack stack1;
    8.     private Stack stack2;
    9.  
    10.     public MyQueue() {
    11.         stack1 = new Stack<>();
    12.         stack2 = new Stack<>();
    13.     }
    14.  
    15.     public void push(int x) {
    16.         stack1.push(x);
    17.     }
    18.  
    19.     public int pop() {
    20.         if(empty()) {
    21.             return -1;
    22.         }
    23.         if(stack2.isEmpty()) {
    24.             while (!stack1.isEmpty()) {
    25.                 stack2.push(stack1.pop());
    26.             }
    27.         }
    28.         return stack2.pop();
    29.     }
    30.  
    31.     public int peek() {
    32.         if(empty()) {
    33.             return -1;
    34.         }
    35.         if(stack2.isEmpty()) {
    36.             while (!stack1.isEmpty()) {
    37.                 stack2.push(stack1.pop());
    38.             }
    39.         }
    40.         return stack2.peek();
    41.     }
    42.  
    43.     public boolean empty() {
    44.         return stack1.isEmpty() && stack2.isEmpty();
    45.     }
    46. }

     

    先别急着走，点个关注先，👀👀👀

    点赞，评论，收藏，支持一下ヾ(≧▽≦*)oヾ(≧▽≦*)o

  • 相关阅读:
    Java技术分享系列：Dubbo 与 Spring Cloud 完美结合
    Vue2的路由和异步请求
    Mac 安装Nodejs
    QStyleFactor和QPalette
    1,2,4,5-四嗪-羧基反应Py-2H-Tetrazine-Py-NH2TFA/dihydroTz-Py-NH2的研究
    Global Mapper栅格计算器，波段计算NDVI、NDSI、NDWI等
    图像处理：图像清晰度评价
    12.OpenWrt-OPKG包管理
    t检验（连续变量）和卡方检验（分类变量）
    torchvision中数据集的使用
  • 原文地址：https://blog.csdn.net/iiiiiihuang/article/details/132687344