数据结构---------------------------------------顺序栈和链栈的实现

今天想把这个顺序栈实现一下，就翻阅资料整理了一下。

下面分别给出顺序栈和链栈的相应功能的实现。

1）顺序栈的图示：

下面是代码：

#include<iostream>
#include<algorithm>
#include<string.h>
#define MAXSIZE 100
using namespace std;
typedef int SElemType;
typedef int Status;
typedef struct
{
    SElemType *base; //栈底指针
    SElemType *top; //栈顶指针
    int stacksize;
}SqStack;
//顺序栈的初始化
Status InitStack(SqStack &S)
{
    S.base = new SElemType[MAXSIZE]; //为顺序栈分配一个大小为MAXSIZE的数组空间
    if(!S.base)
        return 0;
    S.top = S.base; //栈底和栈顶指针都指向栈底的位置
    S.stacksize = MAXSIZE; //栈的容量为MAXSIZE
    return 1;
}
//判断栈是否为空
int StackEmpty(SqStack S)
{
    if(S.top == S.base)
        return 0;
    else
        return 1;
}
//求顺序栈的长度
int StackLength(SqStack S)
{
    return S.top - S.base;
}
//清空顺序栈
Status ClearStack(SqStack &S)
{
    if(S.base)
        S.top = S.base;
    return 1;
}
//顺序栈入栈
Status StackPush(SqStack &S,SElemType e) //将元素e压入栈顶
{
    if(S.top - S.base == S.stacksize) //栈满的情况
        return 0;
    *S.top++=e; //将元素e压入栈顶并使栈顶指针加1
    return 1;
}
//顺序栈的出栈
Status StackPop(SqStack &S,SElemType &e)
{
    if(S.top == S.base) //栈空的情况
        return 0;
    e = *--S.top; //获取栈顶元素e并使栈顶指针减1
    return 1;
}
//取顺序栈栈顶元素
Status GetTop(SqStack S,SElemType &e)
{
    if(S.top == S.base)
        return 0; //这种情况说明栈空，直接退出
    e = *(S.top - 1);
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    SqStack S;
    InitStack(S);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) //往栈中压入n个元素
        StackPush(S,i);
    int t;
    cin>>t;
    while(t--) //弹出栈中t个元素即依次取栈顶元素
    {
        int m;
        cin>>m;
        StackPop(S,m);
        cout<<m<<endl;
    }
    cout<<StackLength(S)<<endl; //输出操作之后栈的长度
    if(StackEmpty(S))
        cout<<"此时栈非空!"<<endl;
    else
        cout<<"栈空!"<<endl;
    ClearStack(S); //清空栈
    if(StackEmpty(S))
        cout<<"此时栈非空!"<<endl;
    else
        cout<<"栈空!"<<endl;
    return 0;
}