如何用两个栈实现一个队列，以及用两个队列实现一个栈

开始

再开始开始实现之前，首先将定读者已经理解了栈和队列的区别。

如果不理解的话，可以先看看这一篇，传送门：【算法】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;
}