面试题---使用栈stack实现队列queue

         在前面的小节里已经实现了queue，当时所采用的是front和rear两个指针分别指向队头和队尾。由于本题限制，不能使用这些指针。

          如何只使用stack实现queue呢？由于stack是现进后出（FILO），而queue是先进先出的（FIFO）。也就是说stack进行了一次反向，进行两次反向就能实现queue的功能，所以可以用两个stack实现queue。

        假设两个栈A和B，且都为空。可以认为栈A提供入队的功能，栈B提供出队的功能。下面是入队和出队的具体算法：

（1）如果栈B不为空，直接弹出栈B的数据。

（2）如果栈B为空，则依次弹出栈A的数据，放入栈B中，再弹出栈B的数据。

于是可以得到下面MyQueue定义及实现：（其中使用的MyData 和 MyStack 是前一章的内容）

class MyQueue
{
public:
	void enqueue(MyData data);	//入队
	void dequeue(MyData &data);	//出队
	bool IsEmpty();				//判空
private:
	MyStack s1;		//用于入队
	MyStack s2;		//用于出队
};

//入队
void MyQueue::enqueue(MyData data)
{
	s1.push(data);		//只对s1进行进栈操作
}
//出队
void MyQueue::dequeue(MyData &data)
{
	MyData temp(0);		//局部变量，用于临时存储

	if(s2.IsEmpty())	
	{
		while(! s1.IsEmpty())
		{					//如果s2为空，把s1的所有元素push到s2中
			s1.pop(&temp);	//弹出s1的元素
			s2.push(temp);	//压入s2中
		}
	}
	if(!s2.IsEmpty())
	{
		//此时如果s2不为空，弹出s2的栈顶元素
		s2.pop(&data);
	}
}
//队列判空
bool MyQueue::IsEmpty()
{
	//如果两个栈都为空，则返回1，否则返回0
	return (s1.IsEmpty() && s2.IsEmpty());
}

下面是测试程序：

int main()
{
	MyData data(0);
	MyQueue q;
	q.enqueue(MyData(1));    //进队顺序 1、2、3
	q.enqueue(MyData(2));
	q.enqueue(MyData(3));

	q.dequeue(data);		
	cout<<"dequeue "<<data.data<<endl;
	q.dequeue(data);
	cout<<"dequeue "<<data.data<<endl;
	q.dequeue(data);
	cout<<"dequeue "<<data.data<<endl;
	cout<<"Empty = "<<q.IsEmpty()<<endl;

	return 0;
}

执行结果：

dequeue 1       //出队列顺序 1、2、3
dequeue 2
dequeue 3
Empty = 1
Press any key to continue