第四章隊列理解隊列是滿足FIFO存取規則的表熟悉定義在抽象數據類型隊列上的基本運算掌握用指針實現隊列的步驟和方法掌握用循環數組實現隊列的步驟和方法理解用隊列解決實際問題的方法3/14/20231第四章隊列隊列和棧一樣是一種特殊的線性表，是操作受限的線性表，稱其為限定性數據結構。隊列的定義及特點定義：隊列是限定只能在表的一端進行插入，在表的另一端進行刪除的線性表隊尾(rear)——允許插入的一端隊頭(front)——允許刪除的一端隊列特點：先進先出(FIFO)3/14/20232a1a2a3…….an入隊出隊frontrear隊列Q=(a1,a2,……,an)雙端隊列a1a2a3…….an端1端2入隊出隊入隊出隊3/14/202334.1

ADT隊列(Queue)ADT隊列上定義的常用的基本運算Empty();Full();First();Last();EnQueue(x);DeQueue(x);

3/14/202344.2鏈隊列結點定義typedef

struct

qnode*qlink;typedef

struct

qnode{

QItemelement;

qlinknext;

}QNode;3/14/20235frontrearx入隊^xfrontreary入隊x^yfrontrearx出隊x^yfrontrear空隊^frontreary出隊^3/14/202364.3隊列的順序存儲結構實現：用一維數組實現sq[M]front=-1rear=-1123450隊空123450frontJ1,J1,J3入隊J1J2J3rearrear123450J4,J5,J6入隊J4J5J6front設兩個指針front,rear,約定：rear指示隊尾元素；front指示隊頭元素前一位置初值front=rear=-1空隊列條件：front==rear入隊列：sq[++rear]=x;出隊列：x=sq[++front];rearrearfrontrear123450J1,J2,J3出隊J1J2J3frontfrontfront3/14/20237存在問題設數組維數為M，則：當front=-1,rear=M-1時，再有元素入隊發生溢出——真溢出當front-1,rear=M-1時，再有元素入隊發生溢出——假溢出解決方案隊首固定，每次出隊剩余元素向下移動——浪費時間循環隊列基本思想：把隊列設想成環形，讓sq[0]接在sq[M-1]之后，若rear+1==M,則令rear=0;0M-11frontrear…...…...實現：利用“?！边\算入隊：rear=(rear+1)%M;sq[rear]=x;出隊：front=(front+1)%M;x=sq[front];隊滿、隊空判定條件3/14/20238012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始狀態J4,J5,J6出隊J7,J8,J9入隊隊空：front==rear隊滿：front==rear解決方案：1.另外設一個標志以區別隊空、隊滿2.少用一個元素空間：隊空：front==rear

隊滿：(rear+1)%M==front3/14/202394.4ADT隊列的應用—電路布線問題3/14/202310電路布線問題startpinendpinLabelallreachablesquares1unitfromstart.3/14/202311電路布線問題startpinendpinLabelallreachableunlabeledsquares2unitsfromstart.113/14/202312電路布線問題startpinendpinLabelallreachableunlabeledsquares3unitsfromstart.11222223/14/202313電路布線問題startpinendpinLabelallreachableunlabeledsquares4unitsfromstart.112222233333/14/202314電路布線問題startpinendpinLabelallreachableunlabeledsquares5unitsfromstart.11222223333444443/14/202315電路布線問題startpinendpinLabelallreachableunlabeledsquares6unitsfromstart.11222223333444445555553/14/202316電路布線問題startpinendpinEndpinreached.Traceback.1122222333344444555555666666663/14/202317電