数据结构用两个栈来模拟一个队列

绝地灬酷狼 2022-08-21 08:56 184阅读 0赞

请利用两个栈S1和S2来模拟一个队列。已知栈的三个操作定义如下：PUSH(ST,x),元素x入栈ST，POP(ST,X)，ST栈顶元素出栈并赋给变量x；Sempty(ST)，判断ST栈是否为空。那么利用栈的操作来实现该队列的三个操作：EnQueue，插入一个元素入队；DeQueue，删除一个元素出队；QueueEmpty，判队列为空。

利用两个顺序栈进行模拟整个过程。

代码实现及解释：

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h> ///利用顺序栈模拟队列
    #define MaxSize 100
    
    using namespace std;
    
    typedef int ElemType;
    
    typedef struct node
    {
        ElemType data[MaxSize];
        int top;
    }SeqStack;
    
    void InitStack(SeqStack &s)
    {
        s.top=-1;
        return;
    }
    
    int StackEmpty(SeqStack s)
    {
        return (s.top==-1);
    }
    
    int push(SeqStack &s, ElemType x)
    {
        if(s.top>=MaxSize)
        {
            cout<<"Over Flow"<<endl;
            return 0;
        }
        else
        {
            s.top++;
            s.data[s.top]=x;
            return 1;
        }
    }
    
    int pop(SeqStack &s,ElemType &x)
    {
        if(s.top==-1)
        {
            cout<<"Stack Empty"<<endl;
            return 0;
        }
        else
        {
            x=s.data[s.top];
            s.top--;
            return 1;
        }
    }
    
    int GetTop(SeqStack s,ElemType &e)
    {
        if(s.top==-1)
        {
            cout<<"Stack Empty"<<endl;
            return 0;
        }
        else
        {
            e=s.data[s.top];
            return 1;
        }
    }
    
    int EnQueue(SeqStack &S1,SeqStack &S2,ElemType x)///S1栈为入队栈，S2栈为出队栈
    {
        ElemType e; ///如果S1栈不满，就可以往S1栈中入；如果S1栈满了，但是S2栈仍为空，依然可以把S1栈中的元素倒在S2栈中，再对S1栈进行入栈操作
        if(S1.top<MaxSize)///如果S1栈满了但是S2栈中没有元素，则此时不能入栈
        {
            push(S1,x);
            return 1;
        }
        if(S1.top>=MaxSize && StackEmpty(S2))
        {
            while(!StackEmpty(S1))
            {
                pop(S1,e);
                push(S2,e);
            }
            push(S1,x);
            return 1;
        }
        /*if(StackEmpty(S1))
        {
            push(S1,x);
            return 1;
        }
        if(!StackEmpty(S1)&&StackEmpty(S2))
        {
            while(!StackEmpty(S1))
            {
                pop(S1,e);
                push(S2,e);
            }
            push(S1,x);
            return 1;
        }*/
        if(S1.top>=MaxSize && !StackEmpty(S2))
        {
            cout<<"Can Not EnQueue!"<<endl;
            return 0;
        }
    }
    
    int OutQueue(SeqStack &S1,SeqStack &S2, ElemType &e)
    {
        ElemType y;///若S2栈不为空栈，则直接对S2进行出栈即可；若S1栈和S2栈都为空，则此时不能再进行出栈了；若S1栈不空，但是S2栈是空栈时，可以把S1栈的元素倒在S2栈中，再对S2栈进行出队；
        if(StackEmpty(S1)&&StackEmpty(S2))
        {
            cout<<"Queue Empty!"<<endl;
            e=0;
            return 0;
        }
        if(!StackEmpty(S1)&&StackEmpty(S2))
        {
            while(!StackEmpty(S1))
            {
                pop(S1,y);
                push(S2,y);
            }
            pop(S2,e);
            return 1;
        }
        if(!StackEmpty(S2))
        {
            pop(S2,e);
            return 1;
        }
    }
    
    int EmptyQueue(SeqStack S1,SeqStack S2)
    {
        if(StackEmpty(S1)&&StackEmpty(S2))
            return 1;
        else return 0;
    }
    
    int main()
    {
        SeqStack S1,S2;
        ElemType n,e;
        int flag;
        InitStack(S1);
        InitStack(S2);
        cout<<"Please Input The Elems:"<<endl;
        cin>>n;
        while(n>0)
        {
            flag=EnQueue(S1,S2,n);
            if(flag==0)
            {
                cout<<"Can Not Do It!"<<endl;
                break;
            }
            cin>>n;
        }
        e=0;
        cout<<"The Queue Is: "<<endl;
        while(EmptyQueue(S1,S2)==0)
        {
            flag=OutQueue(S1,S2,e);
            if(flag)
            {
                cout<<e<<" ";
            }
        }cout<<endl;
        return 0;
    }