第三章栈和队列一、栈的概念栈（stack）是插入和删除操作限定在表尾进行的线性表。栈的逻辑表示为：S=（a1,a2,…,an）表尾元素an称为栈顶(top)表头元素a1称为栈底(bottom)不含元素的空表称为空栈栈的运算特性是后进先出(LastInFirstOut——LIFO)或先进后出(FirstInLastOut——FILO)3.1栈的表示和实现3.1栈的表示和实现3.1栈的表示和实现3.1栈的表示和实现3.1栈的表示和实现3.1栈的表示和实现3.1栈的表示和实现3.1栈的表示和实现3.1栈的表示和实现3.1栈的表示和实现3.2栈的应用--表达式求值3.2栈的应用--表达式求值3.2栈的应用--表达式求值3.2栈的应用--表达式求值3.2栈的应用--表达式求值3.3递归过程例：计算两个非负整数a*b的算法1.递归方式：a*b=b+(a-1)*bFUNCmul1(a，b：integer)：integer；IFa=0THENRETURN(0)ELSERETURN(b+mul1(a-1，b))ENDF；{mul1}3.3递归过程3.3递归过程算法思想：当n=1：只需将该圆盘从X移到Z即可；当n>1：若能将压在n号盘上的n-1个圆盘按规则移至Y，然后把n号盘从X移到Z上，最后再将Y上的n-1个圆盘按规则移至Z上。原问题为：hanoi(n，X，Y，Z)化简为：hanoi(n-1，X，Z，Y)move(X，n，Z)把X上的n号盘移到Z上hanoi(n-1，Y，X，Z)3.3递归过程3.3递归过程一、队列的概念队列（queue）是限定在一端插入,另一端删除的线性表。允许插入的一端叫队尾(rear),允许删除的一端叫队头(front),不含元素的空表称为空队列队列的运算特性是先进先出(FirstInFirstOut--FIFO)二、队列的基本运算INIQUEUE（Q）初始化操作，设置一个空队列EMPTY(Q)判定队列是否为空函数（true/false）ENQUEUE(Q，x)入队列操作，队尾插入元素xDLQUEUE(Q)出队函数（删除）GETHEAD(Q)取队头元素函数CLEAR(Q)队列置空操作CURRENT-SIZE(Q)求队列Q当前元素个数三、队列的链式存储结构——链队列1．存储结构链队列需要队头和队尾两个指针来确定。TYPEqueueptr=queuenodequeuenode=RECORDdata：elemtp；next：queueptrEND；linkedquetp=RECORDfront，rear：queueptrEND；给链队列添加个头结点，并令头指针指向头结点。链队列为空时，头尾指针均指向头结点即q．front=q．rear（且q.front.next=NIL）2．出队算法FUNCdl_linkedque(VARq:linkedquetp):elemtp；IFq.front=q.rearTHENRETURN(NULL)ELSE[s:=q.front↑.next；q.front↑.next:=s↑.next；IFs↑.next=NILTHENq.rear:=q.front；x:=s↑.data；dispose(s)；RETURN(x)]ENDF；{dl_linkedque}删除时的三种情形：a.删除前已空；b.删除前只有一个结点，删除后为空队列；c.其他情形（删除前结点数>1）3．入队算法PROCen_linkedque(VARq：linkedquetp；x：elemtp)；new(p)；p↑.data：=x；p↑.next：=NIL；q.rear↑.next：=p；q.rear：=pENDP；四、队列的顺序存储结构1.一般顺序存储结构用一个向量来存放队列元素，并用两个指针来指示队头和队尾。并约定：头指针sq.front总是指向队头元素的前一个位置；尾指针sq.rear指向队尾元素。CONST=…；TYPEsequeuetp=RECORDelem:ARRAY[1..maxsize]0Felemtp；front,rear:0..maxsizeEND；初始时：sq.front=sq.rear=0空队列条件：sq.front=sq.rear出队时：IFsq.rear=sq.frontTHENRETURN（NULL）ELSE[sq.front:=sq.front+1；RETURN（sq.elem[sq.front]）]入队时：IFsq.rear=maxsizeTHENERROR(`队满`)ELSE[sq.rear:=sq.rear+1；sq.elem[sq.r