day10--232.用栈实现队列+ 225. 用队列实现栈+20. 有效的括号+ 1047. 删除字符串中的所有相邻重复项

本文主要是介绍day10--232.用栈实现队列+ 225. 用队列实现栈+20. 有效的括号+ 1047. 删除字符串中的所有相邻重复项，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、232.用栈实现队列

题目链接：https://leetcode.cn/problems/implement-queue-using-stacks/description/
文章讲解：https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频讲解：https://www.bilibili.com/video/BV1nY4y1w7VC

1.1 初见思路

1.栈先进后出，队列先进先出
2.两个栈，栈A和栈B来模拟队列，入队列操作=入栈A，出队列=出栈B
3.出队列时，先判断栈B是否还有值，如果没有，就把A中的所有都弹出放入栈B，如果B有值，就直接从B中弹出

1.2 具体实现

class MyQueue {Stack<Integer> stackA;Stack<Integer> stackB;public MyQueue() {stackA=new Stack<Integer>();stackB=new Stack<Integer>();}public void push(int x) {stackA.push(x);}public int pop() {if(!stackB.isEmpty()){return stackB.pop();}else{while(!stackA.isEmpty()){stackB.push(stackA.pop());}return stackB.pop();}}public int peek() {if(!stackB.isEmpty()){return stackB.peek();}else{while(!stackA.isEmpty()){stackB.push(stackA.pop());}return stackB.peek();}}public boolean empty() {return stackA.isEmpty() && stackB.isEmpty();}
}

1.3 重难点

把思路想好，没有什么难度

二、 225. 用队列实现栈

题目链接：https://leetcode.cn/problems/implement-stack-using-queues/description/
文章讲解：https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频讲解：https://www.bilibili.com/video/BV1Fd4y1K7sm

2.1 初见思路

1.跟用栈实现队列有区别
2.两个队列A和B，让A中的顺序和栈中出栈的顺序保持一致，让B作为辅助队列

2.2 具体实现

class MyStack {Queue<Integer> queue1; // 和栈中保持一样元素的队列Queue<Integer> queue2; // 辅助队列/** Initialize your data structure here. */public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}/** Push element x onto stack. */public void push(int x) {queue2.offer(x); // 先放在辅助队列中while (!queue1.isEmpty()){queue2.offer(queue1.poll());}Queue<Integer> queueTemp;queueTemp = queue1;queue1 = queue2;queue2 = queueTemp; // 最后交换queue1和queue2，将元素都放到queue1中}/** Removes the element on top of the stack and returns that element. */public int pop() {return queue1.poll(); // 因为queue1中的元素和栈中的保持一致，所以这个和下面两个的操作只看queue1即可}/** Get the top element. */public int top() {return queue1.peek();}/** Returns whether the stack is empty. */public boolean empty() {return queue1.isEmpty();}
}

2.3 重难点

如何实现队列A的顺序和栈的元素顺序一致

三、 20. 有效的括号

题目链接：https://leetcode.cn/problems/remove-element/
文章讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP

3.1 初见思路

1.用栈来实现

3.2 具体实现

class Solution {public boolean isValid(String s) {Stack<Character> stack  = new Stack<Character>();for(int i=0;i<s.length();i++){char c = s.charAt(i);if(c=='(' || c=='{' || c=='['){stack.push(c);}else{if(stack.isEmpty()){return false;}char pc = stack.pop();if(pc=='('){if(c==')'){continue;}else{return false;}}if(pc=='{'){if(c=='}'){continue;}else{return false;}}if(pc=='['){if(c==']'){continue;}else{return false;}}}}return stack.isEmpty();}
}

3.3 重难点

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

题目链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/
文章讲解：https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html
视频讲解：https://www.bilibili.com/video/BV12a411P7mw

4.1 初见思路

1.入栈时先判断栈顶元素是否等于准备入栈的元素，如果相等就不入栈而进行弹出栈顶元素
但是这种实现方法，会存在最终的栈怎么转成字符串?
2.所以应该使用双向队列，即可以从尾部删除元素，有可以从头开始访问元素拼接字符串

4.2 具体实现

class Solution {public String removeDuplicates(String s) {Stack<Character> stack = new Stack<Character>();char[] c = s.toCharArray();for(char cc:c){if(!stack.isEmpty() && stack.peek()==cc){stack.pop();}else{stack.push(cc);}}Stack<Character> temp = new Stack<Character>();while(!stack.isEmpty()){temp.push(stack.pop());}String res = "";while(!temp.isEmpty()){res+=temp.pop();}return res;}
}