栈的定义及基本操作

1、初始条件：栈不存在 操作结果：构造了一个空栈 若栈空，则返回为 1，否则返回 0初始条件：栈S已经存在 操作结果：在栈S的顶部插入一 个元素x，这样x就、成为新的栈顶元素。出栈： Pop_Stack(S,&x) 从栈顶删除，保存在变量 x 中 取栈顶元素： GetTop_Stack(S) 顶元素，且原栈的结构不会变化 销毁栈： Destory_Stack(S) 在的栈 栈的存储方式： (1)顺序存储 下面我分别介绍这两种的实现： 顺序存储顺序存储中用 int dataSTACKSIZE 来存放所有的入栈元素，栈底的位置可以设置固 定在数组的任意一端，栈顶指示实际的栈顶元素位置，它是随着插入和删

2、除是动态变化的， 用 int top 变量来指示栈顶的位置 将 data 和 top 封装在一个结构中#define MAXSIZE 100初始条件：栈初始条件：初始条件：S存在且不为空操作结果：栈S的顶部元素栈s存在且不为空 操作结果：返回栈S的栈栈 S 已经存在 操作结果： 销毁一个已经存2)链式存储栈的定义及基本操作在数据结构中， 栈是限制在表的一端进行插入和删除的线性表。 在线性表中允许插入、 删除 的这一端称为栈顶， 栈顶的当前位置是动态变化的， 这样我们只能在栈顶对栈进行操作； 不 允许插入和删除的另一端称为栈底，栈底是固定不变得，当表中没有元素时称为空栈。对栈的常用操作有： 栈初

3、始化： Init_Stack() 判断空： Empty_Stack() 入栈： Push_Stack(S,x) typedefDataTypedataSTACKSIZE;int top;SeqStack,*PSeqStack ； 下面用一个实例介绍栈的一些基本操作(经过测试 )：#include#include#include#define STACKSIZE 100typedefstructint dataSTACKSIZE;int top;SeqStack,*PSeqStack;PSeqStackInit_SeqStack()PSeqStack S;S=(PSeqStack)malloc(

4、sizeof(SeqStack);if(S!=NULL)S-top=-1;return S;intEmpty_SeqStack(PSeqStack S)if(S-top=-1)return 1;else return 0;intPush_SeqStack(PSeqStackS,int x)if(S-top=STACKSIZE-1)return 0;elseS-top+;S-dataS-top=x;return 1;intPop_SeqStack(PSeqStackS,int *x) if(Empty_SeqStack(S)=1)return 0;else*x=S-dataS-top;S-top

5、-;return 1; intGetTop_SeqStack(PSeqStack S)if(Empty_SeqStack(S)=1) printf(Empty Stack!n);return -1;elsereturn S-dataS-top;intDestory_SeqStack(PSeqStack *S)if(*S)free(*S);*S=NULL;return 1;return 0;int main()PSeqStack s;int x=0;s=Init_SeqStack();Push_SeqStack(s,1);Push_SeqStack(s,2);Push_SeqStack(s,3)

6、;Push_SeqStack(s,4);printf(Top:%d ,GetTop_SeqStack(s);Destory_SeqStack(&s);return 1;链式存储栈的链式存储一般用单链表来实现，实现代码如下： #include#include#include#define STACKSIZE 100 typedefstructLinkStack int data;structLinkStack *next;LinkStackNode,*PLinkStackNode; typedefstructPLinkStackNode top;LinkStack,*PLinkStack; PL

7、inkStackInit_LinkStack()PLinkStack s;s=(PLinkStack)malloc(sizeof(LinkStack);if(s) s-top=NULL;return s;intEmpty_LinkStack(PLinkStack S)if(S-top=NULL)return 1;else return 0;intPush_LinkStack(PLinkStackS,int x)PLinkStackNode p; p=(PLinkStackNode)malloc(sizeof(LinkStackNode); if(p!=NULL)p-data=x; p-next

8、=S-top;S-top=p;return 1;else return 0;intPop_LinkStack(PLinkStackS,int *x) PLinkStack p;if(Empty_LinkStack(S)=1) return 0;elsep=S;*x=S-top-data;S-top=S-top-next;free(p);return 1; intGetTop_LinkStack(PLinkStack S) if(Empty_LinkStack(S)=1) printf(Empty Stack!n);return -1;elsereturn S-top-data; intDestory_LinkStack(PLinkStack *S) PLinkStackNodep,q;if(*S)p=(*S)-top;while(p)q=p;p=p-next;free(q);free(*S);*S=NULL;return 1;int main()PLinkStack s;int x=0;s=Init_LinkStack();Push_LinkSt