剑指offer 利用两个栈实现一个队列

剑指offer60天计划

Posted by liuwenzi on July 24, 2020
阅读数:

利用两个栈实现一个队列

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

题解

  • 一个栈负责del,一个栈负责接收push的值。

    • 当del的时候,如del栈为空,将push栈的内容pop出来,并压入到del栈中

    • 否则,直接将del栈中的内容弹出

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    
    class CQueue {
        private Stack<Integer> pushStack;
        private Stack<Integer> popStack;
        public CQueue() {
            pushStack = new Stack();
            popStack = new Stack();
        }
          
        public void appendTail(int value) {
            pushStack.push(value);
        }
          
        public int deleteHead() {
            if(popStack.size() == 0){
                while(pushStack.size() != 0){
                    popStack.push(pushStack.pop());
                }
            }
            if(popStack.size() == 0){
                return -1;
            }
            return popStack.pop();
        }
    }
      
    /**
     * Your CQueue object will be instantiated and called as such:
     * CQueue obj = new CQueue();
     * obj.appendTail(value);
     * int param_2 = obj.deleteHead();
     */
    

    AqAQkZ

总结

栈:先进后出

队列:先进先出

将内容入栈,在弹出并压入到另一个栈,此时另一个栈出栈顺序就是队列的出队顺序。