关键词:
前言
其实我也不知道这两个问题又什么意义,就像不知道我们平时刷的算法题除了练脑子还有啥意义。
那就练一下,我先说一下我的想法,但是我知道,我的观点写不了几个字,所以后面肯定要掺和一下别人的看法。
我的想法
如何用两个栈实现一个队列
我发四,我只是想找张图,没想到它把我想说的话说了一半掉了。
但是,我觉着它倒来倒去烦不烦呐?
首先,我们分栈A、栈B。
操作有插入,取出。
标兵有栈A标兵、栈B标兵,标记哪个栈为正在插入的栈,哪个栈为正在取出的栈。
刚开始肯定都是无状态的,这时候要取,什么也取不出来,得先存钱。
挑栈A为存、栈B自然为取。
存着存着,要取一个的时候,将栈A全部倒进栈B,栈该怎么出栈就是怎么出栈。栈B出栈一个。
每次出栈,都检查一下负责出栈的栈B是否为空了,空了就把A里面带的东西再都倒进来,如果没得倒,那就说明没东西了。
取完一个之后,想存就继续存,想取就继续取,悉听尊便。
为什么取一下就要倒一波,累不累啊?
如何用两个队列实现一个栈
这个就比较麻烦一些了。
上面那个想了一分钟,这个想了三分钟,我想来想去,两个队列怎么拼,它还是队列啊。
后面想了一下栈的操作,聪明花突然就开了。
首先,材料有两个队列、两个标兵。
刚开始,队列都是空的,只能存,不能取。
存的时候,先往队列A里面存,标兵纪录队列长度。
存到不想存了,想取了,怎么操作?依次出队,往队列B里面去,标兵AB同时工作,纪录各自队列长度。
当队列A只有一个元素的时候,出队。
这时候,存取关系就变了,队列B变为了存队列,队列A变为了取队列。
怎么判断呢?谁的标兵为0,谁就是存(刚起步的时候手动指定A的标兵为-1嘛,第一个存进去的时候一次性加2)
也省的倒腾来倒腾去。
如果两个队列都被清空了,我们就再次将标兵A置为-1,这样还能提高代码的复用性。
好,接下来我们看一下别人的。
别人的想法
去取取经。
来自:https://blog.csdn.net/cherrydreamsover/article/details/80466781
两个栈实现一个队列
看到一个和我想法差不多的老哥啊,不过他考虑的好像没有我详细哈。
图(1):将队列中的元素“abcd”压入stack1中,此时stack2为空;
图(2):将stack1中的元素pop进stack2中,此时pop一下stack2中的元素,就可以达到和队列删除数据一样的顺序了;
图(3):可能有些人很疑惑,就像图3,当stack2只pop了一个元素a时,satck1中可能还会插入元素e,这时如果将stack1中的元素e插入stack2中,在a之后出栈的元素就是e了,显然,这样想是不对的,我们必须规定当stack2中的元素pop完之后,也就是satck2为空时,再插入stack1中的元素。
代码实现:
template<typename T> class CQueue
public:
CQueue(void);
~CQueue(void);
void appendTail(const T& node);
T deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
;
template<typename T>
void CQueue<T>::appendTail(const& T& element)//尾插
stack1.push(element);
template<typename T>
T CQueue<T>::deleteHead()
if (stack2.size() <= 0)
while (stack1.size > 0)
T& data = stack1.top();
stack1.pop();
stack2.push(data);
T head = stack2.top();
stack2.pop();
if (stack2.size() == 0)//当stack2为空时,抛异常
throw new exception("queue is empty");
return head;
如何用两个队列实现一个栈
还是那句话,没有我细嘿嘿
图(1):当栈里面插入元素“abcd”的时候,元素a在栈底(最后出去),d在栈顶(最先出去);
图(2):将元素“abc”从q1中头删,然后再q2中尾插进来之后,头删q1中的元素“d”,就相当于实现了栈顶元素的出栈;
图(3):同理,将元素“ab”从q2中头删,然后尾插到q1中,然后再头删q2中的元素“c”;
图(4):同理,删除元素“b”;
图(5):当栈又插入一个元素“e”时,此时元素“a”不能从队列中删除,而是将元素“a”插入q2中,再删除q1中的元素“e”,最后再删除元素“a”。
说明:其中红色框代表该队列中的元素出队列,该队列为空。
代码实现:
template<typename T> class CStack
public:
CStack(void);
~CStack(void);
void appendTail(const T& node);
T deleteHead();
private:
queue<T> q1;
queue<T> q2;
;
template<typename T>
void CStack<T>::appendTail(const T& node)//实现栈元素的插入
//数据的插入原则:保持一个队列为空,一个队列不为空,往不为空的队列中插入元素
if (!q1.empty())
q1.push(node);
else
q2.push(node);
template<typename T>
T CStack<T>::deleteHead()//实现栈元素的删除
int ret = 0;
if (!q1.empty())
int num = q1.size();
while (num > 1)
q2.push(q1.front());
q1.pop();
--num;
ret = q1.front();
q1.pop();
else
int num = q2.size();
while (num > 1)
q1.push(q2.front());
q2.pop();
--num;
ret = q2.front();
q2.pop();
return ret;
如何用栈实现队列(代码片段)
...思考思考,会有异常不到的收获。。。只为更好的自己如何用栈实现队列?提示下:用一个栈肯定是没办法实现队列,但如果我们有两个栈呢?分析:栈和队列的特性栈是先进后出,FILO出入元素都是在同一端(栈顶)入栈 1540... 查看详情
如何用两个栈实现队列(代码片段)
题目内容:如何用两个栈实现队列?思路分析:栈是先进后出的,队列是先进先出的。整体的思路是将一个栈1当做主要的存储空间,而将栈2当做缓冲区。入栈的时候先对栈1进行判断,看其是否为空,... 查看详情
如何用两个栈实现队列(代码片段)
importjava.util.Stack;publicclassQueueTestprivateStack<Integer>inStack=newStack<>();privateStack<Integer>outStack=newStack<>();/****@Description:(入栈)*@author:liyhui*@date:2018 查看详情
两个栈实现一个队列
用两个栈实现一个队列的功能。解题思路假设两个栈A和B,且都为空。栈A提供push()功能,栈B提供pop()功能。入队列:入栈A。出队列:假设栈B不为空。直接弹出B的元素。假设栈B为空,则依次弹出栈A的元素并压入栈B中,再弹出B... 查看详情
由两个栈组成的队列(代码片段)
由两个栈组成的队列【题目】编写一个类,用两个栈实现队列,支持队列的基本操作(add、poll、peek)。【思路】前景知识:栈,先进后出;队列,先进先出两个栈实现队列,用两个栈就是为了让栈中的数据反转一次,数... 查看详情
如何用“与”,“或”,“非”实现“异或”运算?(代码片段)
与&两个位都为1,结果才为1,否则结果为0或|两个位有一个为1,结果就是1,否则结果为0非~如果位为0,结果是1,如果位为1,结果是0异或^两个位相同结果为0,不同结果为1a^b=1.(a|b)&(~a|~b)2.~(~a&~b)&~(a&b)3.(a&~b)|(~a&a... 查看详情
9用两个队列实现一个栈(代码片段)
现在有一个A队列和一个B队列。(1)入栈操作,判断A队列是否有元素,若A队列有元素,则元素直接入A队列;若没有,则将元素入B队列;(2)出栈操作,若A和B都没有元素,则出栈失败; 判断A是否有元素,若A有元素,则获... 查看详情
两个堆栈实现列队
如何用两个堆栈模拟实现一个队列?如何用两个堆栈模拟实现一个队列? 如果这两个堆栈的容量分别是m和n(m>n),你的方法能保证的队列容量是多少?classSolution{//主要思路:建立两个栈S1,S2,当执行PUSH操作时将数据压... 查看详情
用两个栈实现一个队列
思路:使用两个栈实现一个队列,栈A用作插入栈,栈B用作弹出栈。队列的特点为先进先出。入列时,直接入栈A;出队列时先判断栈B是否为空,若为空,则依次弹出栈A中的数据入栈B,再弹出栈B数据;若不为空直接弹出栈B数据。... 查看详情
用两个栈实现一个队列
题目描述用两个栈来实现一个队列,完成队列的Push和Pop操作。队列中的元素为int类型。 用两个栈实现一个队列的功能?要求给出算法和思路!<分析>:入队:将元素进栈A出队:判断栈B是否为空,如果为空,则将栈A中所有... 查看详情
请教:如何用单片机控制小车转弯?
一般小车转弯分若干种1。三轮式1.1两个动力轮,一个辅助轮举例玩具小车两个动力轮同时转动,前进或后退两个动力轮反向转动或者转动速度不同,转向1.2两个辅助轮,一个动力轮前轮有动力而且可以转向这就要用两个电机控... 查看详情
剑指offer5.用两个栈实现队列(栈)(代码片段)
题目描述用两个栈来实现一个队列,完成队列的Push和Pop操作。队列中的元素为int类型。题目地址https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=13&tqId=11158&tPage=1&rp=2&ru=%2Fta%2Fcoding-interviews&qru 查看详情
剑指offer:用两个栈实现一个队列(代码片段)
题目描述用两个栈来实现一个队列,完成队列的Push和Pop操作。队列中的元素为int类型。类似汉诺塔,当我们需要将栈A下面的元素出栈的时候可以先将栈A中的元素全部逆序压入到另一个栈B,这时栈B保存的就是栈A的逆序,也就是... 查看详情
用有限个栈模拟常数效率操作的队列(代码片段)
...面试的经历。不过并不是我被面试,而是我面试别人。如何用两个栈实现一个队列?这算是一个经典的面试题。因为它经常被拿来用。如果对栈和队列比较掌握的人,就可以轻松的答出来。然而,那天坐在对面的面试者直接抛出... 查看详情
剑指offer:用两个栈实现一个队列(代码片段)
题目用两个栈来实现一个队列,完成队列的Push和Pop操作。队列中的元素为int类型。 解题思路用一个栈A来保存入栈,当要出栈的时候,将栈A的元素按照栈后进先出的特点转移到栈B中(此时栈A为空了)此时栈B中元素的保存顺... 查看详情
598.范围求和ii思维脑筋急转弯(代码片段)
https://leetcode-cn.com/problems/range-addition-ii/因为都是从左上角开始的,故存一个最小的a,b即可。classSolutionpublic:intmaxCount(intm,intn,vector<vector<int>>&ops)intl=m,r=n;for(inti=0 查看详情
用两个队列实现一个栈
#include<iostream>#include<queue>usingnamespacestd;template<typenameT>classMyQueuepublic: MyQueue(void); ~MyQueue(void); voidappendTail(constT&node); TdeleteHead(); voidPrint();p 查看详情
跪求脑筋急转弯、智力题(要附答案的)
谁给我一些高难度的脑筋急转弯和智力题?说的好的加分....先谢谢大家了1.问题:有一天狗狗和青蛙比赛游泳,青蛙为什么输了?答案:因为比的是狗刨泳。2.问题:什么动物的屁股杀伤力比嘴厉害?答案:黄蜂(黄蜂又称为“胡... 查看详情