⚡刷题计划day10栈与队列继续，可以点个免费的赞哦~

往期可看专栏，关注不迷路，

您的支持是我的最大动力🌹~

目录

⚡刷题计划day10继续，可以点个免费的赞哦~

往期可看专栏，关注不迷路，

您的支持是我的最大动力🌹~

题目一：232. 用栈实现队列

题目二：225. 用队列实现栈

法一：两个队列

法二：一个队列

题目三：20. 有效的括号

题目四：1047. 删除字符串中的所有相邻重复项

法一：使用ArrayDeque作为堆栈（效率一般）

法二：将字符串直接作为栈（效率较高）

法三：双指针(效率无敌高)

---

简单来说，栈是先进后出（FILO，First In Last Out），队列是先进先出（FIFO，First In First Out）的数据结构。

栈的常用操作

压栈（Push）：将元素添加到栈顶。
弹栈（Pop）：移除并返回栈顶元素。
查看栈顶元素（Peek）：返回栈顶元素但不移除它。
检查栈是否为空（IsEmpty）：判断栈是否没有任何元素。
获取栈的大小（Size）：返回栈中元素的数量。

队列常用操作

入队（Offer）：将元素添加到队列尾部。
出队（Poll）：移除并返回队列头部的元素。
查看队首元素（Peek/Element）：返回队列头部的元素但不移除它。
检查队列是否为空（IsEmpty）：判断队列是否没有任何元素。
获取队列的大小（Size）：返回队列中元素的数量。

题目一：232. 用栈实现队列

1. 用栈实现队列

