【练习】两个队列实现一个栈/两个栈实现一个队列 STL

【练习】两个队列实现一个栈

//使用两个栈实现一个队列&使用两个队列实现一个栈
#include <iostream>
#include <stack>
#include <queue>
using namespace std;

//两个栈实现一个队列
/*
    入队列：直接压入s1即可
    出队列：如果s2不为空，把s2中的栈顶元素直接弹出；
    否则，把s1的所有元素全部弹出压入s2中，再弹出s2的栈顶元素
*/
template <class T>
class realizeQueue
{
private:
    stack<T> s1;
    stack<T> s2;
    int _scount;
public:
    realizeQueue()
        : _scount(0)
    {}

    void qPush(const T& data)
    {
        s1.push(data);
        ++_scount;
    }

    T qPop()
    {
        T ret;
        if (s2.size() == 0 && s1.size() > 0)
        {
            while (s1.size())
            {
                T& tmp = s1.top();
                s1.pop();
                s2.push(tmp);
            }
        }
        if (s2.size() > 0)
        {
            ret = s2.top();
            s2.pop();
            cout << ret << endl;
        }
        
        if (_scount > 0)
        {
            --_scount;
            return ret;
        }
        return 0;
    }

    int qGetConut()
    {
        return _scount;
    }
};

//使用两个队列实现一个栈
/*
    入栈：如果q1与q2都为空，那么往q1中插入元素

        如果q1不为空，那么往q1中插入元素

        如果q2不为空，那么往q2中插入元素
    出栈：如果q1为空，q2不为空，将q2除最后一个元素的其他元素压q1，弹q2的最后一个元素
        如果q2为空，q1不为空，将q1除最后一个元素的其他元素压q2，弹q1的最后一个元素
*/
template <class T>
class realizeStack
{
private:
    queue<T> q1;
    queue<T> q2;
    int _qcount;

public:
    realizeStack()
        : _qcount(0)
    {}

    void qPush(const T& data)
    {
        if (q1.empty() && q2.empty())
            q1.push(data);
        else if (!q1.empty())
            q1.push(data);
        else if (!q2.empty())
            q2.push(data);

        ++_qcount;
    }

    T qPop()
    {
        T ret;
        if (q1.size() == 0 && q2.size() > 0)
        {
            while (q2.size() != 1)
            {
                T& tmp = q2.front();
                q2.pop();
                q1.push(tmp);
            }
            ret = q2.front();
            q2.pop();
            cout << ret << endl;
        }
        else if (q2.size() == 0 && q1.size() > 0)
        {
            while (q1.size() != 1)
            {
                T& tmp = q1.front();
                q1.pop();
                q2.push(tmp);
            }
            ret = q1.front();
            q1.pop();
            cout << ret << endl;
        }
        if (_qcount > 0)
        {
            --_qcount;
            return ret;
        }
        return 0;
    }

    int qGetCount()
    {
        return _qcount;
    }
};

//测试两个栈实现一个队列
void test_sQueue()
{
    realizeQueue<int> q;
    q.qPush(2);
    q.qPush(4);
    q.qPush(6);
    q.qPush(8);
    int count = q.qGetConut();
    cout << "count " << count << endl;

    q.qPop();
    q.qPop();
    count = q.qGetConut();
    cout << "count " << count << endl;

    q.qPush(0);
    q.qPop();
    q.qPop();
    q.qPop();
    q.qPop();
    count = q.qGetConut();
    cout << "count " << count << endl;


}

//测试两个队列实现一个栈
void test_qStack()
{
    realizeStack<int> s;
    s.qPush(3);
    s.qPush(5);
    s.qPush(7);
    s.qPush(9);
    int count = s.qGetCount();
    cout << "count " << count << endl;

    s.qPop();
    s.qPop();
        
    count = s.qGetCount();
    cout << "count " <<count << endl;

    s.qPush(1);
    s.qPop();
    s.qPop();
    s.qPop();
    s.qPop();
    count = s.qGetCount();
    cout << "count " << count << endl;
}

int main()
{
    test_sQueue();
    //test_qStack();

    system("pause");
    return 0;
}