线性表之顺序栈

• 栈是限制在一端进行插入操作和删除操作的线性表（俗称堆栈）
• 允许进行操作的一端称为”栈顶“
• 另一固定端称为”栈底“
• 当栈中没有元素时称为”空栈“
• 特点：后进先出（LIFO）或先进后出

• 顺序栈是顺序表的一种，具有顺序表同样的存储结构，由数组定义，配合用数组下标表示的栈顶指针top（相对指针）完成各种操作

typedefintdata_t;/*定义栈中数据元素的数据类型*/typedefstruct{data_t*data;/*用指针指向栈的存储空间*/intmaxlen;/*当前栈的最大元素个数*/inttop;/*指示栈顶位置(数组下标)的变量*/}sqstack;/*顺序栈类型定义*/

顺序栈

功能代码

#include<stdio.h>#include<stdlib.h>#include<string.h>#include"sqstack.h"sqstack*stack_create(intlen){sqstack*s;if((s=(sqstack*)malloc(sizeof(sqstack)))==NULL){printf("malloc sqstack failed\n");returnNULL;}if((s->data=(data_t*)malloc(len*sizeof(data_t)))==NULL){printf("malloc data failed\n");free(s);returnNULL;}memset(s->data,0,len*sizeof(data_t));s->maxlen=len;s->top=-1;returns;}intstack_push(sqstack*s,data_tvalue){if(s==NULL){printf("s is NULL\n");return-1;}if(s->top==s->maxlen-1){printf("stack is full\n");return-1;}s->top++;s->data[s->top]=value;return0;}intstack_empty(sqstack*s){if(s==NULL){printf("s is NULL\n");return-1;}return(s->top==-1?1:0);}intstack_full(sqstack*s){if(s==NULL){printf("s is NULL\n");return-1;}return(s->top==s->maxlen-1?1:0);}data_tstack_pop(sqstack*s){s->top--;return(s->data[s->top+1]);}data_tstack_top(sqstack*s){return(s->data[s->top]);}intstack_clear(sqstack*s){if(s==NULL){printf("s is NULL\n");return-1;}s->top=-1;return0;}intstack_free(sqstack*s){if(s==NULL){printf("s is NULL\n");return-1;}if(s->data!=NULL){free(s->data);}free(s);return0;}

头文件

typedefintdata_t;typedefstruct{data_t*data;intmaxlen;inttop;}sqstack;sqstack*stack_create(intlen);intstack_push(sqstack*s,data_tvalue);intstack_empty(sqstack*s);intstack_full(sqstack*s);data_tstack_pop(sqstack*s);data_tstack_top(sqstack*s);intstack_clear(sqstack*s);intstack_free(sqstack*s);

测试文件

#include<stdio.h>#include"sqstack.h"intmain(intargc,constchar*argv[]){sqstack*s;s=stack_create(100);if(s==NULL)return-1;stack_push(s,10);stack_push(s,20);stack_push(s,30);stack_push(s,40);while(!stack_empty(s)){printf("pop: %d \n",stack_pop(s));}stack_free(s);return0;}