题目:用两个栈实现一个队列。队列的生命如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能。 template <typename T>class CQueue { public: CQueue(void); ~CQueue(void); void appendtail(const T& node); T deleteHead(); private: stack<T> stack1; stack<T> stack2; };
解题思路:
插入操作在stack1中进行,删除操作在stack2中进行,如果stack2为空,则将stack1中的所有元素转移到stack2中。
代码实例:
View Code
使用两个队列实现一个栈
参考文献:
http://hi.baidu.com/ozwarld/blog/item/ec9b52d4d48ce1dc50da4b0f.html
解法:
- 有两个队列q1和q2,先往q1内插入a,b,c,这做的都是栈的push操作。
- 现在要做pop操作,即要得到c,这时可以将q1中的a,b两个元素全部dequeue并存入q2中,这时q2中元素为a,b,对q1再做一次dequeue操作即可得到c。
- 如果继续做push操作,比如插入d,f,则把d,f插入到q2中,
- 此时若要做pop操作,则做步骤2
- 以此类推,就实现了用两个队列来实现一个栈的目的。
注意在此过程中,新push进来的元素总是插入到非空队列中,空队列则用来保存pop操作之后的那些元素,那么此时空队列不为空了,原来的非空队列变为空了,总是这样循环。
对于push和pop操作,其时间为O(n).
代码实例
View Code
本文转自xwdreamer博客园博客,原文链接:http://www.cnblogs.com/xwdreamer/archive/2012/05/03/2480651.html,如需转载请自行联系原作者