数据结构-顺序栈

你的名字 2022-07-28 04:30 390阅读 0赞

/*
    编写一个程序，实现顺序栈（假设栈中元素类型为char）的各种基本运算。并完成下面功能：
    （1）初始化栈s;
    （2）判断栈s是否非空；
    （3）依次进栈元素a,b,c,d,e;
    （4）判断栈s是否非空；
    （5）输出栈长度；
    （6）输出从栈顶到栈底元素；
    （7）输出出栈序列；
    （8）判断栈s是否非空；
    （9）释放栈。
    */
    
    #include <iostream>
    #include <malloc.h>
    #include <cstdio>
    #include <cstring>
    #define MaxSize 100
    using namespace std;
    typedef char ElemType;
    typedef struct
    {
        ElemType data[MaxSize];
        int top;            //栈顶指针
    }SqStack;               //定义顺序栈类型
    
    void InitStack(SqStack *&s)           //初始化栈s
    {
        s=(SqStack *)malloc(sizeof(SqStack));
        s->top=-1;          //栈顶指针置-1
    }
    
    bool StackEmpty(SqStack *s)           //判断栈s是否为空
    {
        return (s->top!=-1);
    }
    
    bool Push(SqStack *&s,ElemType e)      //进栈
    {
        if(s->top==MaxSize-1)    //栈上溢出
            return false;
        s->top++;                //栈顶指针增1
        s->data[s->top]=e;       //元素e放在栈顶指针处
        return true;
    }
    
    int getLength(SqStack *s)            //输出栈长度
    {
        return (s->top+1);
    }
    
    bool GetStack(SqStack *&s,int i,ElemType &e)   //输出从栈顶到栈底元素
    {
        if(s->top==-1)
            return false;
        e=s->data[i];
        return true;
    }
    
    bool Pop(SqStack *&s,ElemType &e)   //出栈
    {
        if(s->top==-1)          //栈下溢出
            return false;
        e=s->data[s->top];      //取栈顶元素
        s->top--;               //栈顶指针减1
        return true;
    }
    
    void DestoryStack(SqStack *&s)      //释放栈
    {
        free(s);
    }
    
    int main()
    {
        ElemType a[MaxSize],b;
        SqStack *s;
        InitStack(s);
        cout<<"栈是否非空？";
        if(StackEmpty(s))
            cout<<"是"<<endl;
        else
            cout<<"否"<<endl;
        cout<<"输入要进栈元素:";
        gets(a);
        for(int i=0;i<strlen(a);i++)
        {
            Push(s,a[i]);
        }
        cout<<"元素已进栈"<<endl;
        cout<<"栈是否非空？";
        if(StackEmpty(s))
            cout<<"是"<<endl;
        else
            cout<<"否"<<endl;
        cout<<"栈的长度："<<getLength(s)<<endl;
        cout<<"输出从栈顶到栈底元素:";
        for(int i=s->top;i>=0;i--)
        {
            GetStack(s,i,b);
            cout<<b<<" ";
        }
        cout<<endl;
        cout<<"栈是否非空？";
        if(StackEmpty(s))
            cout<<"是"<<endl;
        else
            cout<<"否"<<endl;
        cout<<"输出出栈序列：";
        for(int i=s->top;i>=0;i--)
        {
            Pop(s,b);
            cout<<b<<" ";
        }
        cout<<endl;
        cout<<"栈是否非空？";
        if(StackEmpty(s))
            cout<<"是"<<endl;
        else
            cout<<"否"<<endl;
        DestoryStack(s);
        cout<<"栈已释放！"<<endl;
        return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220727/8579d938758b4fdb84273c59d0f61cc4.png