用栈实现队列
link：232. 用栈实现队列 - 力扣（LeetCode）
思路分析
首先理清楚栈和队列的异同.
队列是先进先出 栈先进后出【两者都能存储元素】
再来看peek()和poll().
栈和队列都有peek() 可以称之为“瞄一眼”只是看一下当前栈顶/队头元素是什么.
栈中的pop()直接返回栈顶元素（出栈）
队列中的poll()在某种层面上就等效于pop()了.
先用栈1存储所有元素 再逐个pop到栈2中
最后pop栈2全部元素.
注意判断栈满（是否需要扩容）
class MyQueue {private Stack<Integer> stack1;private Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}//数据全部存在stack1中public void push(int x) {stack1.push(x);}public int pop() {//特殊 两者都为空if(empty()){return -1;}//先判断空 stack2不为空直接pop 统一从stack2出if(stack2.empty()){while(!stack1.empty()){//将stack1中的元素传到stack2中stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {//特殊 两者都为空if(empty()){return -1;}//先判断空 stack2不为空直接pop 统一从stack2出if(stack2.empty()){while(!stack1.empty()){//将stack1中的元素传到stack2中stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.empty() && stack2.empty();}
}
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() {dumpstackIn();return stackOut.pop();}public int peek() {dumpstackIn();return stackOut.peek();}public boolean empty() {return stackIn.isEmpty() && stackOut.isEmpty();}private void dumpstackIn() {if(!stackOut.isEmpty()) {return;}while(!stackIn.isEmpty()) {stackOut.push(stackIn.pop());}}
}/*** 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();*/
用队列实现栈
link：225. 用队列实现栈 - 力扣（LeetCode）
思路分析
由于队列是先进先出 想要模拟栈第二个队列就是起到备份的作用.
我们要获取q1最后入列的元素 那么就需要q2中间搭桥：
双队列解决
class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>(); }public void push(int x) {queue2.offer(x);while(!queue1.isEmpty()){queue2.add(queue1.poll());//其实在无容量限制的情况下保持一致使用offer或者add}Queue<Integer> temp = new LinkedList<>();temp = queue1;queue1 = queue2;queue2 = temp; }public int pop() {return queue1.poll();}public int top() {return queue1.peek();}public boolean empty() {return queue1.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();*/
Question
在 push 方法中，使用 offer 和 add 都可以将元素插入到 queue2 中，但这两者有细微的区别。下面是解释为什么这里使用了 add 和 offer：
区别
offer(E e)：用于将元素插入到队列的尾部。如果队列有容量限制（如在阻塞队列中），而队列已满，offer会返回false，表示添加失败。add(E e)：同样将元素插入到队列的尾部，但如果队列已满（有容量限制时），add会抛出IllegalStateException。
在 MyStack 实现中，因为使用的是 LinkedList 作为队列的底层实现，LinkedList 本身没有容量限制，所以在实际操作中 add 和 offer 的行为是相同的。
为什么 push 中既使用了 offer 又使用了 add
offer用于将新元素x加入queue2。这是因为这个元素是新插入的，并且它是我们希望最终在栈顶部的元素。add用于将queue1中剩余的所有元素移动到queue2。在这个上下文中，queue1.poll()会将queue1的元素逐个取出并添加到queue2。这里使用add或offer都没有影响，因为LinkedList没有容量限制。
单队列解决
其实最开始思考用队列实现栈把末尾入队的元素放到队头即可 但是没有对知识点进行清晰的掌握 下附妙招.
Deque继承了Queue接口
Queue 中的 add、poll、peek等效于 Deque 中的 addLast、pollFirst、peekFirst
class MyStack {Deque<Integer> que1;public MyStack() {que1 = new ArrayDeque<>();}public void push(int x) {que1.addLast(x);}public int pop() {int tmp = que1.size()-1;while(tmp>0){que1.addLast(que1.peekFirst());que1.pollFirst();tmp--;}return que1.pollFirst();}public int top() {return que1.peekLast();}public boolean empty() {return que1.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();*/
.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();*/
