devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】stack & queue —— 栈和队列

作者：小丑西瓜9 | 2024-04-30 14:54:39

赞

踩

【数据结构】stack & queue —— 栈和队列

前言

这阵子一直在学数据结构，知识点消化地有点慢导致博客一直没写，现在总算是有时间歇下来补补前面落下的博客了。从现在起恢复周更，努努力一周两篇也不是梦……闲话少说，今天就让我们一起来认识栈和队列

1. 栈的介绍和使用

栈（stack）是一种特殊的线性表，它只允许先进后出，也就是只能在固定的一端进行插入和删除操作。上面的一端叫做栈顶，可以插入删除，下面的一端就叫做栈底。

压栈/入栈/进栈：即从栈顶添加数据

出栈：即数据在栈顶弹出

栈的原则是：先进后出——就像子弹上膛，弹匣最先压进的子弹最后射出

1.1 语法格式

Stack类位于java.util包当中，我们在使用前要记得导包

  1. import java.util.Stack;
  2.  
  3. Stack<E> stack = new Stack<>();

又因为Stack实现了List接口，所以我们也可以用接口来引用Satck对象，要记得List类也需要导包

  1. import java.util.List;
  2. import java.util.ArrayList;
  3.  
  4. List<E> stack = new Stack<>();

 对于两种stack的创建，我更推荐第二种，因为List接口的方法更多，而且Stack我们现在用的比较少，不常用了

注：我们在这里介绍的是Stack的原生方法，也就是用第一种方法创建的，并非是接口的方法

1.2 入栈

E push（E e）：将e入栈，并且返回e，e以及返回值的类型都为E

  1.         Stack<Integer> stack = new Stack<>();
  2.         stack.push(12);
  3.         stack.push(23);
  4.         stack.push(34);
  5.         System.out.println(stack);

因为Stack已经重写了toString方法，所以我们还可以直接打印list，运行结果如下

1.3 出栈

E pop（）：将栈顶元素出栈并返回，它会删除栈顶元素

E peek（）：获取栈顶元素，它并不会删除栈顶元素

  1.         Stack<Integer> stack = new Stack<>();
  2.         stack.push(12);
  3.         stack.push(23);
  4.         stack.push(34);
  5.         System.out.println(stack);
  6.  
  7.         stack.pop();//34被删除
  8.  
  9.         Integer p1 = stack.peek();
  10.         System.out.println(p1);//23
  11.         System.out.println(stack);

我们用Stack（）先创建了一个空栈，然后连续三个push（），栈内元素从下往上是：12、23、34，接下就pop（），删除栈顶元素34，接着在创建一个p1来接收peek（）的值，打印p1，最后在打印stack整个栈。运行结果如下：

1.4 栈的空间

int size（）：获取栈的大小

boolean empty（）：检测栈是否为空

*boolean isEmpty（）：也是判空（是从Collection继承而来的）

  1.         Stack<Integer> stack = new Stack<>();
  2.         stack.push(12);
  3.         stack.push(23);
  4.         stack.push(34);
  5.  
  6.         int size = stack.size();
  7.         System.out.println(size);
  8.  
  9.         boolean flag1 = stack.empty();
  10.         System.out.println(flag1);
  11.         //继承来的
  12.         boolean flag2 = stack.isEmpty();
  13.         System.out.println(flag2);

2. 栈的模拟实现

栈是一种特殊的顺序表，它始终遵循先进后出的原则。因此我们可以用数组来模拟实现，同时我们还可以设置一个size值，它可以用来表示当前存放数据的个数，也就是栈的大小；我们还可以用它来表示当前将要存放数据的下标

  1. import java.util.Arrays;
  2.  
  3. public class MyStack {
  4.     int[] array;
  5.     int usedSize;
  6.  
  7.     public MyStack(){
  8.         this.array = new int[10];
  9.     }
  10.  
  11.     //入栈
  12.     public void push(int val) {
  13.         if (isFull()) {
  14.             //扩容
  15.             this.array = Arrays.copyOf(array,2*array.length);
  16.         }
  17.         array[usedSize] = val;
  18.         usedSize++;
  19.     }
  20.  
  21.     //判满
  22.     public boolean isFull() {
  23.         return usedSize == array.length;
  24.     }
  25.  
  26.     //出栈，删除栈顶元素
  27.     public int pop() {
  28.         if (isFull()) {
  29.             return -1;
  30.         }
  31.         int ret =  array[usedSize-1];
  32.         usedSize--;
  33.         return ret;
  34.     }
  35.  
  36.     //获得栈顶元素但不删除
  37.     public int peek() {
  38.         if (isFull()) {
  39.             return -1;
  40.         }
  41.         return array[usedSize-1];
  42.     }
  43.  
  44.     //求栈的空间大小
  45.     public int size() {
  46.         return usedSize;
  47.     }
  48.  
  49.     //判空
  50.     public boolean empty() {
  51.         return 0 == usedSize;
  52.     }
  53. }

