【剑指offer】8.用两个栈实现队列

2021年11月25日 阅读数:3
这篇文章主要向大家介绍【剑指offer】8.用两个栈实现队列,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
8.用两个栈实现队列

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

示例 1:app

输入:ide

[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”]函数

[[],[3],[],[]]oop

输出:[null,null,3,-1]spa

th:用两个栈,一个栈push数据 另外一个栈pop数据code

输入数据 1 2 3 push进inStack 为 3 2 1 在pop到outStack栈中 为1 2 3 和输入数据顺序同样、队列

复杂度分析

插入元素

时间复杂度:O(1) 一次push操做
空间复杂度:O(1) 一个存储空间it

删除元素

时间复杂度:O(n) 数据从inStack到OutStack栈 loop一次。
空间复杂度:O(n)class

   /*
        * 用两个栈,一个栈push数据 另外一个栈pop数据
        输入数据 1 2 3 push进inStack 为  3 2 1 在pop到outStack栈中 为1 2 3 和输入数据顺序同样、
        */
        Stack<Integer> in;
        Stack<Integer> out;
        public CQueue() {
            in = new Stack();
            out = new Stack();
        }
        
        public void appendTail(int value) {
            in.push(value);
        }
        
        public int deleteHead() {
            if(out.empty()){
                while(!in.empty()){
                    out.push(in.pop());;
                }
            }
    
            if(out.empty()){
                return -1;
            }
    
            return out.pop();
        }