双队列实现栈？双栈实现队列？

双队列实现栈

单个队列是无法实现栈的，双队列是可以的，如下分析（例如出栈）

 

 

注意：

• 哪个队列不为空就放入哪个将元素放入哪个队列
• 若两个都为空，任选一个队列放入即可 

如下代码：

class MyStack {
    public Queue<Integer> q1;
    public Queue<Integer> q2;
    public int usedSize;
    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    //压栈
    public void push(int x) {
        //哪个队列不为空，往那里里面放，都为空就放q1
        if(!q1.isEmpty()){
            q1.offer(x);
        }
        else if(!q2.isEmpty()){
            q2.offer(x);
        }
        else{
            q1.offer(x);
        }
        usedSize++;
    }
    //出栈
    public int pop() {
        //哪个队列不为空，就从哪里取元素放到另一个队列里
        if(empty()){
            return -1;
        }
        if(!q1.isEmpty()){
            //转移usedSize - 1个元素到另一个队列
            //for(int i = 0; i < usedSize - 1; i++)//不能这样写，usedSize会随着出栈不断减少
            int size = usedSize;
            for(int i = 0; i < size - 1; i++){
                q2.offer(q1.poll());
            }
            usedSize--;
            return q1.poll();
        }
        else{
            int size = usedSize;
            for(int i = 0; i < size - 1; i++){
                q1.offer(q2.poll());
            }
            usedSize--;
            return q2.poll();
        }
    }
    
    public int top() {
        //哪个队列不为空，就从哪里取元素放到另一个队列里
        if(empty()){
            return -1;
        }
        int tmp = 0;
        if(!q1.isEmpty()){
            int size = usedSize;
            for(int i = 0; i < size - 1; i++){
                q2.offer(q1.poll());
            }
            tmp = q1.peek();
            q2.offer(q1.poll());
        }
        else{
            int size = usedSize;
            for(int i = 0; i < size - 1; i++){
                q1.offer(q2.poll());
            }
            tmp = q2.peek();
            q1.offer(q2.poll());
        }
        return tmp;
    }
    //判空
    public boolean empty() {
        return usedSize == 0;
    }
}

---

双栈实现队列

单个栈是无法实现队列的，双栈是可以的，如下分析（例如出队）

 

 

 

 注意：

• 出队之前一定要先检查s2中是否有元素，若有直接弹出即可，若没有再将s1全部压入s2中
• 检查队列首元素也是如此(peek)

代码如下：

class MyQueue {
    public Stack<Integer> s1;//入栈
    public Stack<Integer> s2;//出栈
    public MyQueue() {
        this.s1 = new Stack<>();
        this.s2 = new Stack<>();
    }
    //进队
    public void push(int x) {
        s1.push(x);
    }
    //出队
    public int pop() {
        if(empty()) {
            return -1;
        }
        //s2如同蓄水池，一旦要出队列，就全压s1
        //前提一定要是s2为空！若不为空，再压入s2，顺序就不一样！
        if(s2.empty()){
            while(!s1.empty()) {
                s2.push(s1.pop());
            }
            return s2.pop();
        }
        //如果s2里有元素，就直接弹出
        return s2.pop();
    }
    public int peek() {
        if(empty()) {
            return -1;
        }
        //s2如同蓄水池，一旦要出队列，就全压s1
        //前提一定要是s2为空！若不为空，再压入s2，顺序就不一样！
        if(s2.empty()){
            while(!s1.empty()) {
                s2.push(s1.pop());
            }
            return s2.peek();
        }
        //如果s2里有元素，就直接弹出
        return s2.peek();
    }
    
    public boolean empty() {
        return s1.empty() && s2.empty();
    }
}

---