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

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

作者: 历十九喵喵喵 | 来源:发表于2020-07-01 03:30 被阅读0次

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


    思路:创建两个栈,一个实现队列的 插入操作,一个实现队列的 删除操作。、

    如何实现?首先明白,栈是先进后出,队列是先进先出。

    队列进行插入操作时,相当于进栈,队列进行删除操作时,相当于删除栈中最底层的元素,此时需要把栈里面的元素全部弹出来放到第二个空白的栈中,这个第二个栈的第一个元素就是队列要删除的元素了。

    空有理论不行,实操的话又弱点,还是参考大佬的代码吧。

    实现:

    参考大佬的解法:

    class CQueue {

        LinkedList<Integer> A, B;

        public CQueue() {

            A = new LinkedList<Integer>();

            B = new LinkedList<Integer>();

        }

        public void appendTail(int value) {

            A.addLast(value);

        }

        public int deleteHead() {

            if(!B.isEmpty()) return B.removeLast();

            if(A.isEmpty()) return -1;

            while(!A.isEmpty())

                B.addLast(A.removeLast());

            return B.removeLast();

        }

    }

    作者:jyd

    链接:https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/solution/mian-shi-ti-09-yong-liang-ge-zhan-shi-xian-dui-l-2/

    来源:力扣(LeetCode)

    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    这里用  LinkedList 看作栈来使用,虽然我也不知道为什么, 我又去看查 了一下 LinkedList,它的源码定义是这样的:

    public class LinkedList<E>

            extends AbstractSequentialList<E>

            implements List<E>, Deque<E>, Cloneable, java.io.Serializable

    继承了 AbstractSequentialList, 实现了实现 List (列表)、Deque(双端队列、允许两头进,两头出)、Cloneable、Serializable。

    上面涉及的知识更复杂了,但是不重要,我们先看 它的一些方法的实现:

    添加方法:addLast(): 将指定元素添加到此列表的结尾

    移除方法:removeLast():移除并返回此列表的最后一个元素。

    相关文章

      网友评论

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

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