【22】用两个栈实现队列

题目：用两个栈实现一个队列，队列的声明如下

//队列声明如下
template <typename T>
class Queue{
public:
	Queue(void){}
	~Queue(void){};
	void push(const T& value);
	void pop(void);
	int size(void);
	T  front(void);
	T  back(void);
	bool empty(void);
private:
	stack<T> pushStk;
	stack<T> popStk;
};

1. 队列的性质是“先进先出、只能在队列尾部插入、只能在队列头部删除”

2. 利用两个栈分别来实现队列尾部插入和队列头部删除的功能

    pushStk用来表示插入数据的栈，如果popStk是空的直接插入pushStk，如果popStk不为空则把popStk的元素全部搬到pushStk中再插入新元素

    popStk用来表示删除元素的栈，如果popStk不为空直接删除popStk栈顶的元素就是删除队列元素，如果popStk为空则先把pushStk元素搬到popStk中再删除栈顶元素

3. 其它的函数实现依赖于这两个栈，如论如何这两个栈肯定不可能同时不为空，只可能是一个为空一个不为空或者两个都是空

//实现push函数，插入元素到队列尾部
template <typename T> void Queue<T>::push(const T& value){
	//先把popStk中的元素搬到pushStk中再插入新元素
	while(!popStk.empty()){
		 pushStk.push(popStk.top());
	     popStk.pop();
	}
	pushStk.push(value);
}

//实现pop函数，删除队列头元素
template <typename T> void Queue<T>::pop(void){
	//如果两个栈都是空的直接抛异常
	if(pushStk.empty() && popStk.empty()){
	    throw exception("error");
		return;
	}
	if(!popStk.empty()){
	    popStk.pop();
	}
	else{
		while(!pushStk.empty()){
		     popStk.push(pushStk.top());
             pushStk.pop();
		}
		popStk.pop();
	}
}

//实现size函数，得到队列的元素个数
template <typename T> int Queue<T>::size(void){
	if(popStk.empty()){
	    return pushStk.size();
	}
	else{
	    return popStk.size();
	}
}

//实现front函数，得到队列头一个元素
template <typename T> T Queue<T>::front(void){
	//如果两个栈都是空直接抛异常
	if(pushStk.empty() && popStk.empty()){
	   throw exception("error");
	   return 2147483647;
	}
	if(!popStk.empty()){
		return popStk.top();
	}
	else{
		while(!pushStk.empty()){
			popStk.push(pushStk.top());
			pushStk.pop();
		}
		return popStk.top();
	}
}

//实现back函数,得到队列最尾元素
template <typename T> T Queue<T>::back(void){
    if(pushStk.empty() && popStk.empty()){
	   throw exception("error");
	   return 2147483647;
	}
	if(!pushStk.empty()){
		return pushStk.top();
	}
	else{
		while(!popStk.empty()){
			pushStk.push(popStk.top());
			popStk.pop();
		}
		return pushStk.top();
	}
}

//实现empty函数，判断队列是否为空
template <typename T> bool Queue<T>::empty(void){
	if(pushStk.empty() && popStk.empty()){
	   return true;  
	}
	else{
	   return false;
	}
}