代码随想录算法训练营第十天 | 232-用栈实现队列、 225-用队列实现栈、20-有效的括号、1047-删除字符串中的所有相邻重复项
LeetCode232 用栈实现队列
题目链接：https://leetcode.cn/problems/implement-queue-using-stacks/description/
文章讲解：https://programmercarl.com/0232.用栈实现队列.html
视频讲解：https://www.bilibili.com/video/BV1nY4y1w7VC/?vd_source=b989f2b109eb3b17e8178154a7de7a51
这题要用栈来实现队列的先进先出，但是栈是先进后出的，因此我们可以设置两个栈来模拟队列，一个作为入栈，一个作为出栈
元素一开始放进入栈，要取的时候再从入栈放入出栈，再从出栈拿元素，这样元素就是先进先出
class MyQueue {Stack<Integer> stackIn;Stack<Integer> stackOut;public MyQueue() {stackIn = new Stack<>();stackOut = new Stack<>();}public void push(int x) {stackIn.push(x);}public int pop() {move();return stackOut.pop();}public int peek() {move();return stackOut.peek();}public boolean empty() {return stackIn.isEmpty() && stackOut.isEmpty();}public void move(){if(!stackOut.empty()){return;}while(!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}
}
LeetCode225 用队列实现栈
题目链接：https://leetcode.cn/problems/implement-stack-using-queues/submissions/681722036/
文章讲解：https://programmercarl.com/0225.用队列实现栈.html
视频讲解：https://www.bilibili.com/video/BV1Fd4y1K7sm/?vd_source=b989f2b109eb3b17e8178154a7de7a51
这里采用一个队列来模拟栈，栈是先进后出，队列是先进先出，当实现栈pop()的时候，要的是队列的队尾元素，所以我们可以将队尾前的元素都出队再入队，这样最前面的那个元素就是之前的队尾元素
class MyStack {Queue<Integer> que;public MyStack() {que = new LinkedList<>();}public void push(int x) {que.offer(x);}public int pop() {move();return que.poll();}public int top() {move();int result = que.poll();que.offer(result);return result;}public boolean empty() {return que.isEmpty();}public void move(){int size = que.size();for(int i = 1; i <= size-1; i++){que.offer(que.poll());}}
}
LeetCode20 有效的括号
题目链接：https://leetcode.cn/problems/valid-parentheses/description/
文章讲解：https://programmercarl.com/0020.有效的括号.html
视频讲解：https://www.bilibili.com/video/BV1AF411w78g/?vd_source=b989f2b109eb3b17e8178154a7de7a51
括号匹配，很经典的栈应用题，遇到左括号将其放入栈，遇到右括号出栈一个元素进行比对，若匹配则可以继续往下遍历括号串，若不匹配则直接return false
注意pop空栈的问题，以及最后记得检查栈是否为空，若不为空说明还有为匹配的左括号，return false
class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();if(s.length() % 2 != 0){return false;}for(int i = 0; i < s.length(); i++){char ch = s.charAt(i);if(ch == '(' || ch == '[' || ch == '{'){stack.push(ch);}else{if(stack.isEmpty()){return false;}char top = stack.pop();if((ch == ')' && top == '(')||(ch == ']' && top == '[')||(ch == '}' && top == '{')){continue;}else{return false;}}}return stack.isEmpty();}
}
LeetCode1047 删除字符串中的所有相邻重复项
题目链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/
文章讲解：https://programmercarl.com/1047.删除字符串中的所有相邻重复项.html
视频讲解：https://www.bilibili.com/video/BV12a411P7mw/?vd_source=b989f2b109eb3b17e8178154a7de7a51
栈记住了遍历数组当前元素的前一个元素，所以这种相邻元素消除的工作很适合用栈来做
核心逻辑是判断栈顶元素和当前元素是否相同，若相同则一起消除，若不相同则将当前元素入栈
class Solution {public String removeDuplicates(String s) {Stack<Character> stack = new Stack<>();int length = s.length();if(length == 1){return s;}for(int i = 0;i < length;i++){char cur = s.charAt(i);if(stack.isEmpty()){stack.push(cur);}else{char top = stack.peek();if(cur != top){stack.push(cur);}else{stack.pop();}}}StringBuilder result = new StringBuilder();while(!stack.isEmpty()){result.append(stack.pop());}return result.reverse().toString();}
}