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

cloud 发布于2019-08-19 10:26 / 2465人阅读

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

题目：

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。

pop() -- 从队列首部移除元素。

peek() -- 返回队列首部的元素。

empty() -- 返回队列是否为空。

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.

示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:

你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）。

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).

解题思路：

队列先进后出，栈后进先出。用栈实现队列，可以用两个栈完成题解。入队列时用 stack1 存入节点，出队列时 stack1 内节点顺序出栈压入 stack2 中。

例如 1, 2, 3 元素顺序入队列 
即存入栈stack1：[1, 2, 3]

出队列时顺序应为：1->2->3
但是栈先进先出，出栈顺序为：3->2->1
与出队列顺序不相符

借助另一个栈stack2
stack1内的元素顺序出栈并压入stack2
stack1：[1, 2, 3] ---> stack2：[3, 2, 1]
此时stack2出栈顺序：1->2->3
与出队列顺序相符

注意：在出队列时无需着急将 stack1 中的节点顺序压入 stack2。因为要实现的队列是先进后出，可以将 stack2 中的节点全部弹出之后再将 stack1 内节点顺序压入stack2，这样可以将出栈的时间复杂度摊还到 O(1)。

Java：

class MyQueue {
    private Stack stack1;
    private Stack stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek() {
        //stack1节点顺序弹出并压入stack2
        if (stack2.isEmpty()) {//条件是: stack2为空,而不是stack1非空, 这样摊还复杂度O(1)
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());//stack1弹出节点并压入stack2
            }
        }
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

Python：

Python语言没有栈和队列数据结构，只能用数组 List 或双端队列 deque 实现。

这类编程语言就压根不需要用队列实现栈或用栈实现队列这种问题，因为栈和队列本身就必须借助List、deque实现。

所以这道题在这种语言中这就非常简单了，可以说是作弊。

class MyQueue:
    def __init__(self):
        self.queue = []

    def push(self, x: int) -> None:
        self.queue.append(x)

    def pop(self) -> int:
        #弹出第一个元素
        return self.queue.pop(0)

    def peek(self) -> int:
        #返回第一个元素
        return self.queue[0]

    def empty(self) -> bool:
        return not self.queue

欢迎关注微.信公.众号：爱写Bug

GPU云服务器云服务器队列queue 队列实现原理消息队列实现 python队列实现

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

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

[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
leetcode232 Implement Queue using Stacks

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

golden_hamster 2019-08-15 13:32 评论0 收藏0
前端 | 每天一个 LeetCode

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

张汉庆 2019-08-23 13:42 评论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 225：用队列实现栈 Implement Stack using Queues

摘要：下面是入栈时代码获得队列长度反转次数为队列长度减一反转语言没有栈和队列数据结构，只能用数组或双端队列实现。这类编程语言就压根不需要用队列实现栈或用栈实现队列这种问题，因为栈和队列本身就必须借助实现。题目：使用队列实现栈的下列操作： push(x) -- 元素 x 入栈 pop() -- 移除栈顶元素 top() -- 获取栈顶元素 empty() -- 返回栈是否为空 Impl...

AlanKeene 2019-08-19 10:28 评论0 收藏0