数据结构DS03-栈和队列

《数据结构DS03-栈和队列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、栈（Stack）栈的应用队列（Queue）队列的应用第三章栈和队列定义3.1栈与线性表相同，数据元素之间仍为一对一的关系。用顺序栈或链栈存储均可。只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。关键是编写入栈、出栈等函数，具体实现按顺序栈或链栈的存储结构的不同而不同。存储结构运算规则实现方式逻辑结构限定只能在表的一端进行插入和删除运算的线性表。基本操作建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。栈是仅在表尾进行插入、删除操作的线性表。表尾(即an端)称为栈顶(top);表头(即a1端)称为栈底(bottom)。例如：栈

2、S=(a1,a2,a3,……….,an-1,an)插入元素到栈顶的操作，称为入栈。从栈顶删除元素的操作，称为出栈。an称为栈顶元素a1称为栈底元素强调：插入和删除都只能在表的一端（栈顶）进行！栈的基本操作InitStack(S)：构造一个空栈SClearStack(S)：清除栈S中的所有元素StackEmpty(S)：判断栈S是否为空，若为空，则返回true；否则返回falseGetTop(S)：返回S的栈顶元素，但不移动栈顶指针Push(S,x)：插入元素x为新的栈顶元素（入栈操作)Pop(S)：删除S的栈顶元素并返回其值（出栈操作）顺序栈的存储结构和操作的实

3、现顺序栈:是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。在C语言中，预设一个数组的最大空间,栈底设置在0下标端，栈顶随着插入和删除元素而变化，用一个整型变量top来指示栈顶的位置。a1a2……an顺序栈Sai……0n栈底栈顶top压入(PUSH):S[++top]=an+1弹出(POP):e=S[top--]顺序栈存储结构的描述：#defineMaxsize100/*设顺序栈的最大长度为100，可依实现情况而修改*/typedefintdatatype;typedefstruct{datatypestack[Maxsize];inttop；/*栈顶

4、指针*/}SeqStack；/*顺序栈类型定义*/SeqStack*s；/*s为顺序栈类型变量的指针*/顺序栈的几种状态以及在这些状态下栈顶指针top和栈中结点的关系栈为空的条件：top==-1;栈满的条件：top==Maxsize-1若入栈动作使地址向高端增长，称为“向上生成”的栈；若入栈动作使地址向低端增长，称为“向下生成”的栈；对于向上生成的堆栈:入栈：栈指针top“先加后压”:S[++top]=an+1出栈：栈指针top“先弹后减”:e=S[top--]顺序栈的基本操作构造一个空顺序栈SeqStack*InitStack(){SeqStack*S;S=(

5、SeqStack*)malloc(sizeof(SeqStack));if(!S){printf(“空间不足”)；returnNULL;}else{S->top=-1;returnS;}}取顺序栈栈顶元素datatypeGetTop(SeqStack*S){if(S->top==-1){printf("栈是空的!");returnFALSE;}elsereturnS->stack[S->top];}判别空栈intStackEmpty(SeqStack*S){if(S->top==-1)returnTRUE;elsereturnFALSE;}顺序栈的入栈操作—

6、—例如用堆栈存放（A，B，C，D）AACBABAtop核心语句：顺序栈入栈函数PUSH（）SeqStack*Push(SeqStack*S，datatypex){if(S->top==Maxsize-1) returnNULL;/*栈满*/else{S->top++;S->stack[S->top]=x;returns;}}Push(B);Push(C);Push(D);toptoptoptop低地址LPush(A);高地址MBCD顺序栈出栈操作——例如从栈中取出‘B’DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD核心语句：Pop()

7、;顺序栈出栈函数POP()datatypePop(SeqStack*S){if(S->top==-1)/*栈空*/{printf("Thesequencestackisempty!");returnFALSE;}else{S->top--;returnS->stack[S->top+1];}}Pop();Printf(Pop());链栈链栈的构造方式——用top指向栈顶，只能在栈顶插入或删除。栈顶栈底栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈。topa1a2an-1annextdata链栈中每个结点由两个域构成：data域和next域，其定义为：

8、Typedefstruc