首页 > > 程序设计 > Java技术 >

如何用栈实现队列

2018-11-09 02:38:06来源：博客园阅读 ()

about 算法

项目介绍

工作之余，代码敲多了，停下来思考思考，会有异常不到的收获。。。只为更好的自己

如何用栈实现队列？

提示下：用一个栈肯定是没办法实现队列，但如果我们有两个栈呢?

分析：栈和队列的特性

栈是先进后出，FILO

出入元素都是在同一端（栈顶）

入栈

1540432924606.png

出栈

1540432988027.png
队列是先进先出，FIFO
出入元素是在不同的两端（队头和队尾）

入栈

1540433080831.png

出栈

1540433109205.png

思考：组装

让一个栈作为队列的入口，负责插入新元素；另外一个栈作为队列的出口，负责移除老元素。

如图所示

1540433258745.png

让栈A中的所有元素按顺序出栈，再按照出栈顺序压入栈B。

这样一来，元素从栈A弹出并压入栈B的顺序是3，2，1和当初进入栈A的顺序123是相反的，如图

1540433561742.png

1540433605060.png

此时让元素1 “出队”，也就是让元素1从栈B弹出

1540433651738.png

代码实现：

/**
 * @author sunyang
 * @date 2018/10/25 10:18
 */
public class StackImplQueue {

    /**
     * 定义两个栈来实现队列
     * 栈A 负责插入新元素
     * 栈B 负责移除老元素
     */
    private Stack<Integer> stackA = new Stack<>();
    private Stack<Integer> stackB = new Stack<>();

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

    /**
     *
     * 出队操作
     */
    public Integer deQueue(){
        if (stackB.isEmpty()){
            if (stackA.isEmpty()){
                return null;
            }
            fetchFormStackA();
        }

        return stackB.pop();
    }

    /**
     * 从stackA栈中拿到出栈元素压入栈B
     */
    private void fetchFormStackA() {
        while (!stackA.isEmpty()){
            stackB.push(stackA.pop());
        }
    }

    public static void main(String[] args) {
        StackImplQueue stackQueue = new StackImplQueue();
        stackQueue.enQueue(1);
        stackQueue.enQueue(2);
        stackQueue.enQueue(3);

        System.out.println(stackQueue.deQueue());
        System.out.println(stackQueue.deQueue());
        System.out.println(stackQueue.deQueue());

        stackQueue.enQueue(4);
        System.out.println(stackQueue.deQueue());


    }
}