弹出栈顶运算符数学与信息技术学院课件

数据结构

李萍

数据结构李萍第三章栈和队列主要学习内容:掌握栈和队列是两种操作受限的线性表掌握栈和队列的两种存储实现算法理解递归算法执行过程中栈的变化过程

第三章栈和队列主要学习内容:3.1栈1.概念是限定仅在表尾进行插入和删除操作的线性表.允许插入和删除的一端为栈顶（top),另一端称为栈底（bottom).2.图示一、定义an-1an-2…a1a0bottomtop退栈（弹出）进栈（压入）3.1栈1.概念一、定义an-1an-2…a1a0bott3.特性逻辑结构：一对一存储结构：顺序和链式存储（顺序栈和链栈）运算规则：先进后出基本操作：入栈、出栈、读栈顶、判栈空、判栈满等一、定义3.1栈3.特性一、定义3.1栈1.顺序栈的静态定义#defineMAXSIZE1024typedefstruct{datatypedata[MAXSIZE];inttop;}SqStack定义一个指向顺序栈的变量：

SqStacksq;二、栈的表示和实现（顺序栈）3.1栈1.顺序栈的静态定义二、栈的表示和实现（顺序栈）3.1栈2.顺序栈的基本操作栈空栈空：top=-10

栈满：top=sq.MAXSIZE-1读栈顶元素sq.data[top],top的值未变出栈sq.top--top的值改变入栈sq.top++sq.data[top]=e二、栈的表示和实现（顺序栈）3.1栈2.顺序栈的基本操作二、栈的表示和实现（顺序栈）3.1栈3.顺序栈的动态定义#defineMAXSIZE1024typedefstruct{datatype*base;datatype*top;intstacksize;}SqStack定义一个指向顺序栈的变量：

SqStacksq;二、栈的表示和实现（顺序栈）3.1栈3.顺序栈的动态定义二、栈的表示和实现（顺序栈）3.1栈4.顺序栈的基本操作栈空栈空：sq.top=sq.base栈满：sq.top–sq.base>=sq.stacksize读栈顶元素*sq.top,top的值未变出栈sq.top--入栈sq.top++*sq.top=e二、栈的表示和实现（顺序栈）3.1栈4.顺序栈的基本操作二、栈的表示和实现（顺序栈）3.1栈二、栈的表示和实现（链栈）Ntop空栈：top指向空无栈满:因为可以分配结点入栈：在栈顶进行入栈，相当于在链表头插入结点出栈：在栈顶进行出栈，相当于在链表头删除结点3.1栈二、栈的表示和实现（链栈）N3.1栈习题考题：1、若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（）A、dcebfaB、cbdaefC、bcaefdD、afedcb习题考题：一选择题1.对于栈操作数据的原则是（）。

A.先进先出B.后进先出C.后进后出D.不分顺序2.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。A.不确定B.n-i+1C.iD.n-i3.若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。

A.i-j-1B.i-jC.j-i+1D.不确定的一选择题1.对于栈操作数据的原则是（）。4.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）

A.543612B.453126C.346521D.2341565.输入序列为ABC，可以变为CBA时，经过的栈操作为（）

A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop4.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪6.若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是()。

A．top:=top+1;V[top]:=xB.V[top]:=x;top:=top+1C.top:=top-1;V[top]:=xD.V[top]:=x;top:=top-16.若一个栈以向量V[1..n]存储，初始栈顶指针top为1．在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。1．在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应3.2栈的应用1.数制转换（38）10=（）2基本思想：余数先进后出，符合栈的特点2.括号匹配基本思想：从左到右读取括号,不等于#就循环凡出现左括号，则进栈凡出现右括号，首先检查栈是否为空，若栈空，则表明该右括号多作，否则和栈顶元素比较；若相匹配，则左括号出栈，否则表明不匹配表达式检验结束时，若栈空，则表明表达式中匹配正确，否则左括号多余。3.2栈的应用1.数制转换3.2栈的应用3.表达式计算基本思想：需要两个栈：对象栈s1和算符栈s2。当自左至右扫描表达式的每一个字符时:若当前字符是运算对象，入对象栈，若是运算符时，若这个运算符比栈顶运算符高则入算符栈，继续向后处理，若这个运算符比栈顶运算符低则从对象栈出栈两个运算量，从算符栈出栈一个运算符进行运算，并将其运算结果入对象栈，继续处理当前字符。3.2栈的应用3.表达式计算3.2栈的应用3.表达式计算基本思想可以先转化为后缀表达式，再进行计算从左到右依次读取表达式如果是操作数直接输出到后缀表达式是左括号压栈是右括号，弹出栈顶运算符，若不是左括号，将弹出的栈顶运算符输出后缀字符中，重复此步，直到取到左括号，并将左右括号丢弃其它运算符（+-*/等）与栈顶运算符相比，如果高于栈顶运算符，则压栈；否则弹出栈顶元素，输出至后缀表达式读完表达式后，如果最后栈不空，将所有栈元素弹出至后缀表达式3.2栈的应用3.表达式计算3.2栈的应用3.表达式计算基本思想计算后缀表达式读后缀表达式，是操作数就压栈是运算符，则弹出栈顶的两个操作数计算，将结果再压入栈后缀表达式读，栈内即是表达式的值3.2栈的应用3.表达式计算3.3栈与递归的实现如图3。73.3栈与递归的实现如图3。7习题1.栈在（）中应用。

