第三章栈和队列纲要从数据结构角度看，栈和队列是操作受限的线性表，他们的逻辑结构相同。栈只允许在表的一端进行插入或删除操作队列只允许在表的一端进行插入操作、而在另一端进行删除操作。3.1栈的逻辑结构3.1栈的逻辑结构3.1栈的逻辑结构3.1栈的逻辑结构3.1栈的逻辑结构3.1栈的逻辑结构3.1栈的逻辑结构3.2栈的顺序存储结构及实现3.2栈的顺序存储结构及实现（a）空栈(top=base或top=-1)；（b）插入元素A后；（c）插入元素B、C、D、E后(栈满)；（d）删除元素E、D后（e）删除元素C、B、A后（栈空）“上溢”-----当s.top=stacksize-1表示栈满，此时，再做进栈运算必定产生空间溢出，简称“上溢”“下溢”-----当s.top=s.base(或s.top=-1）时表示栈空，此时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。---（简易版）#definemaxsize100typedefstruct{//顺序栈定义ElemTypeelem[maxsize];//栈数组inttop;//栈顶指示器}SqStack;顺序栈的顺序存储表示---（完整版）#definestack_Init_Size100#defineStackIncreament10typedefstruct{//顺序栈定义ElemType*base;//栈底指示器ElemType*top;//栈顶示器intStackSize;//当前已分配的存储空间}SqStack;顺序栈的实现（1）初始化栈intPushStack(SqStack&s,Elemtypex){/*将元素x插入到栈s中，作为s的新栈顶*/if(s.top>=stacksize)returnFALSE;/*栈满*/s.elem[s.top]=x;s.top++;returnTRUE;}intPopStack(SqStack&s,Elemtype&x){/*若栈s不为空，则删除栈顶元素*/if(s.top<0)returnNULL;/*栈空*/s.top--;/*栈顶下移*/x=s.elem[s.top];/*取出栈顶元素*/returnok;}IntGetStackTop(SqStacks,Elemtype&x){/*若栈s不为空，则返回栈顶元素*/if(s.top==s.base)returnNULL;/*栈空*/return(s.elem[s.top-1]);/*取出栈顶元素*/}intEmpty(stack&s){/*栈s为空时，返回为TRUE；非空时，返回为FALSE*/if(s.top==s.base)returnTRUE;returnFALSE;}3.2栈的顺序存储结构及实现3.2栈的顺序存储结构及实现3.2栈的顺序存储结构及实现3.2栈的顺序存储结构及实现3.2栈的顺序存储结构及实现3.2栈的顺序存储结构及实现3.3栈的链式存储结构及实现3.3栈的链式存储结构及实现链栈中数据元素与栈顶指针top的关系：链栈的类型说明如下：typedefstructsnode{elemtypedata;structsnode*next;}StackNode,*LkStack;Voidinitstack(LkStack&ls){ls=null;}Voidgetstacktop(lkstack&ls){if(ls==null)error(“stackisempty.”);return(ls–>data);}3.3栈的链式存储结构及实现算法描述voidpop(LkStack&ls,elemtype&x)if(ls==NULL)returnNULL;p=ls;x=p->data;ls=ls->next;free(p);returnok;}3.3栈的链式存储结构及实现由于栈结构具有后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。3.4栈的应用算法Statusreverse(LinkList&L){Lkstackls;elemtypex;initstack(ls);//初始化栈p=L->next;while(p!=null){push(ls,p->data);p=p->next;}2.行编辑程序一个简单的行编辑程序功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。由于用户在终端上进行输入时，不能保证不出差错,如原为输入：while(*s)却输成：whl