【数据结构】stack queue —

前言

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

1. 栈的介绍和使用

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

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

出栈：即数据在栈顶弹出

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

1.1 语法格式

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

java">import java.util.Stack;Stack<E> stack = new Stack<>();

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

java">import java.util.List;
import java.util.ArrayList;List<E> stack = new Stack<>();

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

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

1.2 入栈

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

java">        Stack<Integer> stack = new Stack<>();stack.push(12);stack.push(23);stack.push(34);System.out.println(stack);

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

1.3 出栈

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

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

java">        Stack<Integer> stack = new Stack<>();stack.push(12);stack.push(23);stack.push(34);System.out.println(stack);stack.pop();//34被删除Integer p1 = stack.peek();System.out.println(p1);//23System.out.println(stack);

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

1.4 栈的空间

int size（）：获取栈的大小

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

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

java">        Stack<Integer> stack = new Stack<>();stack.push(12);stack.push(23);stack.push(34);int size = stack.size();System.out.println(size);boolean flag1 = stack.empty();System.out.println(flag1);//继承来的boolean flag2 = stack.isEmpty();System.out.println(flag2);

2. 栈的模拟实现

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

java">import java.util.Arrays;public class MyStack {int[] array;int usedSize;public MyStack(){this.array = new int[10];}//入栈public void push(int val) {if (isFull()) {//扩容this.array = Arrays.copyOf(array,2*array.length);}array[usedSize] = val;usedSize++;}//判满public boolean isFull() {return usedSize == array.length;}//出栈，删除栈顶元素public int pop() {if (isFull()) {return -1;}int ret =  array[usedSize-1];usedSize--;return ret;}//获得栈顶元素但不删除public int peek() {if (isFull()) {return -1;}return array[usedSize-1];}//求栈的空间大小public int size() {return usedSize;}//判空public boolean empty() {return 0 == usedSize;}
}

3. 栈的应用场景

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

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

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

具体代码

java">class Solution {public boolean isValid(String s) {//创建一个空栈Stack<Character>  stack = new Stack<>();//遍历字符串sfor(int i = 0; i < s.length(); i++) {把字符串s的元素一个个拆出来char ch1 = s.charAt(i);//如果为左括号，就入栈if(ch1 == '(' || ch1 == '[' || ch1 == '{') {stack.push(ch1);} else {//判断栈空不空，空则返回falseif(stack.empty()) {return false;}else {//当前ch1为右括号，那就先获取栈顶元素char ch2 = stack.peek();if((ch2 == '(' && ch1 == ')') || (ch2 == '{' && ch1 == '}') || (ch2 == '[' && ch1 == ']') ) {//匹配成功，栈顶的左括号出栈stack.pop();} else {//匹配失败，直接返回falsereturn false;}}}}//字符串s遍历完了，直接用栈是否为空来当返回值return stack.empty();}
}

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

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

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

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

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

方法一：取巧法

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

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

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

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

具体代码

java">class Solution {public int evalRPN(String[] tokens) {//创建空栈Stack<Integer> stack = new Stack<>();//遍历数组for(int i = 0; i < tokens.length;  i++) {String tmp = tokens[i];//判断是数字还是符号if(!isOperation(tmp)) {//数字就入栈Integer val = Integer.valueOf(tmp);stack.push(val);} else {//符号就弹出两个数字Integer val2 = stack.pop();Integer val1 = stack.pop();//用switch来选择要哪种运算switch (tmp) {//算完后结果再入栈case "+":stack.push(val1 + val2);break;case "-":stack.push(val1 - val2);break;case "*":stack.push(val1 * val2);break;case "/":stack.push(val1 / val2);break;}}}//遍历完字符串数组，弹出最终结果return stack.pop();}public boolean isOperation(String s) {if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {return true;}return false;}
}

4. 队列的介绍和使用

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

入队：即数据从队尾入队

出队：即数据从队头出队

4.1 语法格式

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

java">import java.util.LinkedList;
import java.util.Queue;Queue<Integer> queue = new LinkedList<>();

