美文网首页
2020-06-05(实时记录)队列-用栈实现队列

2020-06-05(实时记录)队列-用栈实现队列

作者: 唐moumou | 来源:发表于2020-06-06 00:02 被阅读0次

就不引题了,大概和栈实现队列所用到的函数差不多。

思路:

同栈实现队列,只不过与上一个题目不同、这个的目的是将先push的元素先pop出去。

但是做的时候犯了一个错误,想的时候是:

先把第一个数5放进辅助栈里,然后把5转移到数据栈
5---NULL to NULL---5
再把第一个数5放进辅助栈,然后把4放进到辅助栈,
5---NULL to 4-5---NULL
再把第一、二个数放进数据栈里
放入顺序是5-4,然后发现数据栈里的排列是4-5的,那么pop的时候还是后进先出,没达到队列的效果
具体代码如下

void push(int x) {
        std::stack<int> temp_stack;
        temp_stack.push(x);
        while(!data_stack.empty())
        {
            temp_stack.push(data_stack.top());
            data_stack.pop();
        }
        
        while(!temp_stack.empty())
        {
            data_stack.push(temp_stack.top());
            temp_stack.pop();
        }
    }

如果把以上栈和队列互换,则放入顺序同样是4-5,就是正确的push效果,详情见上一篇队列实现栈.
错误点在哪里呢?答案就是push进辅助栈的时机,如果画一个流程图执行完第一个循环后的辅助栈是倒叙(即后进的元素在栈顶)的,再执行一次第二个循环将辅助栈的元素全放进数据栈之后又是正序的了,白费了功夫。
所以进行修正如下

void push(int x) {
        std::stack<int> temp_stack;
        while(!data_stack.empty())
        {
            temp_stack.push(data_stack.top());
            data_stack.pop();
        }
        temp_stack.push(x);
        while(!temp_stack.empty())
        {
            data_stack.push(temp_stack.top());
            temp_stack.pop();
        }
    }

第一个循环不执行
NULL-NULL
先把第一个数5放进辅助栈里,然后把5转移到数据栈
5---NULL to NULL---5
第一个循环做一次栈元素交换
NULL---5 to 5 ---NULL
然后把4放进到辅助栈,再把元素放进数据栈
4-5---NULL to 5-4---NULL
进栈顺序为5-4 出栈也为5-4
push更多元素可将栈内元素看成整体,其实就类似于两个数的操作
总之,将push操作放到这里,我的理解是能让push下面的一个循环执行完之后的对应栈为倒叙,就能输出正确结果了

相关文章

  • 2020-06-05(实时记录)队列-用栈实现队列

    就不引题了,大概和栈实现队列所用到的函数差不多。 思路: 同栈实现队列,只不过与上一个题目不同、这个的目的是将先p...

  • 数据结构——栈和队列

    用数组实现栈和队列 用栈实现队列 用队列实现栈 栈和队列的经典算法题最小间距栈宠物收养所 数组实现栈和队列 用数组...

  • leecode刷题(26)-- 用栈实现队列

    leecode刷题(26)-- 用栈实现队列 用栈实现队列 使用栈实现队列的下列操作: push(x) -- 将一...

  • C语言第七次作业:链表

    707. 设计链表 空指针 空节点 225. 用队列实现栈 链式存储栈 双队列实现栈 232. 用栈实现队列 链式...

  • 栈&队列

    一、栈&队列总结 栈/队列的应用接雨水验证栈序列滑动窗口的最大值 栈/队列的特殊实现用两个栈实现队列用两个队列实现...

  • 队列之-队列实现栈

    一、队列实现栈核心算法概述 之前已经描述过了用栈实现队列的功能,见栈系列之-实现队列,那么同样队列也可以用来实现栈...

  • 38_两个有趣的问题

    关键词:通过栈实现队列、通过队列实现栈 0. 通过栈实现队列 用栈实现队列等价于用后进先出的特性实现先进先出的特性...

  • Algorithm小白入门 -- 队列和栈

    队列和栈队列实现栈、栈实现队列单调栈单调队列运用栈去重 1. 队列实现栈、栈实现队列 队列是一种先进先出的数据结构...

  • 算法分析 [BFS、Greedy贪心] 2019-02-18

    队列 和 栈 232. 用栈实现队列 Implement Queue using Stacks双栈,出队列时,将i...

  • Python学习教程:用队列实现栈

    接着上一期跟大家说的用栈实现队列,这期的Python学习教程跟大家讲用队列实现栈 题目:使用队列实现栈的下列操作:...

网友评论

      本文标题:2020-06-05(实时记录)队列-用栈实现队列

      本文链接:https://www.haomeiwen.com/subject/uowzzhtx.html