代码随想录算法训练营第十天 | 用栈实现队列、 用队列实现栈、有效的括号、删除字符串中的所有相邻重复项

用栈实现队列

用两个栈来实现队列的先进后出

/** @lc app=leetcode.cn id=232 lang=java** [232] 用栈实现队列*/// @lc code=startimport java.util.Stack;class MyQueue {Stack<Integer> in = new Stack<>();Stack<Integer> out = new Stack<>();public MyQueue() {}public void push(int x) {in.add(x);}public int pop() {while (!in.isEmpty()) {out.add(in.pop());}int result = out.pop();while (!out.isEmpty()) {in.add(out.pop());}return result;}public int peek() {while (!in.isEmpty()) {out.add(in.pop());}int result = out.peek();while (!out.isEmpty()) {in.add(out.pop());}return result;}public boolean empty() {return in.isEmpty();}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/
// @lc code=end

用队列实现栈

学会了通过维护单个队列实现先进先出栈

/** @lc app=leetcode.cn id=225 lang=java** [225] 用队列实现栈*/// @lc code=startimport java.util.LinkedList;
import java.util.Queue;class MyStack {Queue<Integer> queue;public MyStack() {queue = new LinkedList<>();}public void push(int x) {queue.offer(x);for (int i = 0; i < queue.size() - 1; i++) {queue.offer(queue.poll());}}public int pop() {return queue.poll();}public int top() {return queue.peek();}public boolean empty() {return queue.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/
// @lc code=end

有效的括号

左边括号压入栈，成对弹出，最后栈为空则为有效括号

/** @lc app=leetcode.cn id=20 lang=java** [20] 有效的括号*/// @lc code=startimport java.util.Stack;class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {char temp = s.charAt(i);if (temp == '(' || temp == '[' || temp == '{') {stack.push(temp);} else if (temp == ')') {if (stack.isEmpty() || stack.pop() != '(') {return false;}} else if (temp == ']') {if (stack.isEmpty() || stack.pop() != '[') {return false;}} else if (temp == '}') {if (stack.isEmpty() || stack.pop() != '{') {return false;}}}return stack.isEmpty();}
}
// @lc code=end

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

主要还是对Java的字符串工具不熟

/** @lc app=leetcode.cn id=1047 lang=java** [1047] 删除字符串中的所有相邻重复项*/// @lc code=startimport java.util.Stack;class Solution {public String removeDuplicates(String s) {Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {char current = s.charAt(i);if (!stack.isEmpty() && current == stack.peek()) {stack.pop();} else {stack.push(current);}}StringBuilder result = new StringBuilder();for (char c : stack) {result.append(c);}return result.toString();}
}
// @lc code=end