重点：

栈和队列

Java中

栈不建议用stack来实现

建议用 ArrayDeque和Linkedlist来实现

队列建议用ArrayDeque和Linkedlist来实现

两者效率比较：

java - Why is ArrayDeque better than LinkedList - Stack Overflow

基于Linkedlist是链表等，除了删除操作，ArrayDeque的其他效率都比Linkedlist好

一、[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() {if(!stackOut.isEmpty()){return stackOut.pop();}while(!stackIn.isEmpty()){stackOut.push(stackIn.pop());}return stackOut.pop();}public int peek() {if(!stackOut.isEmpty()){return stackOut.peek();}while(!stackIn.isEmpty()){stackOut.push(stackIn.pop());}return stackOut.peek();}public boolean empty() {if(stackIn.isEmpty()&&stackOut.isEmpty()){return true;}else{return false;}}
}

二、[225]用队列实现栈

重点：queue2 为辅助队列，只做中转用

class MyStack {LinkedList<Integer> queue1;LinkedList<Integer> queue2;public MyStack() {queue1=new LinkedList<>();//辅助队列queue2=new LinkedList<>();}public void push(int x) {queue2.offer(x);while(!queue1.isEmpty()){queue2.offer(queue1.pop());}//队列交换--注意一下！！！LinkedList<Integer> tmp=queue1;queue1=queue2;queue2=tmp;}public int pop() {return queue1.pop();}public int top() {return queue1.peek();}public boolean empty() {return queue1.isEmpty();}
}

三、[20]有效的括号

class Solution {public boolean isValid(String s) {Stack<String> stack=new Stack<>();for(int i=0;i<s.length();i++){if("(".equals(String.valueOf(s.charAt(i)))){stack.push(")");} else if ("{".equals(String.valueOf(s.charAt(i)))) {stack.push("}");} else if ("[".equals(String.valueOf(s.charAt(i)))) {stack.push("]");} else if (!stack.isEmpty()&&stack.peek().equals(String.valueOf(s.charAt(i)))) {stack.pop();}else {return false;}}//栈为空则符合条件return stack.isEmpty();}
}

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

重点：

反转栈中的字符串

方法一：

String str = "";
while (!deque.isEmpty()) {
str = deque.pop() + str;
}

方法二：

StringBuilder stringBuilder=new StringBuilder();
while(!stack.isEmpty()){
stringBuilder.append(stack.pop());
}
stringBuilder.reverse().toString();

class Solution {public String removeDuplicates(String s) {LinkedList<Character> stack=new LinkedList<>();char ch;for(int i=0;i<s.length();i++){ch=s.charAt(i);if(!stack.isEmpty()&&stack.peek()==ch){stack.pop();}else{stack.push(ch);}}StringBuilder stringBuilder=new StringBuilder();while(!stack.isEmpty()){stringBuilder.append(stack.pop());}/*** 这种做法很巧妙String str = "";while (!deque.isEmpty()) {str = deque.pop() + str;}*/return stringBuilder.reverse().toString();}
}