3. 栈的应用场景

括号匹配 —— 力扣 20. 有效的括号

分析：我们可以把想到的情况都列出来，以下四种情况中，只有第一种才是true，其余三种都是false

我们先创建一个空栈，然后遍历字符串s，遇到左括号就入栈，接着继续遍历，遇到右括号就用peek获得栈顶元素，然后跟右括号匹配。如果是一对的，就把左括号出栈，如果不是一队，就直接返回false。而且如果我们遍历完字符串s后，栈还不为空，就时情况三和情况四，直接返回false

具体代码

  1. class Solution {
  2.     public boolean isValid(String s) {
  3.         //创建一个空栈
  4.         Stack<Character>  stack = new Stack<>();
  5.  
  6.         //遍历字符串s
  7.         for(int i = 0; i < s.length(); i++) {
  8.             把字符串s的元素一个个拆出来
  9.             char ch1 = s.charAt(i);
  10.  
  11.             //如果为左括号，就入栈
  12.             if(ch1 == '(' || ch1 == '[' || ch1 == '{') {
  13.                 stack.push(ch1);
  14.             } else {
  15.                 //判断栈空不空，空则返回false
  16.                 if(stack.empty()) {
  17.                     return false;
  18.                 }
  19.                 else {
  20.                     //当前ch1为右括号，那就先获取栈顶元素
  21.                     char ch2 = stack.peek();
  22.                     if((ch2 == '(' && ch1 == ')') 
  23.                         || (ch2 == '{' && ch1 == '}') 
  24.                         || (ch2 == '[' && ch1 == ']') ) {
  25.                         //匹配成功，栈顶的左括号出栈
  26.                         stack.pop();
  27.                     } else {
  28.                         //匹配失败，直接返回false
  29.                         return false;
  30.                     }
  31.                 }
  32.             }
  33.         }
  34.         //字符串s遍历完了，直接用栈是否为空来当返回值
  35.         return stack.empty();
  36.     }
  37. }

逆波兰表达式 —— 力扣 150. 逆波兰表达式求值

在做这道题之前，我们先来讲一下什么是逆波兰表达式：

逆波兰表达式：也叫做后缀表达式，即运算符在操作数后面。我们平时所看到的表达式都是中缀表达式，就像 2 * (3 + 5)，这个表达式我们看起来很简单，算起来也不难；但是对于计算机来说，它就读不懂这个表达式的意思，因此逆波兰表达式应运而生。

逆波兰表达式的格式非常奇怪，我们可以把中缀表达式转换成逆波兰表达式：就像 2 * (3 + 5)，转换后就是 2 3 5 *+，是不是完全看不懂？看不懂就对了，因为这是专门给计算机看的。

我们还可以把中缀表达式转换成逆波兰表达式，这里有两种方法：

方法一：取巧法

  1. 把表达式从左到右加上括号（要按照先乘除后加减的顺序加）
  2. 把对应的运算符向右拉到对应的括号外面

方法二：使用栈，因为篇幅过长，此处不讲，有兴趣的可以在站内搜一下

讲了这么多，就是为了最后要怎么计算逆波兰表达式，没错，还是得用栈

思路：字符串数组tokens中既有数字又有符号，所以我们要额外写一个方法来判断，接着我们遍历字符串数组，一边遍历一边判断，当遇到数字时，就入栈；遇到就弹出两个数字，先放右边，再放左边，确保减和除的顺序不出错，算完后的结果再入栈，一直遍历下去直到字符串的末尾

