栈（栈（StackStack））栈的应用栈的应用队列（队列（QueueQueue））队列的应用队列的应用第三章栈和队列定义3.13.1栈栈与线性表相同，仍为一对一(1:1)关系。用顺序栈顺序栈或链栈链栈存储均可，但以顺序栈更常见只能在栈顶栈顶运算，且访问结点时依照后进先出后进先出（LIFO）或先进后出先进后出（FILO）的原则。关键是编写入栈入栈和出栈出栈函数，具体实现依顺序栈或链栈的存储结构有别而不同。存储结构运算规则实现方式逻辑结构限定只能在表的一端一端进行插入和删除运算的线性表。基本操作建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。栈栈是仅在表尾进行插入、删除操作的线性表。表尾(即an端)称为栈顶/top;表头(即a1端)称为栈底/base例如：栈SS=(a1,a2,a3,……….,an-1,an)插入元素到栈顶的操作，称为入栈栈。从栈顶删除最后一个元素的操作，称为出栈。an称为栈顶元素a1称为栈底元素强调：强调：插入和删除都只能在表的一端（栈顶）进行！栈的基本操作•ClearStack(S)：清除栈S中的所有元素•InitStack(S)：构造一个空栈S•StackEmpty(S)：判断栈S是否为空，若为空，则返回true；否则返回false•GetTop(S)：返回S的栈顶元素，但不移动栈顶指针•Push(S,x)：插入元素x为新的栈顶元素（入栈操作)•Pop(S)：删除S的栈顶元素并返回其值（出栈操作）顺序栈的存储结构和操作的实现顺序栈:是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。在在CC语言中，预语言中，预设一个数组的最设一个数组的最大空间大空间,,栈底设栈底设置在置在00下标端，下标端，栈顶随着插入和栈顶随着插入和删除元素而变化，删除元素而变化，用一个整型变量用一个整型变量ttopop来指示栈顶的来指示栈顶的位置位置。a1a2……an顺序栈Sai……0n栈底栈顶toptop压入(PUSH):PUSH):S[toptop++]=an+1弹出(POP)POP)::e=Se=S[--toptop]顺序栈存储结构的描述：#defineMaxsize100#defineMaxsize100/*设顺序栈的最大长度为100，可依实现情况而修改*/typedefintdatatype;typedefintdatatype;typedefstructtypedefstruct{{datatypestack[Maxsize];datatypestack[Maxsize];inttopinttop；；/*栈顶指针*/}SeqStack}SeqStack；；/*顺序栈类型定义*/SeqStack*sSeqStack*s；；/*s为顺序栈类型变量的指针*/顺序栈的几种状态以及在这些状态下栈顶指针top和栈中结点的关系栈为空的条件：top==0;栈满的条件：top-base==Maxsize若入栈动作使地址向高端增长，称为“向上生成”的栈；若入栈动作使地址向低端增长，称为“向下生成”的栈；对于向上生成的堆栈:入栈：栈指针top“先压后加”:S[top++]=an+1出栈：栈指针top“先减后弹”:e=S[--top]顺序栈的基本操作构造一个空顺序栈SeqStack*InitStack(){SeqStack*S;S=(SeqStack*)malloc(sizeof(SeqStack));if(!S){printf(“空间不足”)；returnNULL;}else{S->top=0;returnS;}}取顺序栈栈顶元素datatypeGetTop(SeqStack*S){if(S->top==0){printf("\n栈是空的!");returnFALSE;}elsereturnS->stack[S->top-1];}判别空栈intStackEmpty(SeqStack*S){if(S->top==0)returnTRUE;elsereturnFALSE;}顺序栈的入栈操作——例如用堆栈存放（A，B，C，D）AACBABAtop核心语句：顺序栈入栈函数PUSH（）SeqStack*Push(SeqStack*S，datatypex){if(S->top==Maxsize)returnNULL;else{S->stack[S->top]=x;S->top++;returns;}}Push(B);Push(C);Push(D);toptoptoptop低地址LPush(A);高地址MBCD顺序栈出栈操作——例如从栈中取出‘BB’DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD核心语句：Pop();顺序栈出栈函数POP()datatypePop(SeqStack*S){if(S->top==0){printf("\nThesequencestackisempty!");returnFALSE;}S->top--;returnS->stack[S->top];}Pop();Printf(Pop());链栈的入栈操作和出栈操作链栈的构造方式——以头指针为栈顶，在头指针处插入或删除.栈顶栈底栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈toptopa1a2an-1annextdata链栈中每个结点由两个域构成：data域和next域，其定义为：Typedefstructnode{datatypedata;structnode*next;}LinkStack;LinkStack*...
