剑指offer-JZ5

用两个栈实现队列

https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=13&tqId=11158&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

c++
本题考查最简单的队列和栈的性质。
队列:先进先出 [1,2,3,4]------4,3,2,1
栈 :后进先出 [1,2,3,4]------1,2,3,4
想要用栈实现队列,最简单的是
a---[1,2,3,4] 出栈然后入栈b [4,3,2,1]
代码如下:

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }
    void copy(stack<int> &a, stack<int> &b){
        while(a.size()){
            b.push(a.top());
            a.pop();
        }
    }
    int pop() {
        copy(stack1,stack2);
        int top_num = stack2.top();
        stack2.pop();
        copy(stack2,stack1);
        return top_num;
    }

private:
    stack<int> stack1; 
    stack<int> stack2;
};

但是频繁复制其实有优化空间的。
比如,两个栈实际上不需要每次出队列就赋值,可以等b结束了再赋值,即
a [1,2,3,4] b[] ---------出队列 ------a[],b[4,3,2,1]
---进队列
a[5,6,7]----b[4,3,2,1]
直到b出完
再进行转换

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }
    int pop() {


        if(! stack2.empty()){
            int top_num = stack2.top();
            stack2.pop();
            return top_num;
        }else if (!stack1.empty()){
            while(stack1.size()){
                stack2.push(stack1.top());
                stack1.pop();
            }
            int top_num = stack2.top();
            stack2.pop();
            return top_num;
        }else{
            return stack2.top();
        }

    }

private:
    stack<int> stack1; 
    stack<int> stack2;
};

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
2022-12-09 21:15
清华大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-06 22:26
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议