LeetCode232—Implement Queue using Stacks

╰半橙微兮° 2022-07-15 02:52 126阅读 0赞

## 原题 ##

[原题链接][Link 1]

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

## 分析 ##

栈是后进先出，队列是先进先出。

如果用栈实现队列的话，需要用到**两个栈**

假设两个栈stack1和stack2，假设现在一组数据压栈，那么他们出栈的顺序肯定是相反的，也就是所谓的后进先出。现在我们将数据压入stack1然后出栈的时候再把数据压入stack2，那么原先stack1中的栈底元素就成了stack2的栈顶元素，弹出的时候也就“先出了”，这就用两个栈实现了一个队列。

### **代码** ###

class Queue {
    private:
        stack<int>s1;
        stack<int>s2;
    public:
        // Push element x to the back of queue.
        void push(int x) {
            s1.push(x);
        }
    
        // Removes the element from in front of queue.
        void pop(void) {
            while(!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
            s2.pop();
            while(!s2.empty())
            {
                s1.push(s2.top());
                s2.pop();
            }
        }
    
        // Get the front element.
        int peek(void) {
            while(!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
            int t = s2.top();
            while(!s2.empty())
            {
                s1.push(s2.top());
                s2.pop();
            }
            return t;
        }
    
        // Return whether the queue is empty.
        bool empty(void) {
            return s1.empty();
        }
    };

说明：这里我愚了。  
入队的时候都往s1中压栈，但是出队的时候，需要将s1中所有元素压入s2中，在弹出栈顶元素。我当时害怕逻辑乱了，我又将s2中的所有元素再压回s1中，保持原来的状态。这样做效率非常低，因为每次出队都有O(n)的复杂度

事实上是不必的，**当我们出队时，只有当s2栈空时，我们才需要再次将s1中的所有元素压入s2，否则直接让s2弹栈即可**  
参考：[https://discuss.leetcode.com/topic/61137/my-c-solution-with-comments][https_discuss.leetcode.com_topic_61137_my-c-solution-with-comments]。

[Link 1]: https://leetcode.com/problems/implement-queue-using-stacks/
[https_discuss.leetcode.com_topic_61137_my-c-solution-with-comments]: https://discuss.leetcode.com/topic/61137/my-c-solution-with-comments

发表评论取消回复

表情：

评论列表（有 0 条评论，126人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode（Queue)232. Implement Queue using Stacks

1.问题 Implement a first in first out (FIFO) queue using only two stacks. The implement

柔情只为你懂/ 2023年09月25日 18:11/ 0 赞/ 50 阅读

相关 232. Implement Queue using Stacks

Implement the following operations of a queue using stacks. push(x) -- Push element

刺骨的言语ヽ痛彻心扉/ 2023年07月03日 07:06/ 0 赞/ 12 阅读

相关 [LeetCode] 232. Implement Queue using Stacks 用栈来实现队列

Implement the following operations of a queue using stacks. push(x) -- Push element

拼搏现实的明天。/ 2022年10月02日 12:52/ 0 赞/ 143 阅读

相关 LeetCode--Implement Queue using Stacks

Problem: > Implement the following operations of a queue using stacks. > \- push(x) –

喜欢ヅ旅行/ 2022年08月17日 16:07/ 0 赞/ 37 阅读

相关 LeetCode-Implement Queue using Stacks

Implement the following operations of a queue using stacks. push(x) -- Push element

Bertha 。/ 2022年08月04日 00:46/ 0 赞/ 143 阅读

相关 LeetCode232—Implement Queue using Stacks

原题 [原题链接][Link 1] > Implement the following operations of a queue using stacks. > >

╰半橙微兮°/ 2022年07月15日 02:52/ 0 赞/ 127 阅读

相关 [leetcode]: 232. Implement Queue using Stacks

1. 题目 Implement the following operations of a queue using stacks. push(x) – Push ele

以你之姓@/ 2022年06月15日 06:44/ 0 赞/ 159 阅读

相关 leetcode 232. Implement Queue using Stacks 双栈实现队列

Implement the following operations of a queue using stacks. push(x) – Push element x to

心已赠人/ 2022年06月08日 12:09/ 0 赞/ 187 阅读

相关 [LeetCode] Implement Stack using Queues

[Implement Stack using Queues][Implement Stack using Queues] Implement the following op

待我称王封你为后i/ 2021年12月03日 07:15/ 0 赞/ 136 阅读

相关 LeetCode : 232. Implement Queue using Stacks 栈实现队列

试题 Implement the following operations of a queue using stacks. push(x) – Push element

落日映苍穹つ/ 2021年06月12日 20:36/ 0 赞/ 480 阅读