具体代码

  1. class Solution {
  2.     public int evalRPN(String[] tokens) {
  3.         //创建空栈
  4.         Stack<Integer> stack = new Stack<>();
  5.  
  6.         //遍历数组
  7.         for(int i = 0; i < tokens.length;  i++) {
  8.             String tmp = tokens[i];
  9.             //判断是数字还是符号
  10.             if(!isOperation(tmp)) {
  11.                 //数字就入栈
  12.                 Integer val = Integer.valueOf(tmp);
  13.                 stack.push(val);
  14.             } else {
  15.                 //符号就弹出两个数字
  16.                 Integer val2 = stack.pop();
  17.                 Integer val1 = stack.pop();
  18.                 //用switch来选择要哪种运算
  19.                 switch (tmp) {
  20.                     //算完后结果再入栈
  21.                     case "+":
  22.                     stack.push(val1 + val2);
  23.                     break;
  24.                     case "-":
  25.                     stack.push(val1 - val2);
  26.                     break;
  27.                     case "*":
  28.                     stack.push(val1 * val2);
  29.                     break;
  30.                     case "/":
  31.                     stack.push(val1 / val2);
  32.                     break;
  33.                 }
  34.             }
  35.         }
  36.         //遍历完字符串数组，弹出最终结果
  37.         return stack.pop();
  38.     }
  39.  
  40.     public boolean isOperation(String s) {
  41.         if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
  42.             return true;
  43.         }
  44.         return false;
  45.     }
  46. }

4. 队列的介绍和使用

队列（Queue）也是一种特殊的线性表，他只允许在一端进行插入操作，在另一端进行删除操作，也就是先进先出。插入操作的一端就是队尾，删除操作的一端就叫做队头

入队：即数据从队尾入队

出队：即数据从队头出队

4.1 语法格式

（在Java中，Queue是一个接口，底层是用链表实现的，因此我们在实例化时必须用LinkedList的对象，因为LinkedList它实现了Queue接口）

  1. import java.util.LinkedList;
  2. import java.util.Queue;
  3.  
  4. Queue<Integer> queue = new LinkedList<>();

要记得导包 

4.2 入队

boolean offer（E e）：将e从队尾插入进队里，如果队列空间不够，则返回false 
  1.         Queue<Integer> queue = new LinkedList<>();
  2.         queue.offer(12);
  3.         queue.offer(23);
  4.         queue.offer(34);
  5.         System.out.println(queue);

 运行结果如下

4.3 出队

E poll（）：将队头数据弹出，并返回该数据（会删除队头元素）
E peek（）：获取队头数据，但并不删除 
  1.         Queue<Integer> queue = new LinkedList<>();
  2.         queue.offer(12);
  3.         queue.offer(23);
  4.         queue.offer(34);
  5.         System.out.println(queue);
  6.  
  7.         queue.poll();//删除12
  8.  
  9.         Integer I = queue.peek();//获取队头元素
  10.         System.out.println(I);//23
  11.         System.out.println(queue);

运行结果如下

4.4 队列的空间

（此处的方法均为Collection的方法，因为Queue没有判空等方法）

int size（）：获取队列的大小

boolean isEmpty（）：检测队列是否为空

  1.         Queue<Integer> queue = new LinkedList<>();
  2.         queue.offer(12);
  3.         queue.offer(23);
  4.         queue.offer(34);
  5.         System.out.println(queue);
  6.  
  7.         System.out.println(queue.size());
  8.         System.out.println(queue.isEmpty());

运行结果如下 

 

5. 队列的模拟使用

5.1 链式存储结构

