代码随想录打卡第10天

232 用队列实现栈

两个栈一个负责入一个负责出。

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() {moveStackIn();return stackOut.pop();}public int peek() {moveStackIn();return stackOut.peek();}public boolean empty() {return stackIn.isEmpty() && stackOut.isEmpty();}public void moveStackIn(){if(!stackOut.isEmpty()) return;while(!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}
}

225 用队列实现栈

使用两个队列，第二个队列充当的是备份的作用

class MyStack {// q1作为主要的队列，其元素排列顺序和出栈顺序相同Queue<Integer> que1 = new ArrayDeque<>();// q2仅作为临时放置Queue<Integer> que2 = new ArrayDeque<>();public MyStack() {}public void push(int x) {while (que1.size() > 0) {que2.add(que1.poll());}que1.add(x);while (que2.size() > 0) {que1.add(que2.poll());}}public int pop() {return que1.poll();}public int top() {return que1.peek();}public boolean empty() {return que1.isEmpty();}
}

20 有效的括号

栈的经典题，要想好不匹配的情况

先将与左边匹配的右边括号放入栈中，如果遇到右边括号，则对比栈顶是否相同，如果相同则弹出，如果不同则返回false

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

1047 删除字符串中重复的元素

注意栈是用来存放的，还有p拼接字符串的字符顺序

class Solution {public String removeDuplicates(String s) {// ArrayDeque会比LinkedList在除了删除元素这一点外会快一点ArrayDeque<Character> que = new ArrayDeque<>();char ch;for (int i = 0; i < s.length(); i++) {ch = s.charAt(i);if (que.isEmpty() || ch != que.peek()) {que.push(ch);} else {que.pop();}}String res = "";while (!que.isEmpty()) {res = que.pop()+res;//注意顺序}return res;}
}