双栈实现队列

主要思想

有两个栈stack1和stack2，
在push时，直接压入stack1
在pop时，判断stack2是否为空，空则将stack1的数据压入stack2，不空则只需将stack2的栈顶弹出。

代码实现

#ifndef _MYQUEUE_H_
#define _MYQUEUE_H_

#include<iostream>
#include<stack>
using namespace std;

template<class T> class Test
{
public:
    Test();
    T pop();
    void push(T element);
private:
    stack<T> stk1;
    stack<T> stk2;

    
};
template<class T> Test<T>::Test() { }

template<class T> T Test<T>::pop()
{
    //TODO:检查stk2中是否为空，不空，则直接弹出stk2的栈顶;
    //否则，将stk1中的size-1个倒入stk2;返回stk1    栈底元素
    T retVal;
    if (!stk2.empty())
    {
        retVal = stk2.top();
        stk2.pop();
        return retVal;
    }
    else
    {
        T tmp;
        while (stk1.size() > 1)
        {
            tmp = stk1.top();
            stk2.push(tmp);
            stk1.pop();
        }
        tmp = stk1.top();
        stk1.pop();
        retVal = tmp;
        return retVal;
    }
}

template<class T> void Test<T>::push(T element)
{
    stk1.push(element);
}

#endif

注意，模板类的声明和定义需要在一个文件中