例题-两个队列实现一个栈

题目描述

使用两个队列实现一个栈，包含入栈push()和出栈pop()操作

原理

将队列A作为当前容器，队列B不管，当入栈push()操作时，全部入队到A，而当A不为空且需要出栈pop()时，将A的前n-1个元素出队到B队列里，如图

则队列A中最后一个元素出队即该”栈”出栈pop()。而当需要再次入栈时，则对队列B进行之前的操作，循环往复。

原理掌握，则每次需要做的就是判断当前哪个队列不为空就对其进行操作。

代码实现

下面代码为整型int的实现，如需其他类型则可用模板template实现，仅供参考

class QueueToStack {
public:
    queue<int> queue1;
    queue<int> queue2;
    void push(int num)
    {		//入栈
    	if (!queue2.empty())
    		queue2.push(num);
    	else
    		queue1.push(num);
    }
    int pop()
    {					//出栈
    	if (!queue1.empty()) 
    	{
    		while (queue1.size() > 1) 
    		{
    			queue2.push(queue1.front());
    			queue1.pop();
    		}
    		int res = queue1.front();
    		queue1.pop();
    		return res;
    	}else if (!queue2.empty()) 
    	{
    		while (queue2.size() > 1)
    		{
    			queue1.push(queue2.front());
    			queue2.pop();
    		}
    		int res = queue2.front();
    		queue2.pop();
    		return res;
    	}
        cout << "栈为空!" << endl;	//无元素时
    	return 0;
    }
}