数据结构学习笔记-栈的顺序存储（C语言实现）

栈的模式是后进先出，就是最后插入的在最上面。其原理就一个只在表尾进行插入和删除的线性表。把允许插入的一端叫做栈顶，另一端叫做栈尾。数据数量在一定范围内推荐使用顺序栈，反之则使用链栈

栈作为一种特殊的线性表，也拥有顺序存储和链式存储。下面为顺序存储（该顺序表忘记定义表长度了，只定义了数组长度）：

#include <stdio.h>
#include <stdlib.h>
#define StackSize 5
typedef int SEletype;
typedef struct{
    SEletype data[StackSize];
    int top;
}StackList;
//初始化栈,栈顶指向数组最后面的数据下标
StackList init(){
    StackList sl;
    sl.top=-1;
    return sl;
}
//清空栈
void cleanSList(StackList *s){
    s->top=-1;
}
//判断该栈是否为空
int StackEmpty(StackList s){
    if(s.top==-1){
        return 0;
    }else{
        return 1;
    }
}
//获取栈顶元素
void getTop(StackList s,SEletype *e){
    *e=s.data[s.top];
}
//获取栈元素的个数
int stackLength(StackList s){
    return s.top+1;
}
void insertELE(StackList *s,SEletype e){
    if(s->top==StackSize-1){
        printf("该栈已满，无法插入");
    }else{
        s->top++;
        s->data[s->top]=e;
    }
}
void deleteEle(StackList *s,SEletype *e){
    if(s->top==-1){
        printf("该栈是空栈");
    }else{
        *e=s->data[s->top];
        s->top--;
    }
}
int main()
{
    StackList sl;
    SEletype e=100,s,d;
    sl=init();
    insertELE(&sl,e);
    printf("栈的状态：%d\n",StackEmpty(sl));
    getTop(sl,&s);
    printf("栈顶的值：%d\n",s);
    printf("栈的元素个数：%d\n",stackLength(sl));
    deleteEle(&sl,&d);
    printf("删除的元素：%d\n",d);
    printf("栈的元素个数：%d\n",stackLength(sl));
    return 0;
}

像这种顺序栈有一些缺陷，就是当栈满时，不能改变栈的大小，所以只能尽量给适当大小的空间，但还是会造成空间的浪费或不足，这时就可以让两个栈存在一个数组中，栈顶分别在数组的两端，向栈插入数据时，两个栈顶之间的距离会越来越小，直至栈满。像这种就叫做两栈共享空间。通常都是当两个栈的空间大小有相反关系时，才会使用这个共享空间栈。

#include <stdio.h>#include <stdlib.h>#define DStackSize 10typedef int DSEletype;typedef struct{    DSEletype data[DStackSize];    int top1;    int top2;}DStackList;//两栈共享空间初始化,两个栈都为空，所以第一个栈的栈顶为-1，第二个栈的栈顶为数组最大长度DStackList initD(){    DStackList ds;    ds.top1=-1;    ds.top2=DStackSize;    return ds;}//需要指定要插入的栈void insertDSEle(DStackList *ds,DSEletype dse,int stackNumber){    if(ds->top1+1==ds->top2){        printf("两个栈都满了，无法插入");    }else{        if(stackNumber==1){            ds->top1++;            ds->data[ds->top1]=dse;        }else if(stackNumber==2){            ds->top2--;            ds->data[ds->top2]=dse;        }    }}//删除时同样需指定栈void deleteDSEle(DStackList *ds,DSEletype *dse,int stackNumber){    if(ds->top1==-1&&ds->top2==DStackSize){        printf("两栈都为空");    }else{        if(stackNumber==1){            *dse=ds->data[ds->top1];            ds->top1--;        }else if(stackNumber==2){            *dse=ds->data[ds->top2];            ds->top2++;        }    }}void getDTop(DStackList ds,DSEletype *dse,int stackNumber){    if(ds.top1==-1&&ds.top2==DStackSize){        printf("两栈都为空");    }else{        if(stackNumber==1){            *dse=ds.data[ds.top1];        }else if(stackNumber==2){            *dse=ds.data[ds.top2];        }    }}void main(){    DStackList ds;    ds=initD();    DSEletype is,de,ge;    is=666;    insertDSEle(&ds,is,1);    getDTop(ds,&ge,1);    printf("获取栈顶值：%d\n",ge);    deleteDSEle(&ds,&de,1);    printf("删除值：%d\n",de);    getDTop(ds,&ge,1);    printf("获取栈顶值：%d\n",ge);}