面试题8：用两个栈实现一个队列

题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队尾插入结点和在队列头删除结点功能。

template<typename T>
class CQueue{
public:
CQueue(void);
~CQueue(void);
void appendTail(const T& node);
T deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
};

解答：

这题仔细分析下，应该可以做出来。有两个栈stack1和stack2。

我们可以用stack1专门执行appendTail操作，stack2专门执行deleteHead操作。

那么，如果stack2为空，我们将stack1(出队列逆序)的数压入到stack2（出队列顺序），在对stack2进行出栈。

如果stack2非空，直接出栈。

实现如下：

#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;

template<typename T>
class CQueue{
public:
CQueue(void){}
~CQueue(void){}
void appendTail(const T& node);
T deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
};

template<typename T>
void CQueue<T>::appendTail(const T& node)
{
stack1.push(node);
}

template<typename T>
T CQueue<T>::deleteHead()
{
if (stack2.size() <= 0)
{
if (stack1.size() <= 0) throw new exception("queue is empty");
while (stack1.size() > 0)
{
stack2.push(stack1.top());
stack1.pop();
}
}
T temp = stack2.top();
stack2.pop();
return temp;
}

int main()
{
CQueue<int> myQueue;
myQueue.appendTail(1);
myQueue.appendTail(2);
cout << myQueue.deleteHead() << endl;
myQueue.appendTail(3);
myQueue.appendTail(4);
cout << myQueue.deleteHead() << endl;
cout << myQueue.deleteHead() << endl;
cout << myQueue.deleteHead() << endl;
//cout << myQueue.deleteHead() << endl;
return 0;
}

思考：

用两个队列实现一个栈。

和上面思路差不多，每次进栈时，两个队列中有一个为空，于是，将进栈元素添加到非空的那个队列（如果两个为空，则任选一个），出栈时，将非空的那个队列的前n-1个元素加入到为空的那个队列，最后一个元素出队列即为出栈。