队列是一种特殊的顺序表，它始终遵循先进先出的原则。因此我们可以使用链表来模拟实现，即链式结构

  1. public class MyQueue {
  2.  
  3.     //创建链表
  4.     class ListNode {
  5.        public int val;
  6.        public ListNode prev;
  7.        public ListNode next;
  8.  
  9.         public ListNode(int val) {
  10.             this.val = val;
  11.         }
  12.     }
  13.  
  14.     public ListNode head;
  15.     public ListNode last;
  16.  
  17.     //入队（尾插法）
  18.     public void offer(int val) {
  19.         ListNode node = new ListNode(val);
  20.         if (head == null) {
  21.             head = last = node;
  22.         } else {
  23.             last.next = node;
  24.             node.prev = last;
  25.             last = last.next;
  26.         }
  27.     }
  28.  
  29.     //出队（头删法）返回出对的元素
  30.     public int poll() {
  31.         try {
  32.             checkQueueEmpty();
  33.         } catch (QueueEmptyException e) {
  34.             e.printStackTrace();
  35.         }
  36.         int ret = head.val;
  37.         if (head.next == null) {
  38.             head = last = null;
  39.         } else {
  40.             head = head.next;
  41.             head.prev = null;
  42.         }
  43.         return ret;
  44.     }
  45.  
  46.     private void checkQueueEmpty() throws QueueEmptyException {
  47.         if (isEmpty()){
  48.             throw new QueueEmptyException("队列为空！");
  49.         }
  50.     }
  51.  
  52.     //取出队头元素，不删除
  53.     public int peek() {
  54.         try {
  55.             checkQueueEmpty();
  56.         } catch (QueueEmptyException e) {
  57.             e.printStackTrace();
  58.         }
  59.         return head.val;
  60.     }
  61.  
  62.     public boolean isEmpty() {
  63.         return head == null;
  64.     }
  65. }

栈的空间异常判断

  1. public class QueueEmptyException extends RuntimeException{
  2.     public QueueEmptyException() {
  3.  
  4.     }
  5.     public QueueEmptyException(String message) {
  6.         super(message);
  7.     }
  8. }

5.2 顺序存储结构

除了用链式结构，我们还可以使用顺序结构来模拟实现队列

  1. public class MyQueue {
  2.     int[] array;
  3.     int front;
  4.     int rear;
  5.  
  6.     public MyQueue(){
  7.         this.array = new int[10];
  8.     }
  9. }

初始状态（队列为空）：front == rear == 0
进队：当队列不满时，先送数据到队尾，再将rear加1
出队：当队列不为空时，先把队头数据取出，再将front加1
但是当我们把队列内所有的元素都删除时，front又会等于rear，此时队列内为空，但front == rear ≠ 0，会出现“假溢出”现象

循环队列

为了解决“假溢出”现象，我们可以把队列头尾相接，形成循环队列。循环队列是一种头尾相接的顺序存储结构

当我们要向循环队列插入一个元素，此时如果last是在队尾，就应该：last = (last+1)%elem.length

当我们要把循环队列删除一个元素，此时如果first是在队头，就应该：first = (first+1)%elem.length

当我们想要区分队列是空是满，有三种方法：

1. 添加一个计数size，插入一个就size++，用size去跟array.length来比较判断

2. 浪费一个空间，这个空间不放元素，当last指向这里时，即为满

3. 使用标记，标记上队头队尾的位置，一旦first和last到那里，就能判断

可以做一下这道题加深理解 —— 力扣 622. 设计循环队列

6. 栈和队列的相互转换

6.1 用队列实现栈

原题地址： 力扣 225. 用队列实现栈

读题后我们可以提炼出重点：

  1. 我们可以使用两个队列，并且使用队列的标准操作（push、pop、peek、size、isEmpty）
  2. 我们要实现的是栈的四个基本操作：push、top、pop、empty（通过示例我们可以知道top等同于peek）
  3. 要注意MyStack类各方法的返回值

具体代码

1. 先把两个队列初始化：

  1.     public Queue<Integer> queue1;
  2.     public Queue<Integer> queue2;
  3.     public MyStack() {
  4.         queue1 = new LinkedList<>();
  5.         queue2 = new LinkedList<>();
  6.     }

2. 判空 empty( ) ：

  1.     public boolean empty() {
  2.         return (queue1.isEmpty() && queue2.isEmpty());
  3.     }

3. 入栈 push( )：

入栈的思想很简单，哪个队列空了就放在哪个队列

我们可以先判断整个栈空不空，即使用empty，为true就直接放入队列1。不为空则表明俩队列有一个为空，一个不为空，照这个思路我们可以用代码来实现

  1.     public void push(int x) {
  2.         if (empty()) {
  3.             queue1.offer(x);
  4.             return;
  5.         }
  6.         if (!queue1.isEmpty()) {
  7.             queue1.offer(x);
  8.         } else {
  9.             queue2.offer(x);
  10.         }
  11.     }

