面试题9: 用两个栈实现队列

9-1 用两个栈实现队列

import java.util.Stack;

/**
 * 分析:
 * 入队列: 往stack中压入即可  时间复杂度O(1)
 * 出队列: 判断stack是否为空-->
 *          为空: 将stack1全部弹栈, 压入stack2, 从stack2栈顶弹出
 *          不为空: 直接弹出
 *          均摊时间复杂度 O(1)
 */


public class A09_TwoStackImplQueue {
    // 内部类定义队列
    public static class MyQueue{
        private static Stack<Integer> stack1 = new Stack<>();
        private static Stack<Integer> stack2 = new Stack<>();

        public void push(int p){
            stack1.push(p);
        }

        public int pop() throws Exception {
            // 如果两个栈都为空 抛出异常
            if(stack1.isEmpty() && stack2.isEmpty()){
                throw new Exception("队列为空!");
            }

            if(stack2.isEmpty()){
                while(!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }
    }





    public static void main(String[] args) throws Exception {
        MyQueue queue = new MyQueue();
        queue.push(1);
        queue.push(2);
        queue.push(3);

        System.out.println(queue.pop());
        System.out.println(queue.pop());

        queue.push(4);
        System.out.println(queue.pop());
        System.out.println(queue.pop());


    }

}

9-2 用两个队列实现栈

package cn.zxy.interview;

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 要求:
 * 两个栈实现队列
 *
 * 压栈: 如果都空, 任选一个入队列; 如果一个为空, 入非空队列
 *
 * 弹栈: 如果都为空, 抛异常
 *      选择非空的队列, 将元素依次出队列, 拿到最后一个删除
 *
 *      如何拿到最后一个? 代码
 *
 */


public class A09_TwoQueueImplStack {
    private static class MyStack{
        private Queue<Integer> queue1 = new LinkedList<>();
        private Queue<Integer> queue2 = new LinkedList<>();

        private void push(int p){
            // 选择一个非空队列
            Queue<Integer> queue = queue1.isEmpty() ? queue2 : queue1;
            queue.add(p);
        }

        private int pop() throws Exception {
            // 都为空, 抛出异常
            if(queue1.isEmpty() && queue2.isEmpty()){
                throw new Exception("栈为空!");
            }

            // 确定非空队列
            Queue<Integer> queuePop = null;
            Queue<Integer> queuePush = null;
            if(queue1.isEmpty()){
                queuePop = queue2;
                queuePush = queue1;
            }else{
                queuePop = queue1;
                queuePush = queue2;
            }

            int value = -1;
            while(!queuePop.isEmpty()){
                value = queuePop.remove();
                // 如果弹出后某个元素后, Queue为空, 说明是最后一个, 不再push
                if(queuePop.isEmpty()){
                    break;
                }else{
                    queuePush.add(value);
                }
            }
            return value;
        }
    }

    public static void main(String[] args) throws Exception {
        MyStack stack = new MyStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println(stack.pop());
        System.out.println(stack.pop());

        stack.push(4);
        System.out.println(stack.pop());
        System.out.println(stack.pop());

    }

}