顺序栈及其实现过程

目录

一、概念

二、顺序栈

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;   
}