资源描述：
《链队列的基本操作》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构刘家芬Sept2012第三章栈和队列栈和队列也是线性表栈和队列的基本操作是线性表操作的子集栈和队列是两种应用非常广泛的数据结构本章目标栈和队列的基本概念栈和队列的存储结构栈和队列的基本操作栈和队列的操作实现栈的概念栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。又称后进先出LIFO(LastInFirstOut)线性表先进后出FILO(FirstInLastOut)线性表a1a2a3an栈底栈顶出栈进栈栈顶和栈底允许插入和删除的一端称为栈顶(top)，也叫表尾；另一端称为栈底(
2、bottom)。指示栈顶位置的指针称为栈顶指针top。栈底也可以用一个指针bottom来指示。当表中没有元素时称为空栈。栈的基本操作入栈和出栈初始化栈判断元素个数取栈顶元素a1a2aian⋯⋯⋯⋯bottomtop进栈（push）出栈(pop)栈的抽象数据类型定义ADTStack{数据对象：D={ai
3、ai∈ElemSet,i=1,2,…,n，n≥0}数据关系：R={
4、ai∈D,i=2,3,…,n}基本操作：InitStack(&S)DestroyStack(&S)ClearSta
5、ck(&S)StackEmpty(S)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTraverse(S,visit());}ADTStack栈的表示和实现与线性表类似，栈也有两种存储表示方法栈的顺序存储结构栈的链式存储结构栈的顺序存储结构和线性表类似，栈的顺序存储结构也是利用一组连续的存储单元依次存放从栈底到栈顶的数据元素，我们称为顺序栈。#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;ty
6、pedefstruct{SElemType*base;//栈底指针SElemType*top;//栈顶指针intstacksize;//栈的当前最大可用容量}SqStack;SqStackS;栈的顺序存储结构base称为栈底指针，始终指向栈底；当base=NULL时，表明栈结构不存在。top为栈顶指针a.top的初始值指向栈底，即top=baseb.空栈：当top=base时为栈空的标记c.当栈非空时，top的位置：指向当前栈顶元素的下一个位置stacksize——当前栈可使用的最大容量进栈、出栈操
7、作空栈bottomtop元素a进栈bottomtopa元素b，c进栈bottomtopabc元素c出栈bottomtopabbottomtopabdef元素d，e，f进栈进栈、出栈操作说明栈空条件s.top=s.base，此时不能出栈栈满条件s.top-s.base>=s.stacksize，此时不能进栈进栈操作*s.top=e;s.top++;退栈操作s.top--；e=*s.top；当栈满时再做进栈运算会产生空间溢出。当栈空时再做退栈运算也会产生溢出。顺序栈基本操作算法——构造空栈顺序栈基本操作
8、算法——取栈顶元素顺序栈基本操作算法——入栈顺序栈基本操作算法——出栈栈的链式存储表示栈的链式存储结构称为链栈，其插入和删除操作只能在表头位置上进行。链栈的头结点在栈底，栈顶指针top用于标识整个链表。空栈top⋀非空栈topa3a2⋀a1栈的链式存储表示链栈的结点类型说明如下：typedefstructStackNode{SElemTypedata;structStackNode*next;}StackNode,*StackPtr;StackPtrS;链栈的基本操作——初始化StatusInitS
9、tack(StackPtr&S){S=(StackPtr)malloc(sizeof(StackNode));if(!S)returnERROR;S->next=NULL;returnOK;}链栈的基本操作——入栈StatusPush(StackPtr&S,SElemTypee){p=(StackPtr)malloc(sizeof(StackNode));if(!p)returnERROR;p->data=e;p->next=S;S=p;returnOK;}SpeS链栈的基本操作——出栈Status
10、Pop(StackPtr&S,SElemType&e){if(!(S->next)
11、
12、!S)returnERROR;//空栈p=S;e=S->data;S=S->next;free(p);returnOK;}栈的应用举例——数制转换十进制整数N向d进制数的转换（d=2,8,16)是计算机的一个基本问题。转换规则对应于一个简单算法原理:n=(ndivd)*d+nmodd其中：div为整除运算,mod为求余运算例如(255)10=(？)8nndiv8nmod8255317
