线性表之链式栈

• 插入操作和删除操作均在链表头部进行，链表尾部就是栈底，栈顶指针就是头指针
• 不需要预先分配固定大小
• 动态增长和收缩

typedefintdata_t;/*定义栈中数据元素数据类型*/typedefstructnode_t{data_tdata;/*数据域*/structnode_t*next;/*链接指针域*/}linkstack_t;/*链栈类型定义*/

• 功能实现

#include<stdio.h>#include<stdlib.h>#include"linkstack.h"linkstackstack_create(){linkstack s;s=(linkstack)malloc(sizeof(listnode));if(s==NULL){printf("malloc failed\n");returnNULL;}s->data=0;s->next=NULL;returns;}intstack_push(linkstack s,data_tvalue){linkstack p;if(s==NULL){printf("s is NULL\n");return-1;}p=(linkstack)malloc(sizeof(listnode));if(p==NULL){printf("malloc failed\n");return-1;}p->data=value;//p->next = NULL;p->next=s->next;s->next=p;return0;}data_tstack_pop(linkstack s){linkstack p;data_tt;p=s->next;s->next=p->next;t=p->data;free(p);p=NULL;returnt;}intstack_empty(linkstack s){if(s==NULL){printf("s is NULL\n");return-1;}return(s->next==NULL?1:0);}data_tstack_top(linkstack s){return(s->next->data);}linkstackstack_free(linkstack s){linkstack p;if(s==NULL){printf("s is NULL\n");returnNULL;}while(s!=NULL){p=s;s=s->next;printf("free:%d\n",p->data);free(p);}returnNULL;}

• 头文件

typedefintdata_t;typedefstructnode{data_tdata;structnode*next;}listnode,*linkstack;linkstackstack_create();intstack_push(linkstack s,data_tvalue);data_tstack_pop(linkstack s);intstack_empty(linkstack s);data_tstack_top(linkstack s);linkstackstack_free(linkstack s);

• 测试文件

#include<stdio.h>#include<stdlib.h>#include"linkstack.h"intmain(intargc,constchar*argv[]){linkstack s;s=stack_create();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));}s=stack_free(s);return0;}