剑指offer：用两个栈实现队列用两个队列实现栈

曾经终败给现在 2021-09-16 06:30 402阅读 0赞

**试题：**  
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。  
**代码：**  
首先显然要有个stack用来push，由于stack的后进后出原则，要想实现队列的先进先出功能就需要第二个stack将第一个stack中的数据重新压一遍进行反序。

import java.util.Stack;
    
    public class Solution {
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        
        public void push(int node) {
            stack1.push(node);
        }
        
        public int pop() {
            if(stack2.empty()){
                while(!stack1.empty()){
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }
    }

**用两个队列实现栈**

Version A (efficient push):
    
    push:
    enqueue in queue1
    pop:
    while size of queue1 is bigger than 1, pipe dequeued items from queue1 into queue2
    dequeue and return the last item of queue1, then switch the names of queue1 and queue2
    Version B (efficient pop):
    
    push:
    enqueue in queue2
    enqueue all items of queue1 in queue2, then switch the names of queue1 and queue2
    pop:
    deqeue from queue1

[代码来源][Link 1]

class Stack2
        {
            private Queue<int> q1;
            private Queue<int> q2;
     
            public Stack2()
            {
                q1 = new Queue<int>();
                q2 = new Queue<int>();
            }
            public void Push(int x)
            {
                q1.Enqueue(x);                                                                                                                                                                                                                                
            }
            public int Pop()
            {
                if (q1.Count == 0)
                {
                    if (q2.Count == 0)
                    {
                        throw new Exception("为空");
                    }
                    else
                    {
                        while (q2.Count > 1)
                        {
                            q1.Enqueue(q2.Dequeue());
                        }
                        return q2.Dequeue();//出队
                    }
                    
                }
                while (q1.Count > 1)
                {
                    q2.Enqueue(q1.Dequeue());
                }
                return q1.Dequeue();//出队
            }
        }

[Link 1]: https://blog.csdn.net/mumeiliuli/article/details/78252433