题解 | #用两个栈实现队列#

用两个栈实现队列

http://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6

方法一:双栈模拟队列

1.结题思路

模拟题,首先根据栈和队列的特性,栈是先进后出,队列是先进先出,不难得知,将数组元素按1,2,3顺序压入栈后,出栈顺序为3,2,1,改变了一次元素先后顺序,而将元素再压入栈后,出栈顺序即与第一次入栈时相同,实现了先入先出。

2.解法

入栈:栈1入栈即为模拟入队。
出栈:栈1在栈2为空的时候,将栈1内元素全部依次出栈再入栈栈2,再出栈2栈顶元素即为出队;在栈2非空的时候,则直接出栈。

3.图解

图片说明

4.具体代码

class Solution
{
public:
    void push(int node) {
        stack1.push(node);//用栈1入栈模拟队列入队 
    }

    int pop() {
        if(!stack2.empty()){//栈2有元素则直接出栈 
            int ans=stack2.top();
            stack2.pop();
            return ans; 
        }else{//否则将栈1元素出队到栈2,再让栈2顶元素出栈 
            while(!stack1.empty()){
                int temp=stack1.top();
                stack1.pop();
                stack2.push(temp);
            } 
            int ans=stack2.top();
            stack2.pop();
            return ans;
        }
    }

private:
    stack<int> stack1;//栈1模拟入队操作 
    stack<int> stack2;//栈2模拟出队操作 
};

5.时间复杂度和空间复杂度分析

时间复杂度:O(1),每个元素最多出入栈1栈2各一次,出入栈操作均为O(1)
空间复杂度:O(n),n是模拟队列中的元素个数,用到了栈来存放n个数

全部评论
int temp=stack1.top(); stack1.pop(); pop了2次吧,出栈了2次,一次Pop就够了,第二条语句可以干掉了吧我觉得
点赞 回复 分享
发布于 2023-03-06 12:22 广东

相关推荐

能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务