双栈模拟队列

---

一、简介

队列的操作，即进队和出队伍，还有判空函数，由于这里调用STL的栈，用的是deque做的容器，不存在判满。

那么，有种很容易想到的思路，从a进栈，但是由于先进来的被压在了最下面，而我以后需要第一个用的就是这个被压在底部的元素，所以，当要取得时候，把栈a倒扣，元素全部灌倒b中，把b中的第一个拿走就好了。

二、具体实现

下面说说具体的实现。

• 首先，需要定义两个栈a,b用于元素的进出。

入队列：

• 如果b为空，直接把元素压入a；
• 如果b有元素，把b中元素反扣到a中，再压入元素（保证先后次序）

出队列：

• 如果a，b都空，没有元素，提示错误。
• 如果a空，b不空，直接弹出b的第一个元素。
• 如果a不空，首先把a中元素反扣到b中，输出b中的第一个元素。
• 不会出现a,b同时不空的情况

贴代码：

#include <stack>
using namespace std;
template<class T>
class StackQueue  
{
public:
	StackQueue();
	virtual ~StackQueue();
	void EnQueue(T x);
	T DeQueue();
	bool IsEmpty();
private:
	stack<T> a;
	stack<T> b;	
};

template<class T>
void StackQueue<T>::EnQueue(T x)
{
	if (b.empty())			//如果栈b为空，直接压入栈a
		a.push(x);
	else					//如果栈b不空，首先把元素还到栈a，再压入
	{
        while (!b.empty()) {  
            a.push(b.top());
			b.pop();
        }  
        a.push(x);  
	}
}

template<class T>
T StackQueue<T>::DeQueue()
{
	if (IsEmpty()) 
	{
		cout<<"no elem"<<endl;
		exit(0);
	}
	if(a.empty())
	{
		T x=b.top();
		b.pop();
		return x;
	}
	while(!a.empty())
	{
		b.push(a.top());
		a.pop();
	}
	T x=b.top();
	b.pop();
	return x;
}


template<class T>
bool StackQueue<T>::IsEmpty()
{
	if(a.empty()&&b.empty())
		return true;
	else
		return false;
}

三、测试函数

int main()
{
	StackQueue<int> SQ;

	//模拟顺序进栈
	for(int i=0; i<7; i++)
		SQ.EnQueue(i+2);
	//模拟顺序出栈
	cout<<"输出顺序出栈的测试"<<endl;
	for(int j=0; j<7; j++)
		cout<<SQ.DeQueue()<<"   ";
	cout<<endl;
	cout<<"测试中途插入"<<endl;
	SQ.EnQueue(1);
	SQ.EnQueue(2);
	SQ.EnQueue(3);
	cout<<SQ.DeQueue()<<"   ";
	SQ.EnQueue(4);
	SQ.EnQueue(5);
	while (!SQ.IsEmpty())
	{
		cout<<SQ.DeQueue()<<"   ";
	}
	return 0;
}

测试截图：