4. 出栈 pop( )：

首先，判断栈是否为空，不为空直接返回-1（写个异常更好，此处不展示）；接下来，把一个队列中的N-1个元素放到另一个队列中，此时队列剩下的最后一个元素就是我们要“出栈”的元素

  1.     public int pop() {
  2.         if (empty()) {
  3.             return -1;
  4.         }
  5.         
  6.         if (!queue1.isEmpty()) {
  7.             int size = queue1.size();
  8.             for (int i = 0; i < size - 1; i++) {
  9.                 queue2.offer(queue1.poll());
  10.             }
  11.             return queue1.poll();
  12.         } else {
  13.             int size = queue2.size();
  14.             for (int i = 0; i < size - 1; i++) {
  15.                 queue1.offer(queue2.poll());
  16.             }
  17.             return queue2.poll();
  18.         }
  19.     }

5. 获取栈顶元素 top( )：

思路跟出栈类似，但只是返回栈顶元素并不删除

  1.     public int top() {
  2.         if (empty()) {
  3.             return -1;
  4.         }
  5.         if (!queue1.isEmpty()) {
  6.             int size = queue1.size();
  7.             int ret = 0;
  8.             for (int i = 0; i < size; i++) {
  9.                 ret = queue1.poll();
  10.                 queue2.offer(ret);
  11.             }
  12.             return ret;
  13.         } else {
  14.             int size = queue2.size();
  15.             int ret = 0;
  16.             for (int i = 0; i < size; i++) {
  17.                 ret = queue2.poll();
  18.                 queue1.offer(ret);
  19.             }
  20.             return ret;
  21.         }
  22.     }

6.2 用栈实现队列

原题地址：​​​​​​​力扣 232. 用栈实现队列

​

同样我们先读题，提炼信息：

  1. 我们可以使用两个栈，并且使用队列的标准操作（push、pop、peek、size、isEmpty）
  2. 我们要实现的是栈的四个基本操作：push、pop、peek、empty
  3. 要注意MyQueue类各方法的返回值

具体代码

1. 先把两个栈初始化

  1.     Stack<Integer> stack1;
  2.     Stack<Integer> stack2;
  3.     public MyQueue() {
  4.         stack1 = new Stack<>();
  5.         stack2 = new Stack<>();
  6.     }

2. 判空 empty( )：

  1.     public boolean empty() {
  2.         return stack1.empty() && stack2.empty();
  3.     }

3. 入队 push( )：

直接把元素压入任一栈中

  1.     public void push(int x) {
  2.        stack1.push(x);
  3.     }

4. 出队 pop( )：

队列的原则是先进先出，我们现在手头上有两个栈，当把第一个数据入栈时，此时要出队的就是它。所以我们可以用另一个栈来存放栈底之上的所有元素，最后元素即为要取出的元素。

因此我们得通过循环把栈1的元素全存到栈2里

  1.     public int pop() {
  2.         if (empty()) {
  3.             return -1;
  4.         }
  5.         if (stack2.isEmpty()) {
  6.             while (!stack1.isEmpty()) {
  7.                 stack2.push(stack1.pop());
  8.             }
  9.         }
  10.         return stack2.pop();
  11.     }

5. 获取队头元素peek( )：

思路和出队类似，但我们不把元素弹出

  1.     public int peek() {
  2.         if (empty()) {
  3.             return -1;
  4.         }
  5.         if (stack2.isEmpty()) {
  6.             while (!stack1.isEmpty()) {
  7.                 stack2.push(stack1.pop());
  8.             }
  9.         }
  10.         return stack2.peek();
  11.     }

结语

今天我们一起学习了栈和队列，它们俩在结构上和原则上都很类似，要牢记栈是先进后出，队列是先进先出，这些知识点在后面二叉树的学习中还会遇到，接下来博主会把链表的那篇博客补上，敬请期待吧

希望大家能喜欢这篇文章，有总结不到位的地方还请多多谅解，若有出现纰漏，希望大佬们看到错误之后能够在私信或评论区指正，博主会及时改正，共同进步！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/513891
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号