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

两个栈实现一个队列
要求：只能使用栈的pop和push，以及测试栈是否为空三个操作。
实现思路：
队列里面使用stack one 和 stack two。
进队列时，直接进入栈one即可。
出队列时，从two弹出一个元素，如果two里面的元素为空，则将one里面的元素依次弹出并压入two中，再从two弹出一个元素返回。

用STL里面的stack模拟实现queue的代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stack>
using std::stack;

template<class T> class CQueue
{
public:
    CQueue()
    {
        nSize = 0;
    }

    void clear()
    {
        while (!one.empty())
        {
            one.pop();
        }
        while (!two.empty())
        {
            two.pop();
        }
    }

    void push(const T& t)
    {
        one.push(t);
        ++nSize;
    }

    void pop()
    {
        if (two.empty())
        {
            while (!one.empty())
            {
                two.push(one.top());
                one.pop();
            }
        }
        two.pop();
        --nSize;
    }

    T& front()
    {
        if (two.empty())
        {
            while (!one.empty())
            {
                two.push(one.top());
                one.pop();
            }
        }
        return two.top();
    }

    T& back()
    {
        return one.top();
    }

    bool empty()
    {
        return nSize == 0;
    }

private:
    stack<T> one;
    stack<T> two;
    int nSize;
};

#define MAX 20

int main()
{
    CQueue<int> q;

    srand(time(NULL));
    for (int i = 0; i < MAX; ++i)
    {
        q.push(i);

        if (rand() % 2)
        {
            printf("front: %d\n", q.front());
            q.pop();
        }
    }

    while (!q.empty())
    {
        printf("front: %d\n", q.front());
        q.pop();
    }

    return 0;
}

两个队列实现一个栈
要求：只能使用从队列的尾部入和头部出，以及测试队列是否为空三个操作。
实现思路：
队列里面使用queue one 和 stack two。
进栈时，根据当前元素是全部存储在哪个队列而选择从one或者two的尾部进入。
出栈时，假设当前元素都存储在one里面，则不断出队列，直到队列为空之前的所有元素一次进入队列two，而one里面的最后一个元素作为栈弹出的值返回。
对于当前元素是存储在哪个队列里面，可以设置变量标记，初始化时候存储在one里面，操作一次，由于元素要倒转，则存储位置会变一次。

用STL里面的queue模拟实现的stack代码如下：

#include <stdio.h>
#include <queue>
using std::queue;

template<class T> class CStack
{
public:
    CStack()
    {
        nSize = 0;
        nTime = 1;
    }

    void clear()
    {
        while (!one.empty())
        {
            one.pop();
        }
        while (!two.empty())
        {
            two.pop();
        }
    }

    void push(const T& t)
    {
        if (nTime % 2)
        {
            one.push(t);
        }
        else
        {
            two.push(t);
        }
        ++nSize;
    }

    void pop()
    {
        if (nTime % 2)
        {
            while (!one.empty())
            {
                T t = one.front();
                one.pop();
                if (!one.empty())
                {
                    two.push(t);
                }
            }
        }
        else
        {
            while (!two.empty())
            {
                T t = two.front();
                two.pop();
                if (!two.empty())
                {
                    one.push(t);
                }
            }
        }

        nTime = (nTime + 1) % 2;
        --nSize;
    }

    T& top()
    {
        if (nTime % 2)
        {
            while (!one.empty())
            {
                T t = one.front();
                one.pop();
                if (!one.empty())
                {
                    two.push(t);
                }
                else
                {
                    two.push(t);
                    nTime = (nTime + 1) % 2;
                    return two.back();
                }
            }
        }
        else
        {
            while (!two.empty())
            {
                T t = two.front();
                two.pop();
                if (!two.empty())
                {
                    one.push(t);
                }
                else
                {
                    one.push(t);
                    nTime = (nTime + 1) % 2;
                    return one.back();
                }
            }
        }
    }

    bool empty()
    {
        return nSize == 0;
    }

private:
    queue<T> one;
    queue<T> two;
    int nSize;
    int nTime;
};

#define MAX 20

int main()
{
    CStack<int> stack;

    for (int i = 0; i < MAX; ++i)
    {
        stack.push(i);
    }

    while (!stack.empty())
    {
        printf("top: %d\n", stack.top());
        stack.pop();
    }

    return 0;
}