顺序栈及其实现过程
目录
一、概念
二、顺序栈
2.1顺序栈的结构模型
2.2顺序栈的实现
2.2.1创建
2.2.2判断栈是否为空
2.2.3判断栈是否为空
2.2.4入栈
2.2.5出栈
2.2.6查看栈顶
2.2.7清空栈
2.2.8释放栈
一、概念
栈是限制在某一端进行插入、删除操作的线性表，俗称堆栈，允许操作的一端称为“栈顶”，另一固定端称为“栈底”，当栈中没有元素时称为“空栈”，栈的明显特点是“后入先出” （LIFO）
二、顺序栈
2.1顺序栈的结构模型
typedef int data_t;typedef struct{data_t *data;//指向栈的存储空间int maxlen; //当前栈的最大元素个数int top; //栈顶位置---类似数组下标
}sqstack;
不难看出有顺序表的影子，栈的存储空间就可以看作一张顺序表，只不过因为是栈，对于插入、取出操作有限制，另外还多了栈顶指针的概念
2.2顺序栈的实现
sqstack.h
typedef int data_t;typedef struct{data_t *data;//指向栈的存储空间int maxlen; //当前栈的最大元素个数int top; //栈顶位置---类似数组下标
}sqstack;sqstack* SqStack_create(int maxlen); //创建顺序栈，创建时指定存储空间大小
int SqStack_push(sqstack *s, data_t value); //入栈
data_t SqStack_pop(sqstack *s); //出栈
int SqStack_is_empty(sqstack *s); //判断栈是否为空
int SqStack_is_full(sqstack *s); //判断栈是否已满
data_t SqStack_seetop(sqstack *s); //查看栈顶
data_t SqStack_clear(sqstack *s); //清空栈
data_t SqStack_free(sqstack *s); //释放栈空间2.2.1创建
根据2.1顺序栈的结构模型可知，创建时需要分配两块内存空间，因此要malloc申请两次
sqstack* SqStack_create(int maxlen)
{sqstack *s;//创建栈结构s = (sqstack*)malloc(sizeof(sqstack));if(s == NULL){printf("SqStack_create:malloc sqstack failed!\n");return NULL;}//初始化栈结构 存储空间申请和清空、赋值maxlen、tops->data = (data_t*)malloc(maxlen * sizeof(data_t));if(s->data == NULL){printf("SqStack_create:malloc data space failed!\n");free(s);//存储空间都申请失败了 申请的栈结构空间也没必要了 直接释放避免内存泄漏s = NULL;return NULL;}memset(s->data,0,maxlen * sizeof(data_t));s->maxlen = maxlen;s->top = -1;//0是栈底 maxlen-1是栈顶！！！return s;
}2.2.2判断栈是否为空
int SqStack_is_empty(sqstack *s)
{//参数检查if(s == NULL){printf("SqStack_is_empty:sqstack passed is NULL!\n");return -1;}return (s->top == -1? 1 : 0);
}2.2.3判断栈是否为空
int SqStack_is_full(sqstack *s)
{//参数检查if(s == NULL){printf("SqStack_is_full:sqstack passed is NULL!\n");return -1;}return (s->top == s->maxlen-1? 1 : 0);
}2.2.4入栈
其实就和顺序表插入数据元素差不多，注意判断栈是否满了
int SqStack_push(sqstack *s, data_t value)
{//参数检查if(s == NULL){printf("SqStack_push:sqstack passed is NULL!\n");return -1;}//判断栈是否满了if(s->top == s->maxlen-1){printf("SqStack_push:sqstack is full!\n");return -1;}//入栈s->top++;s->data[s->top] = value;return 1;
} 2.2.5出栈
data_t SqStack_pop(sqstack *s)
{//参数检查if(s == NULL){printf("SqStack_pop:sqstack passed is NULL!\n");return -1;}s->top--;//执行出栈操作时 应由程序员自行检查栈是否为空 下面的检查是避免越界if(s->top < -1){s->top = -1;}return (s->data[s->top+1]);
}2.2.6查看栈顶
data_t SqStack_seetop(sqstack *s)
{//参数检查if(s == NULL){printf("SqStack_seetop:sqstack passed is NULL!\n");return -1;}return (s->data[s->top]);
}2.2.7清空栈
data_t SqStack_clear(sqstack *s)
{//参数检查if(s == NULL){printf("SqStack_clear:sqstack passed is NULL!\n");return -1;}memset(s->data,0,(s->maxlen) * sizeof(data_t));s->top = -1;return 1;
} 2.2.8释放栈
data_t SqStack_free(sqstack *s)
{//和创建相反 倒推回去释放所malloc的内存if(s == NULL)//参数检查{printf("SqStack_free:sqstack passed is NULL!\n");return -1;}if(s->data != NULL)//创建当中已经处理了为空的结果 malloc--free操作配对{free(s->data);}free(s);return 1;
}