A.递归调用B.子程序调用

C.表达式求值D.A，Ｂ，Ｃ2.表达式a*(b+c)-d的后缀表达式是()。

A．abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd3.表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。（要求能画出栈的变化情况）

A.3,2,4,1,1；(*^(+*-B.3,2,8；(*^-C.3,2,4,2,2；(*^(-D.3,2,8；(*^(-习题1.栈在（）中应用。习题4.递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。

A．队列B．多维数组

C．栈D.线性表习题4.递归过程或函数调用时，处理参数及返回地址，要用一种共享栈1.设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。共享栈3.4队列一、定义队列是只允许在一端删除，另一端插入的线性表，允许删除的一端叫队头（front),允许插入的一端叫队尾（rear）.特点：先进先出a0，a1，a2，…，an-1，进队出队队首队尾3.4队列一、定义a0，a1，a2，…，an-1，3.4队列三、队列的顺序实现1.语言描述#defineMAXSIZE1024/*队列的最大容量*/typedefstruct{datatypedata[MAXSIZE];/*队员的存储空间*/intrear,front;/*队头队尾指针*/}SqQueue;

定义一个指向队的变量：

SqQueuesq;3.4队列三、队列的顺序实现3.4队列三、队列的顺序实现2.操作实现置空队sq.front=sq.rear=0入队sq.data[sq.rear]=xsq.rear++;出队sq.front--;

读队头、队尾sq.data[sq.front]sq.data[sq.rear-1]3.4队列三、队列的顺序实现3.4队列三、队列的顺序实现2.操作实现队中元素个数m=sq.rear-sq.front队满m==MAXSIZE队空m==03.4队列三、队列的顺序实现3.4队列三、队列的顺序实现2.操作实现存在的问题：假溢出sq.rear=m-1时，再入队时虽然前面有空间，但是尾指针已经接近空间的上界而不能再入队。frontrearBCD3.4队列三、队列的顺序实现frontrearBCD3.4队列三、队列的顺序实现2.操作实现假溢出解决方案：队首固定，每次出队剩余元素向下移动——浪费时间。循环队列基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;入队：sq.data[rear]=x;

sq.rear=(rear+1)%M;出队：sq.front=(front+1)%M;3.4队列三、队列的顺序实现3.4队列三、队列的顺序实现2.操作实现循环队列存在的问题：队空sq.front==sq.rear队满sq.front==sq.rear3.4队列三、队列的顺序实现3.4队列三、队列的顺序实现2.操作实现循环队列解决方案：另外设一个标志存储队中元素个数num==0代表队空，num==MAXSIZE代表队满少用一个元素空间：队空：front==rear

队满：(rear+1)%M==front3.4队列三、队列的顺序实现3.4队列四、循环队列的实现1.语言描述typedefstruct{datatypedata[M];intfront;intrear;intcount;//记录队中元素点数}cirqueue;3.4队列四、循环队列的实现3.4队列四、循环队列的实现2.基本操作入队voidenqueue（cirqueue*q,datatypex）{if(q->count==M)//判队满if((q.rear+1)%M==q.front){printf(“overflow“);exit(0);}q->data[q->rear]=x;q->rear=(q->rear+1)%M;//插入元素xq->count++;//修改表长}3.4队列四、循环队列的实现3.4队列四、循环队列的实现2.基本操作出队datatypedequeue(cirqueue*q){if(q->count==0)//判队空if((q.rear==q.front)){printf(“queuenull“);exit(0);}q->front=(q->front+1)%m;//删除队头元素

q->count--;//修改表长

return(q->data[q->font]);}3.4队列四、循环队列的实现3.4队列四、循环队列的实现2.基本操作读队头元素datatypegetqueue(cirqueueq){return(q.data[q.front]);}3.4队列四、循环队列的实现3.4队列五、链队列1.定义限制在表头删除，表尾插入的单链表。由一个头指针和一个尾指针确定链表的头和尾frontrear

datalink3.4队列五、链队列frontreardatalin3.4队列五、链队列2.语言描述结点类型描述typedefstructnode{datatypedata;structnode*next;}queuenode;头尾指针描述typedefstruct{queuenode*front;queuenode*rear;}linkqueue;3.4队列五、链队列头尾指针描述3.4队列五、链队列3.图示(a)非空队rearfronta1an∧

…a2rearfronta1∧

rearfront

∧(b)空队(c)链队中只有一个元素结点

头尾指针封装在一起的链队3.4队列五、链队列(a)非空队rearfronta1an∧3.4队列五、链队列4.算法实现创建一个带头结点的空队：

LinkQueue*Init_LQueue(){queuenode*s;linkqueuep;s=(queuenode*)malloc(sizeof(queuenode));//申请结点

s->next=NULL;p.front=s;p.rear=s;return&p;3.4队列五、链队列3.4队列五、链队列4.算法实现入队

voidIn_LQueue(linkqueue*q,datatypex){QNode*p;p=malloc(sizeof(QNnode));//申请新结点

p->data=x;p->next=q->rear->next;q->rear->next=p;//插入尾部

q->rear=p;//改变尾指针}3.4队列五、链队列3.4队列五、链队列4.算法实现出队intOut_LQueue(linkqueue*q,datatype*x){queuennode*p;if(Empty_LQueue(q)){printf(＂队空＂)；return0;}//队空，出队失败

else{p=q->front->next;q->front->next=p->next;*x=p->data;//队头元素放x中

free(p);if(q->front->next==NULL)q->rear=q->front;//只有一个元素时，出队后队空，此时还要要修改队尾指针参考

return1;}}3.4队列五、链队列习题考题：1.设栈S和队列Q的初始状态均为空，元素a，b，c，d，e，f，g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b，d，c，f，e，a，g，则栈S的容量至少是

A.1

B.2

C.3

D.4习题考题：习题考题：2、某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺顺序是（）A、bacdeB、dbaceC、dbcaeD、ecbad习题考题：习题1.用链接方式存储的队列，在进行删除运算时（）。

A.仅修改头指针B.仅修改尾指针

C.头、尾指针都要修改D.头、尾指针可能都要修改2.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时()。

A．仅修改队头指针B.仅修改队尾指针

C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改习题1.用链接方式存储的队列，在进行删除运算时（）习题3.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。

A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m17.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？()A.1和5B.2和4C.4和2D.5和118.若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是()。

A.1234B.4132C.4231D.4213习题3.假设以数组A[m]存放循环队列的元素,其头尾指针分1.已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_______。2．区分循环队列的满与空，只有两种方法，它们是______和______。3．设循环队列用数组A[1..M]表示，队首、队尾指针分别是FRONT和TAIL，判定队满的条件为_______。习题1.已知链队列的头尾指针分别是f和r，则将值x入队的操作序谢谢!谢谢!数据结构

李萍

数据结构李萍第三章栈和队列主要学习内容:掌握栈和队列是两种操作受限的线性表掌握栈和队列的两种存储实现算法理解递归算法执行过程中栈的变化过程

第三章栈和队列主要学习内容:3.1栈1.概念是限定仅在表尾进行插入和删除操作的线性表.允许插入和删除的一端为栈顶（top),另一端称为栈底（bottom).2.图示一、定义an-1an-2…a1a0bottomtop退栈（弹出）进栈（压入）3.1栈1.概念一、定义an-1an-2…a1a0bott3.特性逻辑结构：一对一存储结构：顺序和链式存储（顺序栈和链栈）运算规则：先进后出基本操作：入栈、出栈、读栈顶、判栈空、判栈满等一、定义3.1栈3.特性一、定义3.1栈1.顺序栈的静态定义#defineMAXSIZE1024typedefstruct{datatypedata[MAXSIZE];inttop;}SqStack定义一个指向顺序栈的变量：

SqStacksq;二、栈的表示和实现（顺序栈）3.1栈1.顺序栈的静态定义二、栈的表示和实现（顺序栈）3.1栈2.顺序栈的基本操作栈空栈空：top=-10

栈满：top=sq.MAXSIZE-1读栈顶元素sq.data[top],top的值未变出栈sq.top--top的值改变入栈sq.top++sq.data[top]=e二、栈的表示和实现（顺序栈）3.1栈2.顺序栈的基本操作二、栈的表示和实现（顺序栈）3.1栈3.顺序栈的动态定义#defineMAXSIZE1024typedefstruct{datatype*base;datatype*top;intstacksize;}SqStack定义一个指向顺序栈的变量：

SqStacksq;二、栈的表示和实现（顺序栈）3.1栈3.顺序栈的动态定义二、栈的表示和实现（顺序栈）3.1栈4.顺序栈的基本操作栈空栈空：sq.top=sq.base栈满：sq.top–sq.base>=sq.stacksize读栈顶元素*sq.top,top的值未变出栈sq.top--入栈sq.top++*sq.top=e二、栈的表示和实现（顺序栈）3.1栈4.顺序栈的基本操作二、栈的表示和实现（顺序栈）3.1栈二、栈的表示和实现（链栈）Ntop空栈：top指向空无栈满:因为可以分配结点入栈：在栈顶进行入栈，相当于在链表头插入结点出栈：在栈顶进行出栈，相当于在链表头删除结点3.1栈二、栈的表示和实现（链栈）N3.1栈习题考题：1、若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（）A、dcebfaB、cbdaefC、bcaefdD、afedcb习题考题：一选择题1.对于栈操作数据的原则是（）。

A.先进先出B.后进先出C.后进后出D.不分顺序2.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。A.不确定B.n-i+1C.iD.n-i3.若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。

A.i-j-1B.i-jC.j-i+1D.不确定的一选择题1.对于栈操作数据的原则是（）。4.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）

A.543612B.453126C.346521D.2341565.输入序列为ABC，可以变为CBA时，经过的栈操作为（）

A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop4.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪6.若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是()。

A．top:=top+1;V[top]:=xB.V[top]:=x;top:=top+1C.top:=top-1;V[top]:=xD.V[top]:=x;top:=top-16.若一个栈以向量V[1..n]存储，初始栈顶指针top为1．在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。1．在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应3.2栈的应用1.数制转换（38）10=（）2基本思想：余数先进后出，符合栈的特点2.括号匹配基本思想：从左到右读取括号,不等于#就循环凡出现左括号，则进栈凡出现右括号，首先检查栈是否为空，若栈空，则表明该右括号多作，否则和栈顶元素比较；若相匹配，则左括号出栈，否则表明不匹配表达式检验结束时，若栈空，则表明表达式中匹配正确，否则左括号多余。3.2栈的应用1.数制转换3.2栈的应用3.表达式计算基本思想：需要两个栈：对象栈s1和算符栈s2。当自左至右扫描表达式的每一个字符时:若当前字符是运算对象，入对象栈，若是运算符时，若这个运算符比栈顶运算符高则入算符栈，继续向后处理，若这个运算符比栈顶运算符低则从对象栈出栈两个运算量，从算符栈出栈一个运算符进行运算，并将其运算结果入对象栈，继续处理当前字符。3.2栈的应用3.表达式计算3.2栈的应用3.表达式计算基本思想可以先转化为后缀表达式，再进行计算从左到右依次读取表达式如果是操作数直接输出到后缀表达式是左括号压栈是右括号，弹出栈顶运算符，若不是左括号，将弹出的栈顶运算符输出后缀字符中，重复此步，直到取到左括号，并将左右括号丢弃其它运算符（+-*/等）与栈顶运算符相比，如果高于栈顶运算符，则压栈；否则弹出栈顶元素，输出至后缀表达式读完表达式后，如果最后栈不空，将所有栈元素弹出至后缀表达式3.2栈的应用3.表达式计算3.2栈的应用3.表达式计算基本思想计算后缀表达式读后缀表达式，是操作数就压栈是运算符，则弹出栈顶的两个操作数计算，将结果再压入栈后缀表达式读，栈内即是表达式的值3.2栈的应用3.表达式计算3.3栈与递归的实现如图3。73.3栈与递归的实现如图3。7习题1.栈在（）中应用。

A.递归调用B.子程序调用

C.表达式求值D.A，Ｂ，Ｃ2.表达式a*(b+c)-d的后缀表达式是()。

A．abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd3.表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。（要求能画出栈的变化情况）

A.3,2,4,1,1；(*^(+*-B.3,2,8；(*^-C.3,2,4,2,2；(*^(-D.3,2,8；(*^(-习题1.栈在（）中应用。习题4.递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。

A．队列B．多维数组

C．栈D.线性表习题4.递归过程或函数调用时，处理参数及返回地址，要用一种共享栈1.设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。共享栈3.4队列一、定义队列是只允许在一端删除，另一端插入的线性表，允许删除的一端叫队头（front),允许插入的一端叫队尾（rear）.特点：先进先出a0，a1，a2，…，an-1，进队出队队首队尾3.4队列一、定义a0，a1，a2，…，an-1，3.4队列三、队列的顺序实现1.语言描述#defineMAXSIZE1024/*队列的最大容量*/typedefstruct{datatypedata[MAXSIZE];/*队员的存储空间*/intrear,front;/*队头队尾指针*/}SqQueue;

定义一个指向队的变量：

SqQueuesq;3.4队列三、队列的顺序实现3.4队列三、队列的顺序实现2.操作实现置空队sq.front=sq.rear=0入队sq.data[sq.rear]=xsq.rear++;出队sq.front--;

读队头、队尾sq.data[sq.front]sq.data[sq.rear-1]3.4队列三、队列的顺序实现3.4队列三、队列的顺序实现2.操作实现队中元素个数m=sq.rear-sq.front队满m==MAXSIZE队空m==03.4队列三、队列的顺序实现3.4队列三、队列的顺序实现2.操作实现存在的问题：假溢出sq.rear=m-1时，再入队时虽然前面有空间，但是尾指针已经接近空间的上界而不能再入队。frontrearBCD3.4队列三、队列的顺序实现frontrearBCD3.4队列三、队列的顺序实现2.操作实现假溢出解决方案：队首固定，每次出队剩余元素向下移动——浪费时间。循环队列基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;入队：sq.data[rear]=x;

sq.rear=(rear+1)%M;出队：sq.front=(front+1)%M;3.4队列三、队列的顺序实现3.4队列三、队列的顺序实现2.操作实现循环队列存在的问题：队空sq.front==sq.rear队满sq.front==sq.rear3.4队列三、队列的顺序实现3.4队列三、队列的顺序实现2.操作实现循环队列解决方案：另外设一个标志存储队中元素个数num==0代表队空，num==MAXSIZE代表队满少用一个元素空间：队空：front==rear

队满：(rear+1)%M==front3.4队列三、队列的顺序实现3.4队列四、循环队列的实现1.语言描述typedefstruct{datatypedata[M];intfront;intrear;intcount;//记录队中元素点数}cirqueue;3.4队列四、循环队列的实现3.4队列四、循环队列的实现2.基本操作入队voidenqueue（cirqueue*q,datatypex）{if(q->count==M)//判队满if((q.rear+1)%M==q.front){printf(“overflow“);exit(0);}q->data[q->rear]=x;q->rear=(q->rear+1)%M;//插入元素xq->count++;//修改表长}3.4队列四、循环队列的实现3.4队列四、循环队列的实现2.基本操作出队datatypedequeue(cirqueue*q){if(q->count==0)//判队空if((q.rear==q.front)){printf(“queuenull“);exit(0);}q->front=(q->front+1)%m;//删除队头元素

q->count--;//修改表长

return(q->data[q->font]);}3.4队列四、循环队列的实现3.4队列四、循环队列的实现2.基本操作读队头元素datatypegetqueue(cirqueueq){return(q.data[q.front]);}3.4队列四、循环队列的实现3.4队列五、链队列1.定义限制在表头删除，表尾插入的单链表。由一个头指针和一个尾指针确定链表的头和尾frontrear

datalink3.4队列五、链队列frontreardatalin3.4队列五、链队列2.语言描述结点类型描述typedefstructnode{datatypedata;structnode*next;}queuenode;头尾指针描述typedefstruct{queuenode*front;queuenode*rear;}linkqueue;3.4队列五、链队列头尾指针描述3.4队列五、链队列3.图示(a)非空队rearfronta1an∧

…a2rearfronta1∧

rearfront

∧(b)空队(c)链队中只有一个元素结点

头尾指针封装在一起的链队3.4队列五、链队列(a)非空队rearfronta1an∧3.4队列五、链队列4.算法实现创建一个带头结点的空队：

LinkQueue*Init_LQueue(){queuenode*s;linkqueuep;s=(queuenode*)malloc(sizeof(queuenode));//申请结点

s->next=NULL;p.front=s;p.rear=s;return&p;3.4队列五、链队列3.4队列五、链队列4.算法实现入队

voidIn_LQueue(linkqueue*q,datatypex){QNode*p;p=malloc(sizeof(QNnode));//申请新结点

p->data=x;p->next=q->rear->next;q->rear->next=p;//插入尾部

q->rear=p;