学步园

57.用俩个栈实现队列。
题目：某队列的声明如下： 
83
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;
};
分析：从上面的类的声明中，我们发现在队列中有两个栈。
因此这道题实质上是要求我们用两个栈来实现一个队列。
相信大家对栈和队列的基本性质都非常了解了：栈是一种后入先出的数据容器，
因此对队列进行的插入和删除操作都是在栈顶上进行；队列是一种先入先出的数据容器，

我们总是把新元素插入到队列的尾部，而从队列的头部删除元素。

/*
57.用俩个栈实现队列。
题目：某队列的声明如下： 
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;
};

2个栈 s1，s2 
入队时，将元素压入s1。
出队时，判断s2是否为空，
	如不为空，则直接弹出顶元素；
	如为空，则将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队。
*/
#include <iostream>
#include <stack>
using namespace std;

template<class T>
class Queue
{
	private:
		stack<T> s1,s2;
	public:
		Queue(){}
		~Queue(){}
		
		void append(const T& node)// append a element to tail
		{
			s1.push(node);
		}
		
		void deleteHead() // remove a element from head
		{	
				if(s2.empty())//s2空，s1全部s2 
				{
					
					while(!s1.empty())
					{
						
						s2.push(s1.top());
						s1.pop();
					}
					cout<<"出队："<<s2.top()<<endl;
					s2.pop();
				}
				else
				{
					cout<<"出队："<<s2.top()<<endl;
					s2.pop();
				}
		}
};

int main() {

	Queue<char> q;
	
	q.append('a');
	q.append('b');
	q.append('c');
	q.append('d');
	q.deleteHead();
	q.deleteHead();
	
	cout<<"****************"<<endl;
	q.append('f');
	q.deleteHead();
	q.deleteHead();
	q.deleteHead();
	
	return 0;
}