【题目】
某队列的声明如下：
C++ Code
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
template<typename T> class CQueue { public: CQueue() {} ~CQueue() {} void appendTail(const T &node); // append a element to tail void deleteHead(); // remove a element from head private: stack<T> m_stack1; stack<T> m_stack2; }; |
【分析】
我们用一个表来总结一下前面的例子执行的步骤：
|
操作 |
m_stack1 |
m_stack2 |
|
append a |
{a} |
{} |
|
append b |
{a,b} |
{} |
|
append c |
{a,b,c} |
{} |
|
delete head |
{} |
{b,c} |
|
delete head |
{} |
{c} |
|
append d |
{d} |
{c} |
|
delete head |
{d} |
{} |
总结完push和pop对应的过程之后，我们可以开始动手写代码了。
【代码】
C++ Code
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
/////////////////////////////////////////////////////////////////////// // Append a element at the tail of the queue /////////////////////////////////////////////////////////////////////// template<typename T> void CQueue<T>::appendTail(const T &element) { // push the new element into m_stack1 m_stack1.push(element); } /////////////////////////////////////////////////////////////////////// // Delete the head from the queue /////////////////////////////////////////////////////////////////////// template<typename T> void CQueue<T>::deleteHead() { // if m_stack2 is empty, and there are some // elements in m_stack1, push them in m_stack2 if(m_stack2.size() <= 0) { while(m_stack1.size() > 0) { T &data = m_stack1.top(); m_stack1.pop(); m_stack2.push(data); } } // push the element into m_stack2 assert(m_stack2.size() > 0); m_stack2.pop(); } |
【扩展】
这道题是用两个栈实现一个队列。反过来能不能用两个队列实现一个栈？如果可以，该如何实现？
【参考】
http://zhedahht.blog.163.com/blog/static/2541117420073293950662/