开始
再开始开始实现之前，首先将定读者已经理解了栈和队列的区别。
如果不理解的话，可以先看看这一篇，传送门：【算法】7 分不清栈和队列？一张图给你完整体会
用两个栈实现一个队列
这本来就是一道面试题，所以如果你感兴趣的话可以先自己实现一遍。这是队列的声明：
template <typename T> class CQueue{
public:
CQueue(void);
~CQueue(void);
void appendTail(const T& node);
T deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
};你要补充的就是在队列尾部插入结点和在队列头部删除结点的功能。
下面是图片演示过程，以及具体代码实现。
插入a，b，c：往stack1中依次压入了a，b，c
删除队列头：将c，b依次从stack1弹出和压入stack2
删除队列头：将b从stack2中弹出
插入d：往stack1中压入d
删除队列头：将c从stack2中弹出
template <typename T> void CQueue<T>::appendTail(const T& element){
stack1.push(element);
}
template <typename T> T CQueue<T>::deleteHead(){
if(stack2.size() <= 0){
while(stack1.size > 0){
T& data = stack1.top();
stack1.pop();
stack2.push(data);
}
}
if(stack2.size() == 0){
throw new exceptions("queue is empty");
}
T head = stack2.top();
stack2.pop();
return head;
}用两个队列实现一个栈
写完了上面的代码，是不是也想换过来试一试呢？
同样是图片演示，以及具体代码实现。
插入a：向queue1中压入a
插入b：向queue1中压入b之前，先将a压入到queue2中，再将a从queue1中弹出
插入c，d：同上过程，最后如图所示
从栈顶删除d：将queue1中的d弹出
从栈顶删除c(1)：queue1为空，此时先将a和b依次压入queue1，再从queue2中弹出
从栈顶删除c(2)：将queue2中的c弹出，并将queue1中的a和b弹出再压入queue2
template <typename T> class CStack {
public:
CStack(void);
~CStack(void);
void appendTail(const T& node);
T deleteHead();
private:
queue<T> queue1;
queue<T> queue2;
};
template <typename T> CStack<T>::CStack(void) {
}
template <typename T> CStack<T>::~CStack(void) {
}
template <typename T> void CStack<T>::appendTail(const T& element) {
if (queue1.size() >= 1) {
T& data = queue1.front();
queue1.pop();
queue2.push(data);
}
queue1.push(element);
}
template <typename T> T CStack<T>::deleteHead() {
T head;
if (queue1.size() >= 1) {
head = queue1.front();
queue1.pop();
}
else if (queue1.size() == 0&&queue2.size() > 0) {
while (queue2.size() > 1) {
T& data = queue2.front();
queue2.pop();
queue1.push(data);
}
head = queue2.front();
queue2.pop();
while (queue1.size() > 0) {
T& data = queue1.front();
queue1.pop();
queue2.push(data);
}
}
else {
throw new exception("stack is empty");
}
return head;
}
