美文网首页
[剑指Offer]09.用两个栈实现队列

[剑指Offer]09.用两个栈实现队列

作者: 炭烧熊猫 | 来源:发表于2020-03-28 21:01 被阅读0次

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

    示例 1:

    输入:
    ["CQueue","appendTail","deleteHead","deleteHead"]
    [[],[3],[],[]]
    输出:[null,null,3,-1]
    示例 2:

    输入:
    ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
    [[],[],[5],[2],[],[]]
    输出:[null,-1,null,null,5,2]
    提示:

    1 <= values <= 10000
    最多会对 appendTail、deleteHead 进行 10000 次调用

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof

    解题思路
    挺有意思的一道题,说这个题有意思不是因为这个题的思路难,而是写了半天,发现忽略了好多小细节。因为队列是先进先出,而栈是先进后出,如果要用栈来实现队列,很容易就想到了用两个栈来回倒,入队就是向栈里压入元素,出队就是将整个栈压入另外一个栈,将栈底元素变成栈顶元素,再出栈。

    实现如下:

    class CQueue {
        Stack stackA;
        Stack stackB;
    
        boolean deleteHead;
        boolean appendTail;
    
        public CQueue() {
            stackA = new Stack();
            stackB = new Stack();
    
            appendTail = false;
            deleteHead = false;
        }
        
        public void appendTail(int value) {
            if(deleteHead){
                switchStack(stackA,stackB);        
            }
    
            if(!stackB.empty())
                stackB.push(value);
            else
                stackA.push(value); 
    
            appendTail = true;
            deleteHead = false;     
        }
        
        public int deleteHead() {
            if(appendTail){
                switchStack(stackA,stackB);
            }   
    
            appendTail = false;
            deleteHead = true;     
    
            if(stackA.empty() && !stackB.empty())
                return (Integer)stackB.pop();
    
            if(stackB.empty() && !stackA.empty())
                return (Integer)stackA.pop();
    
            return -1;
        }
    
        private void switchStack(Stack a, Stack b){
            if(!a.empty()){
                while(!a.empty()){
                    Integer value = (Integer) a.pop();
                    b.push(value);
                }
            } else if(!b.empty()){
                while(!b.empty()){
                    Integer value = (Integer) b.pop();
                    a.push(value);
                }
            }
            
        }
    }
    

    提交没问题,但是感觉写的很繁琐,是因为没有想清楚几个问题就动手了。

    1. Stack A 和Stack B 可以为固定的栈,即A永远用于进队,B用于出队而不是两个栈来回颠倒,所以appendTail 和 deleteHead 完全用不上。
    2. Stack 直接使用了java 类包 java.util.Stack, 可以显式给定数据类型,不需要后面再casting
    3. 提交后发现执行时间较慢,原因是使用的Stack是基于Vector的,有些人直接利用了LinkedList,时间效率一下子就提高了。
    4. 最后理解了一下Stack.pop() 和 peek()的区别,一个是栈顶元素出栈,后者是保留。

    改后的代码为

    class CQueue {
        Stack<Integer> in;
        Stack<Integer> out;
    
        public CQueue() {
            in = new Stack<>();
            out = new Stack<>();
        }
    
        public void appendTail(int value) {
            if(!out.empty())
               switchStack(out,in);
            in.push(value);
        }
    
        public int deleteHead() {
            if(!in.empty())
                switchStack(in,out);
    
            if(!out.empty())
                return out.pop();
    
            return -1;
        }
    
        private void switchStack(Stack a, Stack b){
            while(!a.empty()){
                Integer value = (Integer) a.pop();
                b.push(value);
            }
        }
    }
    

    其中switchStack 可以继续化简为

    b.push(a.pop());
    

    相关文章

      网友评论

          本文标题:[剑指Offer]09.用两个栈实现队列

          本文链接:https://www.haomeiwen.com/subject/uzasuhtx.html