用两个栈实现队列和用两个队列实现栈

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

template <class T>

class CQueue

{
　　CQueue();

　　~CQueue();

　　void appendTail(const T& node);

　　T deleteHead();

private:

　　stack<T> stack1;

　　stack<T> stack2;

};

 如上图所示：每次插入结点时都插入到stack1，例如依次插入a,b,c，然后为了达到队列的先进先出特性也就是要删除a,但是stack1只有栈的特性，只会先输出c,故需要把stack1中的数据依次的输出到stack2中，存入stack2的序列分别为c,b,a,此时stack2的栈顶是a,也就是我们需要输出的元素。也就是说每次的插入都需要在stack1中进行，删除操作首先需要检查stack2是否为空，若不为空，则直接输出stack2的栈顶，否则依次把stack1中的元素全部导入到stack2然后再输出。

故可以写出简单的代码如下：

#include<iostream>
#include<stack>
using namespace std;
template <class T>
class CQueue{
    CQueue();
    ~CQueue();
    void appendTail(const T& node);
    T deleteHead();
private:
    stack<T> stack1;
    stack<T> stack2;
};
template <class T>
void CQueue<T>::appendTail(const T& node)
{
    stack1.push(node);//入队列全放入stack1
}
template <class T>
T CQueue<T>::deleteHead()
{
    if (stack2.size() <= 0)
    {
        if (stack1.size() <= 0)
            throw exception("the queue is empty");//两个栈都为空
        else{//stack1不为空，stack2为空，则stack1全部入stack2
            while (stack1.size() > 0){
                T value = stack1.top();
                stack2.push(value);
                stack1.pop();
            }
        }
    }//stack2不为空则直接输出
    T r_value = stack2.top();
    stack2.pop();
    return r_value;
}

 

题目二：用两个队列实现栈，栈的声明如下，分别实现栈的push()函数和topAnddelete()函数，用来完成在栈的顶部插入和删除（返回栈顶值）的操作

template <class T>

class CStack{
　　CStack();

　　~CStack();

　　void push(const T& node);

　　T topAnddelete();

private:

　　queue<T> queue1;

　　queue<T> queue2;

};

 

也就是说，根据上面的分析每次删除操作前，总有一个queue是空的，一个queue是满的（当然两个都为空时我们的删除操作直接抛出异常就可以了），然后满的那个queue一定是我们要在其上完成删除操作的，需要把满的queue除队尾元素之外的所有元素都移到另一个空的queue，然后再删除这个唯一的元素（删除后必然又有一个queue为空）。所以每次只需要检测哪个queue不为空然后完成相应的操作即可。

代码如下：

#include<iostream>
#include<queue>
using namespace std;
template <class T>
class CStack{
public:
        CStack();
        ~CStack();
        void push(const T& node);
        T topAnddelete();
private:
        queue<T> queue1;
        queue<T> queue2;
};
template <class T>
void CStack<T>::push(const T &node)//每次都选择插入queue1
{
    queue1.push(node);
}
template<class T>
T CStack<T>::topAnddelete()
{
    if (queue1.empty() && queue2.empty()){//若为空抛出异常
        throw exception("the stack is empty");
    }
    else if(!queue1.empty() && queue2.empty()){//queue1不为空，queue2为空
        while (queue1.size() > 1){
            T value = queue1.front();
            queue2.push(value);
            queue1.pop();
        }
        T r_value = queue1.front();
        queue1.pop();
        return r_value;
    }
    else{//queue2不为空，queue1为空
        while (queue2.size() > 1){
            T value = queue2.front();
            queue1.push(value);
            queue2.pop();
        }
        T r_value = queue2.front();
        queue2.pop();
        return r_value;
    }
}