[Leetcode] Implement Queue using Stacks 用栈实现队列

Martin91 发布于2019-08-14 12:29 / 2343人阅读

摘要：注意的方法是和，实际上我们应该实现的是和或者和，的实现和是一样的，但将改为时，我们要先把到的元素保存，然后再弹出输出栈，然后返回这个保存的元素。

Implement Queue using Stacks

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

双栈法 复杂度

时间入队O(1) 出队O(N) 空间 O(N)

思路

队列和栈都是顺序插入的，区别在于队列的出口方向和栈的出口方向是相反的，利用这个性质，如果我们将元素按照顺序插入栈后，再一个个弹出并反向插入另一个栈，那么这第二个栈的出口顺序就和队列是一样的了。所以我们构造两个栈，所有新加的元素都加入输入栈，一旦要出队列时，我们便将输入栈的元素都反向加入输出栈，再输出。需要注意的是，如果输出栈不为空时，说明当前要输出的元素还在输出栈中，所以我们就暂时不用将输入栈的元素加入输出栈（而且加入后也会导致顺序错误）。

注意

Leetcode的方法是pop和push，实际上我们应该实现的是poll和offer（或者enqueue和dequeue），offer的实现和push是一样的，但将pop改为poll时，我们要先把peek到的元素保存，然后再弹出输出栈，然后返回这个保存的元素。

代码

class MyQueue {
    
    Stack input = new Stack();
    Stack output = new Stack();
    
    // Push element x to the back of queue.
    public void push(int x) {
        input.push(x);
    }

    // Removes the element from in front of queue.
    public void pop() {
        int x = peek();
        output.pop();
    }

    // Get the front element.
    public int peek() {
        if(output.isEmpty()){
            while(!input.isEmpty()){
                output.push(input.pop());
            } 
        }
        return output.peek();
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return input.isEmpty() && output.isEmpty();
    }
}

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

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

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

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

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

cloud 2019-08-19 10:26 评论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 225：用队列实现栈 Implement Stack using Queues

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

AlanKeene 2019-08-19 10:28 评论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