剑指offer-5、两个栈实现⼀个队列

题⽬形貌

⽤两个栈来实现⼀个队列，完成队列的 Push 和 Pop 操作。 队列中的元素为 int 类型。
思路及解答

• 栈的特性是先辈后出
  
• 队列的特性是先辈先出
  

有两个栈 stack1 , stack2 ；

• 如果有新的数据进⼊，那么我们可以直接 push 到 stack1 ；
  
• 如果必要取出数据，那么我们优先取出 stack2 的数据，如果 stack2 ⾥⾯数据是空的，那么我们必要把所有的 stack1 的数据倒⼊ stack2 。再从 stack2 取数据。
  

比方：

• push 1 --> push 2
  

• pop 1
  

• push 3 --> push 4
  

• pop 2
  

1. import java.util.Stack;
3. public class Solution {
5.     Stack<Integer> stackIn;
6.     Stack<Integer> stackOut;
8.     /** Initialize your data structure here. */
9.     public MyQueue() {
10.         stackIn = new Stack<>(); // 负责进栈
11.         stackOut = new Stack<>(); // 负责出栈
12.     }
13.    
14.     /** Push element x to the back of queue. */
15.     public void push(int x) {
16.         stackIn.push(x);
17.     }
18.    
19.     /** Removes the element from in front of queue and returns that element. */
20.     public int pop() {   
21.         dumpstackIn();
22.         return stackOut.pop();
23.     }
24.    
25.     /** Get the front element. */
26.     public int peek() {
27.         dumpstackIn();
28.         return stackOut.peek();
29.     }
30.    
31.     /** Returns whether the queue is empty. */
32.     public boolean empty() {
33.         return stackIn.isEmpty() && stackOut.isEmpty();
34.     }
36.     // 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中
37.     private void dumpstackIn(){
38.         if (!stackOut.isEmpty()) return;
39.         while (!stackIn.isEmpty()){
40.                 stackOut.push(stackIn.pop());
41.         }
42.     }
43. }

复制代码

扩展-两个队列实现栈

队列是先辈先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先辈后出的顺序。
所以用栈实现队列， 和用队列实现栈的思路还是不一样的，这取决于这两个数据结构的性子。
但是依然还是要用两个队列来模拟栈，只不外没有输入和输出的关系，而是另一个队列完全用来备份的！

1. class MyStack {
3.     Queue<Integer> queue1; // 和栈中保持一样元素的队列
4.     Queue<Integer> queue2; // 辅助队列
6.     /** Initialize your data structure here. */
7.     public MyStack() {
8.         queue1 = new LinkedList<>();
9.         queue2 = new LinkedList<>();
10.     }
11.    
12.     /** Push element x onto stack. */
13.     public void push(int x) {
14.         queue2.offer(x); // 先放在辅助队列中
15.         while (!queue1.isEmpty()){
16.             queue2.offer(queue1.poll());
17.         }
18.         Queue<Integer> queueTemp;
19.         queueTemp = queue1;
20.         queue1 = queue2;
21.         queue2 = queueTemp; // 最后交换queue1和queue2，将元素都放到queue1中
22.     }
23.    
24.     /** Removes the element on top of the stack and returns that element. */
25.     public int pop() {
26.         return queue1.poll(); // 因为queue1中的元素和栈中的保持一致，所以这个和下面两个的操作只看queue1即可
27.     }
28.    
29.     /** Get the top element. */
30.     public int top() {
31.         return queue1.peek();
32.     }
33.    
34.     /** Returns whether the stack is empty. */
35.     public boolean empty() {
36.         return queue1.isEmpty();
37.     }
38. }

复制代码

• 时间复杂度: pop为O(n)，其他为O(1)
  
• 空间复杂度: O(n)
  

优化：
其实这道题目就是用一个队列就够了。
一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。

1. class MyStack {
2.     Queue<Integer> queue;
3.    
4.     public MyStack() {
5.         queue = new LinkedList<>();
6.     }
7.    
8.     public void push(int x) {
9.         queue.add(x);
10.     }
11.    
12.     public int pop() {
13.         rePosition();
14.         return queue.poll();
15.     }
16.    
17.     public int top() {
18.         rePosition();
19.         int result = queue.poll();
20.         queue.add(result);
21.         return result;
22.     }
23.    
24.     public boolean empty() {
25.         return queue.isEmpty();
26.     }
28.     public void rePosition(){
29.         int size = queue.size();
30.         size--;
31.         while(size-->0)
32.             queue.add(queue.poll());
33.     }
34. }

复制代码

• 时间复杂度: pop为O(n)，其他为O(1)
  
• 空间复杂度: O(n)