232.用栈实现队列

• 用两个栈来实现
• 当pop时，检测out栈是否为空，若为空，则将in栈的元素全都放入out栈中

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

225. 用队列实现栈

• 单个队列方法
• 将前面n-1个元素弹出并加入底部，这样就可以模拟后进先出

class MyStack {// 用单个队列// 将前面n-1个元素弹出并加入底部private Queue<Integer> a;public MyStack() {a = new LinkedList<>();}public void push(int x) {// size-1int n = a.size();a.offer(x);while (n > 0) {a.offer(a.poll());n--;}}public int pop() {return a.poll();}public int top() {return a.peek();}public boolean empty() {return a.isEmpty();}
}

20. 有效的括号

public boolean isValid(String s) {// 输入：s = "()[]{}"//输出：trueHashMap<Character,Character> map = new HashMap<>();map.put('(',')');map.put('[',']');map.put('{','}');Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);if (ch == '(' || ch == '{' || ch == '[') {stack.push(map.get(ch));}// [()]// ])else if (stack.isEmpty() || ch != stack.pop()) {return false;}}// ([return stack.isEmpty();
}

• Deque和Stack栈

public boolean isValid(String s) {// 输入：s = "()[]{}"//输出：trueHashMap<Character,Character> map = new HashMap<>();map.put('(',')');map.put('[',']');map.put('{','}');Deque<Character> stack = new LinkedList<>();for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);if (ch == '(' || ch == '{' || ch == '[') {stack.push(map.get(ch));}// [()]// ])else if (stack.isEmpty() || ch != stack.pop()) {return false;}}// ([return stack.isEmpty();
}

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

• 要知道栈为什么适合做这种类似于爱消除的操作，因为栈帮助我们记录了 遍历数组当前元素时候，前一个元素是什么

public String removeDuplicates(String s) {// 输入："abbaca"//输出："ca"Deque<Character> stack = new LinkedList<>();for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);if (stack.isEmpty()) {stack.push(ch);continue;} else if (ch == stack.peek()) {stack.pop();continue;}stack.push(ch);}StringBuilder sb = new StringBuilder();while (!stack.isEmpty()) {sb.append(stack.pop());}return sb.reverse().toString();
}

150. 逆波兰表达式求值

public static int evalRPN(String[] tokens) {Deque<Integer> stack = new LinkedList<>();for (String token : tokens) {switch (token){case "+":stack.push(stack.pop()+stack.pop());break;case "-":stack.push(-1*(stack.pop()-stack.pop()));break;case "*":stack.push(stack.pop()*stack.pop());break;case "/":int a = stack.pop();int b = stack.pop();stack.push(b/a);break;default:stack.push(Integer.parseInt(token));}}return stack.pop();
}