如何用栈实现队列

2021-05-17  本文已影响0人  CXY_XZL

1.简知

栈:先入后出,队列:先进先出


2.解题思路

1.使用两个栈,假设为栈A和栈B;
2.有入栈操作时,让元素入栈A;
3.当元素要出栈时,将栈A的元素压入栈B,此时栈B中元素的出栈顺序是和队列相同的;
4.当又有元素要入栈时,再将栈B中的元素压入到栈A,然后将要入栈的元素压入到栈A;
5.总之,栈A负责实现队列的入队操作,栈B实现队列的出队操作;


3.实现代码

public class StackToQueue {
    private Stack<Integer> stackA = new Stack<Integer>();
    private Stack<Integer> stackB = new Stack<Integer>();

    /**
     * 入队操作
     * @param element 入队的元素
     */
    public void enQueue(int element){
        stackA.push(element);
    }

    /**
     * 出队的元素
     */
    public Integer deQueue(){
        if (stackB.isEmpty()){
            if (stackA.isEmpty()){
                return null;
            }
            transfer();
        }
        return stackB.pop();
    }

    /**
     * 栈A的元素转移到栈B
     */
    private void transfer(){
        while (!stackA.isEmpty()){
            stackB.push(stackA.pop());
        }
    }

    public static void main(String[] args) {
        StackToQueue stackToQueue = new StackToQueue();
        stackToQueue.enQueue(1);
        stackToQueue.enQueue(2);
        stackToQueue.enQueue(3);
        System.out.println(stackToQueue.deQueue());
        System.out.println(stackToQueue.deQueue());
        stackToQueue.enQueue(4);
        System.out.println(stackToQueue.deQueue());
        System.out.println(stackToQueue.deQueue());

    }
}
上一篇 下一篇

猜你喜欢

热点阅读