leetcode232 Implement Queue using Stacks

golden_hamster 发布于2019-08-15 13:32 / 2400人阅读

摘要：题目要求通过队列实现一个栈的功能。栈的为压入栈顶，出栈，栈顶元素，栈是否为空。重复上述的操作。但是当需要弹出元素时，则从桶弹出。这样，下次加入的元素必然全部位于桶后的所有元素，而桶中的元素也能保证位输入顺序。极大的减少了不必要的入栈出栈。

题目要求

Implement the following operations of a queue using stacks.

push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
Notes:
You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

通过队列实现一个栈的功能。栈的api为push（压入栈顶），pop（出栈），peek（栈顶元素），empty（栈是否为空）。这道题和之前的使用栈实现队列功能是类似的，可以参考我的这篇博客。

思路与代码

因为栈本质上是将输入的元素逆序输出，因此如果我们通过两个栈对输入的元素进行两次逆序操作就可以保证按照最初的顺序输出。那么什么时候进行逆序的操作呢？

思路一：倒入再倒回。
将栈想象为两个桶，每次我都想获得第一个桶中最底下的东西，因此我将第一个桶倒入第二个桶，这时原来在第一个桶底的元素就在第二个桶的最上面。取完第二个桶中的内容后，我再把东西倒回。这样每次都只需要往第一个桶里面添加新元素，如果想要获得第一个桶桶底的元素，就把它倒到第二个桶里面去。重复上述的操作。图示如下：

1.输入[1,2,3,4,5]

2.获得捅底的元素1，则将1号桶导入2号桶，获取元素后再倒回

3.输入[6]

4.获得当前捅底的元素2，那么操作同第二步

这个方法其实增加许多不需要的倒出倒入操作，那么有没有可能我们只在需要的时候对这么大的数据量进行倒入倒出操作呢？

思路二：多次加入，一次倒出
从上一个例子我们可以看见，桶1中的内容一定是输入顺序的逆序，而桶2中的内容则一定和输入顺序相同。那么我们能不能保证无时无刻，桶1中的元素全部位于桶2之后，从而确保每次从桶2中获得的元素是正确的顺序。而当桶2中没有元素时，只要导入桶1的元素就可以了。

方法是每次添入元素时，仍然直接加入桶1。但是当需要弹出元素时，则从桶2弹出。如果桶2是空的话，那么就把桶1中的内容倒入桶2。这样，下次加入的元素必然全部位于桶2后的所有元素，而桶2中的元素也能保证位输入顺序。图例如下：

1.输入[1,2,3,4,5]

2.弹出1

3.弹出2

4.输入[6,7]

这样我们确保了每个元素只会入栈出栈再入栈出栈两次，即进入桶1，弹出桶1，进入桶2，弹出桶2。极大的减少了不必要的入栈出栈。代码如下：

public class ImplementQueueusingStacks_232 {
    Stack s1 = new Stack();
    Stack s2 = new Stack();
    /** Push element x to the back of queue. */
    public void push(int x) {
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(s2.isEmpty()){
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        if(s2.isEmpty()){
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return s1.empty() && s2.empty();
    }
}

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

GPU云服务器云服务器 Implement Stacks Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68155.html

LeetCode 232：用栈实现队列 Implement Queue using Stacks

摘要：题目使用栈实现队列的下列操作将一个元素放入队列的尾部。用栈实现队列，可以用两个栈完成题解。入队列时用存入节点，出队列时内节点顺序出栈压入中。这类编程语言就压根不需要用队列实现栈或用栈实现队列这种问题，因为栈和队列本身就必须借助实现。题目：使用栈实现队列的下列操作： push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队...

cloud 2019-08-19 10:26 评论0 收藏0
[Leetcode] Implement Queue using Stacks 用栈实现队列

摘要：注意的方法是和，实际上我们应该实现的是和或者和，的实现和是一样的，但将改为时，我们要先把到的元素保存，然后再弹出输出栈，然后返回这个保存的元素。 Implement Queue using Stacks Implement the following operations of a queue using stacks. push(x) -- Push element x to th...

Martin91 2019-08-14 12:29 评论0 收藏0
leetcode225 implement stack using queues

摘要：题目要求使用队列来模拟实现一个栈。栈是指先进后出的数据结构，而队列则是先进先出的数据结构。队列的包括在队列尾插入数据，输出队列头的数据，查看队列的长度，队列是否为空。题目要求 Implement the following operations of a queue using stacks. push(x) -- Push element x to the back of que...

binta 2019-08-15 13:30 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0