双栈模拟队列

data_structure

一、简介

队列的操作，即进队和出队伍，还有判空函数，由于这里调用STL的栈，用的是deque做的容器，不存在判满。

那么，有种很容易想到的思路，从a进栈，但是由于先进来的被压在了最下面，而我以后需要第一个用的就是这个被压在底部的元素，所以，当要取得时候，把栈a倒扣，元素全部灌倒b中，把b中的第一个拿走就好了。

二、具体实现

下面说说具体的实现。

• 首先，需要定义两个栈a,b用于元素的进出。

入队列：

• 如果b为空，直接把元素压入a；
• 如果b有元素，把b中元素反扣到a中，再压入元素（保证先后次序）

出队列：

• 如果a，b都空，没有元素，提示错误。
• 如果a空，b不空，直接弹出b的第一个元素。
• 如果a不空，首先把a中元素反扣到b中，输出b中的第一个元素。
• 不会出现a,b同时不空的情况

贴代码：

#include <stack>
using namespace std;
template<class T>
class StackQueue  
{
public:
    StackQueue();
    virtual ~StackQueue();
    void EnQueue(T x);
    T DeQueue();
    bool IsEmpty();
private:
    stack<T> a;
    stack<T> b; 
};

template<class T>
void StackQueue<T>::EnQueue(T x)
{
    if (b.empty())          //如果栈b为空，直接压入栈a
        a.push(x);
    else                    //如果栈b不空，首先把元素还到栈a，再压入
    {
        while (!b.empty()) {  
            a.push(b.top());
            b.pop();
        }  
        a.push(x);  
    }
}
template<class T>
T StackQueue<T>::DeQueue()
{
    if (IsEmpty()) 
    {
        cout<<"no elem"<<endl;
        exit(0);
    }
    if(a.empty())
    {
        T x=b.top();
        b.pop();
        return x;
    }
    while(!a.empty())
    {
        b.push(a.top());
        a.pop();
    }
    T x=b.top();
    b.pop();
    return x;
}
template<class T>
bool StackQueue<T>::IsEmpty()
{
    if(a.empty()&&b.empty())
        return true;
    else
        return false;
}

三、测试函数

int main()
{
    StackQueue<int> SQ;
    //模拟顺序进栈
    for(int i=0; i<7; i++)
        SQ.EnQueue(i+2);
    //模拟顺序出栈
    cout<<"输出顺序出栈的测试"<<endl;
    for(int j=0; j<7; j++)
        cout<<SQ.DeQueue()<<"   ";
    cout<<endl;
    cout<<"测试中途插入"<<endl;
    SQ.EnQueue(1);
    SQ.EnQueue(2);
    SQ.EnQueue(3);
    cout<<SQ.DeQueue()<<"   ";
    SQ.EnQueue(4);
    SQ.EnQueue(5);
    while (!SQ.IsEmpty())
    {
        cout<<SQ.DeQueue()<<"   ";
    }
    return 0;
}

测试截图：