要记得导包

4.2 入队

boolean offer（E e）：将e从队尾插入进队里，如果队列空间不够，则返回false

java">        Queue<Integer> queue = new LinkedList<>();queue.offer(12);queue.offer(23);queue.offer(34);System.out.println(queue);

运行结果如下

4.3 出队

E poll（）：将队头数据弹出，并返回该数据（会删除队头元素）

E peek（）：获取队头数据，但并不删除

java">        Queue<Integer> queue = new LinkedList<>();queue.offer(12);queue.offer(23);queue.offer(34);System.out.println(queue);queue.poll();//删除12Integer I = queue.peek();//获取队头元素System.out.println(I);//23System.out.println(queue);

运行结果如下

4.4 队列的空间

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

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

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

java">        Queue<Integer> queue = new LinkedList<>();queue.offer(12);queue.offer(23);queue.offer(34);System.out.println(queue);System.out.println(queue.size());System.out.println(queue.isEmpty());

运行结果如下

5. 队列的模拟使用

5.1 链式存储结构

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

java">public class MyQueue {//创建链表class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;//入队（尾插法）public void offer(int val) {ListNode node = new ListNode(val);if (head == null) {head = last = node;} else {last.next = node;node.prev = last;last = last.next;}}//出队（头删法）返回出对的元素public int poll() {try {checkQueueEmpty();} catch (QueueEmptyException e) {e.printStackTrace();}int ret = head.val;if (head.next == null) {head = last = null;} else {head = head.next;head.prev = null;}return ret;}private void checkQueueEmpty() throws QueueEmptyException {if (isEmpty()){throw new QueueEmptyException("队列为空！");}}//取出队头元素，不删除public int peek() {try {checkQueueEmpty();} catch (QueueEmptyException e) {e.printStackTrace();}return head.val;}public boolean isEmpty() {return head == null;}
}

栈的空间异常判断

java">public class QueueEmptyException extends RuntimeException{public QueueEmptyException() {}public QueueEmptyException(String message) {super(message);}
}

5.2 顺序存储结构

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

java">public class MyQueue {int[] array;int front;int rear;public MyQueue(){this.array = new int[10];}
}

初始状态（队列为空）：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. 用队列实现栈

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

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

具体代码

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

java">    public Queue<Integer> queue1;public Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}

2. 判空 empty( ) ：

java">    public boolean empty() {return (queue1.isEmpty() && queue2.isEmpty());}

3. 入栈 push( )：

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

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

java">    public void push(int x) {if (empty()) {queue1.offer(x);return;}if (!queue1.isEmpty()) {queue1.offer(x);} else {queue2.offer(x);}}

4. 出栈 pop( )：

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

java">    public int pop() {if (empty()) {return -1;}if (!queue1.isEmpty()) {int size = queue1.size();for (int i = 0; i < size - 1; i++) {queue2.offer(queue1.poll());}return queue1.poll();} else {int size = queue2.size();for (int i = 0; i < size - 1; i++) {queue1.offer(queue2.poll());}return queue2.poll();}}

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

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

java">    public int top() {if (empty()) {return -1;}if (!queue1.isEmpty()) {int size = queue1.size();int ret = 0;for (int i = 0; i < size; i++) {ret = queue1.poll();queue2.offer(ret);}return ret;} else {int size = queue2.size();int ret = 0;for (int i = 0; i < size; i++) {ret = queue2.poll();queue1.offer(ret);}return ret;}}

6.2 用栈实现队列

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

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

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

具体代码

1. 先把两个栈初始化

java">    Stack<Integer> stack1;Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}

2. 判空 empty( )：

java">    public boolean empty() {return stack1.empty() && stack2.empty();}

3. 入队 push( )：

直接把元素压入任一栈中

java">    public void push(int x) {stack1.push(x);}

4. 出队 pop( )：

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

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

java">    public int pop() {if (empty()) {return -1;}if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.pop();}

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

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

java">    public int peek() {if (empty()) {return -1;}if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.peek();}