写点什么

脑筋急转弯:如何用两个栈实现一个队列?用两个队列实现一个栈

用户头像
极客good
关注
发布于: 刚刚
  • 怎么判断呢?谁的标兵为 0,谁就是存(刚起步的时候手动指定 A 的标兵为-1 嘛,第一个存进去的时候一次性加 2)

  • 也省得倒腾来倒腾去。

  • 如果两个队列都被清空了,我们就再次将标兵 A 置为-1,这样还能提高代码的复用性。


好,接下来我们看一下别人的。


02 别人的想法


========


两个栈实现一个队列?


==========


看到一个和我想法差不多的老哥啊,不过他考虑得好像没有我详细哈。



图(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 =


【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


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


}

用户头像

极客good

关注

还未添加个人签名 2021.03.18 加入

还未添加个人简介

评论

发布
暂无评论
脑筋急转弯:如何用两个栈实现一个队列?用两个队列实现一个栈