如何用栈实现队列

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());


    }
}

打印结果

 

1540435153368.png

 

题外话：时间复杂度

入栈操作的时间复杂度显然是o(1)

出栈操作的时间复杂度如果发生转移的话就是o（n）

如果没有发生转移的话也是o（1）