栈的定义及基本操作.docx

《栈的定义及基本操作.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、栈的定义及基本操作在数据结构中，栈是限制在表的一端进行插入和删除的线性表。在线性表中允许插入、删除的这一端称为栈顶，栈顶的当前位置是动态变化的，这样我们只能在栈顶对栈进行操作；不允许插入和删除的另一端称为栈底，栈底是固定不变得，当表中没有元素时称为空栈。对栈的常用操作有：栈初始化：Init_Stack()初始条件：栈不存在操作结果：构造了一个空栈判断空：Empty_Stack()若栈空，则返回为1，否则返回0入栈：Push_Stack(S,x)初始条件：栈S已经存在操作结果：在栈S的顶部插入一个元素x，这样x就、成为新的栈顶元素。出栈：Pop_Stack(S,&x)初始条件：栈S存在且不为

2、空操作结果：栈S的顶部元素从栈顶删除，保存在变量x中取栈顶元素：GetTop_Stack(S)初始条件：栈s存在且不为空操作结果：返回栈S的栈顶元素，且原栈的结构不会变化销毁栈：Destory_Stack(S)初始条件：栈S已经存在操作结果：销毁一个已经存在的栈栈的存储方式：（1）顺序存储（2）链式存储下面我分别介绍这两种的实现：顺序存储顺序存储中用intdata[STACKSIZE]来存放所有的入栈元素，栈底的位置可以设置固定在数组的任意一端，栈顶指示实际的栈顶元素位置，它是随着插入和删除是动态变化的，用inttop变量来指示栈顶的位置将data和top封装在一个结构中#defineMA

3、XSIZE100typedef{DataTypedata[STACKSIZE];inttop;}SeqStack,*PSeqStack；下面用一个实例介绍栈的一些基本操作(经过测试)：#include#include#include#defineSTACKSIZE100typedefstruct{intdata[STACKSIZE];inttop;}SeqStack,*PSeqStack;PSeqStackInit_SeqStack(){PSeqStackS;S=(PSeqStack)malloc(sizeof(SeqStack))

4、;if(S!=NULL)S->top=-1;returnS;}intEmpty_SeqStack(PSeqStackS){if(S->top==-1)return1;elsereturn0;}intPush_SeqStack(PSeqStackS,intx){if(S->top==STACKSIZE-1)return0;else{S->top++;S->data[S->top]=x;return1;}}intPop_SeqStack(PSeqStackS,int*x){if(Empty_SeqStack(S)==1)return0;else{*x=S->data[S->top];S->to

5、p--;return1;}}intGetTop_SeqStack(PSeqStackS){if(Empty_SeqStack(S)==1){printf("EmptyStack!");return-1;}elsereturnS->data[S->top];}intDestory_SeqStack(PSeqStack*S){if(*S){free(*S);*S=NULL;return1;}return0;}intmain(){PSeqStacks;intx=0;s=Init_SeqStack();Push_SeqStack(s,1);Push_SeqStack(s,2);Push_Seq

6、Stack(s,3);Push_SeqStack(s,4);printf("Top:%d",GetTop_SeqStack(s));Destory_SeqStack(&s);return1;}链式存储栈的链式存储一般用单链表来实现，实现代码如下：#include#include#include#defineSTACKSIZE100typedefstructLinkStack{intdata;structLinkStack*next;}LinkStackNode,*PLinkStackNode;typedefstruct{PLinkS

7、tackNodetop;}LinkStack,*PLinkStack;PLinkStackInit_LinkStack(){PLinkStacks;s=(PLinkStack)malloc(sizeof(LinkStack));if(s)s->top=NULL;returns;}intEmpty_LinkStack(PLinkStackS){if(S->top==NULL)return1;elsereturn0;}int