LeetCode 225：用队列实现栈 Implement Stack using Queues

AlanKeene 发布于2019-08-19 10:28 / 1314人阅读

摘要：下面是入栈时代码获得队列长度反转次数为队列长度减一反转语言没有栈和队列数据结构，只能用数组或双端队列实现。这类编程语言就压根不需要用队列实现栈或用栈实现队列这种问题，因为栈和队列本身就必须借助实现。

题目：

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

push(x) -- 元素 x 入栈

pop() -- 移除栈顶元素

top() -- 获取栈顶元素

empty() -- 返回栈是否为空

Implement the following operations of a stack using queues.

push(x) -- Push element x onto stack.

pop() -- Removes the element on top of the stack.

top() -- Get the top element.

empty() -- Return whether the stack is empty.

示例:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // 返回 2
stack.pop();   // 返回 2
stack.empty(); // 返回 false

注意:

你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。

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

你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）

Notes:

You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.

Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.

You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

解题思路：

方法一（两个队列）：

队列先进后出，栈后进先出。用队列实现栈，可以用两个队列完成题解：

出入栈：

入栈时用 queue1 来存入节点；出栈时queue1 内节点顺序出队列并入队列到 queue2，直到queue1剩最后一个元素时即为栈顶元素，弹出即可；

取栈顶元素：

用一个 top 指针一直指向栈顶元素，top() 方法查询栈顶元素时直接返回 top 指针即可。

方法二（一个队列）：

只用一个队列，只需要在入栈时反转队列即可：

入栈存入到队列queue

节点1入栈：queue：1
反转队列0次：queue：1

节点2入栈queue：1->2
反转队列1次：
queue：1->2 --> queue：2->1

节点2入栈queue：2->1->3
反转队列2次：
queue：2->1->3 ---> queue：1->3->2 ---> queue：3->2->1

......

这样不管什么时候出队顺序都是按照出栈的顺序。

Java：

方法一

class MyStack {
    Queue queue1;
    Queue queue2;
    private int top;//指向栈顶元素

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        queue1.offer(x);
        top = x;//新加入元素为栈顶元素
    }

    public int pop() {
        while (queue1.size() > 1) {//条件为队列1的元素个数大于一
            top = queue1.poll();//用top暂存元素，当循环结束时，top刚好是栈顶元素
            queue2.add(top);
        }
        //队列1与队列2交换
        Queue tmp = queue2;
        queue2 = queue1;
        queue1 = tmp;
        return queue2.poll();//返回队列2的队列头元素，队列2也只有一个元素
    }

    public int top() {
        return top;
    }

    public boolean empty() {
        return queue1.isEmpty();//队列1决定了栈是否为空
    }
}

方法二：

每次入队时反转队列即可，只有入栈需要特殊操作，出栈、取栈顶元素、是否空都按照队列正常出队列、取队列头元素、是否空方法操作。下面是入栈时代码：

Queue queue = new LinkedList<>();

public void push(int x) {
    queue.add(x);
    int sz = queue.size();//获得队列长度
    while (sz > 1) {//反转次数为队列长度减一
        queue.add(queue.remove());//反转
        sz--;
    }
}

Python：

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

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

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

class MyStack:

    def __init__(self):
        self.stack = []

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

    def pop(self) -> int:
        return self.stack.pop(-1)

    def top(self) -> int:
        return self.stack[-1]

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

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

专线服务云服务器 java 栈队列 java 栈队列面试 python实现栈队列实现原理

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

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

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] Implement Stack using Queues 用队列实现栈

摘要：双队列法复杂度时间空间思路和类似，我们也可以用两个队列来模拟栈的操作。当时，我们将数字进非空的队列就行了。操作和一样，区别在于我们拿到最后一个数后，还要再把它进另一个队列中。双队列法复杂度时间 O(N) 空间 O(N) 思路和Implement Queue using Stack类似，我们也可以用两个队列来模拟栈的操作。当push时，我们将数字offer进非空的队列就行了。当p...

ivan_qhz 2019-08-14 12:39 评论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 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

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

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

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