//两个栈实现一个队列 #include<stack> //STL
#include<iostream> using namespace std; template<class T>
class CQueue
{
public:
CQueue();
~CQueue(); void appendTail(const T& node);
T deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
}; //思路：一个栈做添加队尾元素用；另一个做删除队首元素用。
// 操作时，对应栈有数据，另一个为空。 template<class T>
CQueue<T>::CQueue()
{
} template<class T>
CQueue<T>::~CQueue()
{
}
//stack1作为添加队尾元素的栈
template<class T>
void CQueue<T>::appendTail(const T& node)
{
if(stack1.empty())
{
while(!stack2.empty())
{
T temp = stack2.top();
stack1.push(temp);
stack2.pop();
}
stack1.push(node);
}
else
stack1.push(node);
} //stack2作为删除队首元素的栈
template<class T>
T CQueue<T>::deleteHead()
{
T Head;
if(stack2.empty())
{
if(stack1.empty())
{
cerr<<"This Queue is already empty!"
<<"Have no to be deleted!"<<endl;
exit();
}
while(!stack1.empty())
{
T temp = stack1.top();
stack2.push(temp);
stack1.pop();
}
Head = stack2.top();
stack2.pop();
}
else
{
Head = stack2.top();
stack2.pop();
} return Head;
} int main(int argc, char* argv[])
{
CQueue<char> q1;
q1.appendTail('a');
q1.appendTail('b');
q1.appendTail('c');
q1.appendTail('d');
q1.appendTail('e'); char Head = q1.deleteHead();
cout<<Head<<endl;
Head = q1.deleteHead();
cout<<Head<<endl; q1.appendTail('f');
q1.appendTail('g');
Head = q1.deleteHead();
cout<<Head<<endl;
Head = q1.deleteHead();
cout<<Head<<endl;
Head = q1.deleteHead();
cout<<Head<<endl;
Head = q1.deleteHead();
cout<<Head<<endl;
return ;
}
自己所做如上所示。思路就是：一个做删除栈；一个做添加栈。
相比较于作者的思想，虽然大体一致，但自己的思想有多余的部分：
在添加元素的时候，无论stack1是否为空，作者采取的策略为直接入栈，而自己却是先将stack2中的元素再弹出压入stack1，这一步根本就是多余的！
作者代码如下：（自己默写）
//作者代码，更简洁！
//stack1做入队操作，直接入队
template<typename T>
void CQueue<T>::appendTail(const T& node)
{
stack1.push(node);
} //stack2做出队操作
template<typename T>
T CQueue<T>::deleteHead()
{
if(stack2.empty())
{
while(stack1.empty())
{
T head = stack1.top();
stack2.push(head);
stack1.pop();
}
} if(stack2.empty())
throw new exception("queue is empty."); T Head = stack2.top();
stack2.pop(); return Head;
}
作者代码的结构安排更紧凑，更简洁！！！