鸿 网 互 联 www.68idc.cn

如何用两个栈实现一个队列,以及用两个队列实现一个栈

来源:互联网 作者:佚名 时间:2015-10-24 14:16
一、RDB持久化模式缺陷1.问题描述: 并发200路,模拟不断写Redis,持续4小时后,接口调用开始出现大量失败,错误信息如下:{data:{sendResult:null},base:{retur

开始

再开始开始实现之前,首先将定读者已经理解了栈和队列的区别(如果不理解的话,可以先看看这一篇,,传送门:【算法】7 分不清栈和队列?一张图给你完整体会 )

用两个栈实现一个队列

这本来就是一道面试题,所以如果你感兴趣的话可以先自己实现一遍。这是队列的声明:

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); } } if(stack2.size() == 0){ throw new exceptions("queue is empty"); } T head = stack2.top(); stack2.pop(); return head; } 用两个队列实现一个栈

写完了上面的代码,是不是也想换过来试一试呢?

同样是图片演示,以及具体代码实现。

这里写图片描述

template <typename T> class CStack { public: CStack(void); ~CStack(void); void appendTail(const T& node); T deleteHead(); private: queue<T> queue1; queue<T> queue2; }; template <typename T> CStack<T>::CStack(void) { } template <typename T> CStack<T>::~CStack(void) { } template <typename T> void CStack<T>::appendTail(const T& element) { if (queue1.size() >= 1) { T& data = queue1.front(); queue1.pop(); queue2.push(data); } queue1.push(element); } template <typename T> T CStack<T>::deleteHead() { T head; if (queue1.size() >= 1) { head = queue1.front(); queue1.pop(); } else if (queue1.size() == 0&&queue2.size() > 0) { while (queue2.size() > 1) { T& data = queue2.front(); queue2.pop(); queue1.push(data); } head = queue2.front(); queue2.pop(); while (queue1.size() > 0) { T& data = queue1.front(); queue1.pop(); queue2.push(data); } } else { throw new exception("stack is empty"); } return head; }

网友评论
<