(https://leetcode.cn/problems/implement-queue-using-stacks/description/)

主要思路：

使用栈来模拟队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。

可以结合如下动画理解，这样就将栈转换为了队列：

注意几个点：

• 在push时，直接将数据放进输入栈就可

• 在pop时，会复杂一些，我们需要先判断输出栈是否为空，不为空直接输出；为空则需要将输入栈中的数据全部导入到输出栈，再弹出数据即可

• 关于队列判空，如果进栈和出栈都为空的话，说明模拟的队列为空了。

代码如下：

import java.util.Stack;
​
class MyQueue {
​Stack<Integer> stackIn; // 负责进栈的栈Stack<Integer> stackOut; // 负责出栈的栈
​public MyQueue() {stackIn = new Stack<>(); // 初始化进栈栈stackOut = new Stack<>(); // 初始化出栈栈}
​public void push(int x) {stackIn.push(x); // 将元素x推入stackIn}public int pop() {dumpstackIn(); // 将stackIn中的元素转移到stackOut中return stackOut.pop(); // 弹出stackOut的栈顶元素}public int peek() {dumpstackIn(); // 将stackIn中的元素转移到stackOut中return stackOut.peek(); // 返回stackOut的栈顶元素但不移除}
​public boolean empty() {return stackIn.isEmpty() && stackOut.isEmpty(); // 如果两个栈都为空，则队列为空}
​//将功能相近的函数要抽象出来，就是将输入栈中的数据导入到输出栈private void dumpstackIn() {if (!stackOut.isEmpty()) return; // 如果stackOut不为空，则不需要转移while (!stackIn.isEmpty()) { // 当stackIn不为空时stackOut.push(stackIn.pop()); // 将stackIn的栈顶元素弹出并推入stackOut}}
}

题目二：225. 用队列实现栈

1. 用队列实现栈

(https://leetcode.cn/problems/implement-stack-using-queues/description/)

这题开始也想着和上题一样，使用一个输入队列，一个输出队列，但是仔细想一下，行不通。

队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。

所以用栈实现队列， 和用队列实现栈的思路还是不一样的，这取决于这两个数据结构的性质。

下面解法一先给出两个队列的实现

如下面动画所示，用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。

法一：两个队列

AC代码如下：

class MyStack {
​Queue<Integer> queue1; // 主队列，用来模拟栈Queue<Integer> queue2; // 辅助队列，用于临时存储元素
​/** * 初始化数据结构。*/public MyStack() {queue1 = new LinkedList<>(); // 初始化主队列queue2 = new LinkedList<>(); // 初始化辅助队列}/** * 将元素 x 压入栈顶。*/public void push(int x) {queue2.offer(x); // 先将元素 x 放入辅助队列while (!queue1.isEmpty()){ // 将主队列中的所有元素转移到辅助队列queue2.offer(queue1.poll());}Queue<Integer> queueTemp; // 临时变量用于交换队列queueTemp = queue1; // 交换队列，此时queue2成为主队列queue1 = queue2;queue2 = queueTemp;}/** * 移除并返回栈顶元素。*/public int pop() {return queue1.poll(); // 由于queue1模拟栈，所以直接移除并返回队首元素}/** * 获取栈顶元素。*/public int top() {return queue1.peek(); // 返回queue1的队首元素，即栈顶元素}/** * 判断栈是否为空。*/public boolean empty() {return queue1.isEmpty(); // 如果主队列为空，则栈为空}
}

法二：一个队列

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。

AC代码

class MyStack {Queue<Integer> queue;
​public MyStack() {queue = new LinkedList<>();}
​public void push(int x) {queue.offer(x);int size = queue.size();while (size-->1)//将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部queue.offer(queue.poll());}
​public int pop() {return queue.poll();}
​public int top() {return queue.peek();}
​public boolean empty() {return queue.isEmpty();}
}

题目三：20. 有效的括号

1. 有效的括号

(https://leetcode.cn/problems/valid-parentheses/description/)

由于栈结构的特殊性，非常适合做对称匹配类的题目。

分析：

第一种情况，字符串里左（右）方向的括号多余了 ，所以不匹配。

已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false

第二种情况，括号没有多余，但是 括号的类型没有匹配上。

遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false

第三种情况，字符串里右方向的括号多余了，所以不匹配。

遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false

还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！

根据以上分析三种情况实现，AC代码如下：

class Solution {public boolean isValid(String s) {if(s.length()%2 != 0){return false;}char[] c = s.toCharArray();Deque<Character> deque = new LinkedList<>();for (int i=0;i<s.length();i++){if(c[i] == '('){deque.push(')');}else if (c[i] == '{'){deque.push('}');}else if (c[i] == '['){deque.push(']');}else if(deque.isEmpty() || deque.peek()!=c[i]){return false;}else{deque.pop();}}return deque.isEmpty();}
}

题目四：1047. 删除字符串中的所有相邻重复项

1. 删除字符串中的所有相邻重复项

(https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/)

本题要删除相邻相同元素，相对于[20. 有效的括号]来说其实也是匹配问题，[20. 有效的括号]是匹配左右括号，本题是匹配相邻元素，最后都是做消除的操作。

本题也是用栈来解决的经典题目。

法一：使用ArrayDeque作为堆栈（效率一般）

大致思路：

开始先将字符入栈，然后下一字符入栈前判断是否与已入栈字符相等。

若相等，则直接将栈中元素弹出，

若栈为空或不相等，则入栈，

将字符串遍历结束后，将栈中字符导出为字符串格式，因为从栈里弹出的元素是倒序的，所以再对字符串进行反转一下，就得到了最终的结果。

动画如图：

AC代码及注释：

class Solution {public String removeDuplicates(String s) {//1.ArrayDeque会比LinkedList在除了删除元素这一点外会快一点//2.在Java中，ArrayDeque 是双端队列的实现，它提供了队列和栈的功能。尽管它是一个队列，但它同时支持在两端进行操作，所以它也可以用来模拟栈的行为，直接调用对应方法即可。ArrayDeque<Character> queue = new ArrayDeque<>();char[] c = s.toCharArray();for(int i=0;i<s.length();i++){if(queue.isEmpty() || c[i] != queue.peek()){queue.push(c[i]);}else {queue.pop();}}String str = "";//注意这里挺妙，queue.pop() 作为第一个加数，这样我们就不需要再翻转字符串了。while (!queue.isEmpty()){str = queue.pop() +str;}return str;
​}
}

法二：将字符串直接作为栈（效率较高）

拿字符串直接作为栈，省去了栈还要转为字符串的操作，效率较高。

AC代码及注释：

class Solution {public String removeDuplicates(String s) {StringBuilder sb = new StringBuilder();for (char c : s.toCharArray()) {// 如果StringBuilder不为空，并且最后一个字符与当前字符相同if (sb.length() != 0 && sb.charAt(sb.length() - 1) == c) {// 删除StringBuilder中的最后一个字符sb.deleteCharAt(sb.length() - 1);} else {// 否则，将当前字符添加到StringBuilder中sb.append(c);}}return sb.toString();}
}

法三：双指针(效率无敌高)

AC代码及注释：

class Solution {public String removeDuplicates(String s) {char[] ch = s.toCharArray();int fast = 0;int slow = 0;while(fast < s.length()){// 直接用fast指针覆盖slow指针的值ch[slow] = ch[fast];// 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了if(slow > 0 && ch[slow] == ch[slow - 1]){slow--;}else{slow++;}fast++;}return new String(ch,0,slow);}
}

有所帮助可以点个免费的赞赞哦~🌹