1第6章隊列(QUEUES)2本章內(nèi)容6.1抽象數(shù)據(jù)類型6.2公式化描述6.3鏈表描述6.4應(yīng)用2/6/20233隊列的實現(xiàn)隊列的應(yīng)用本章重點46.1抽象數(shù)據(jù)類型定義:隊列（queue）是一個線性表，其插入和刪除操作分別在表的不同端進行。添加新元素的那一端被稱為隊尾（rear）.刪除元素的那一端被成為隊首（front）.隊列是一個先進先出（first-in-first-out,FIFO）的線性表

e1,e2,e3,…,ei,…,en-1,en↑↑frontrear2/6/20235隊列66.1隊列的抽象數(shù)據(jù)類型描述抽象數(shù)據(jù)類型Queue{實例 有序線性表，一端稱為front，另一端稱為rear；操作

Create():創(chuàng)建一個空的隊列；IsEmpty():如果隊列為空，則返回true，否則返回false；IsFull():如果隊列滿，則返回true；否則返回false；First():返回隊列的第一個元素；Last():返回隊列的最后一個元素；Add(x):向隊列中添加元素x；//enqueueDelete(x):刪除隊首元素，并送入x;//dequeue}7

6.2公式化描述

公式:

location(i)=i–1第一個元素:queue[0],第二個元素:queue[1]……front總是為0,rear始終是最后一個元素的位置e1e2e3……enqueue012MaxSize-1frontrear8公式化描述隊列的長度:rear+1空隊列

:rear=-1Add(x):rear=rear+1;queue[rear]=x;

O(1)Delete(x):x=queue[0];queue[0..rear-1]←queue[1..rear];rear=rear-1;Q(n)e1e2e3……enqueue012MaxSize-1frontrear9公式化描述

公式:

location(i)=location(1)+i–1front=location(1),rear=location(lastelement)空隊列:rear<frontDelete(x):front=front+1;

Q(1)Add(x):whenrear<Maxsize–1:rear=rear+1;queue[rear]=x;

Q(1)whenrear=Maxsize-1andfront>0

？假溢出10公式化描述平移隊列queue[0..rear-front+1]←queue[front..rear];rear=rear+1;queue[rear]=x;

時間復(fù)雜性

:Q(n)whenrear=Maxsize-1andfront>0Add(x)？隊列的移位之前隊列的移位之后11公式化描述

公式:location(i)=(location(1)+i–1)%Maxsize↓location(i+1)=(location(i)+1)%Maxsize循環(huán)隊列abcdqueue012MaxSize-1frontrear12循環(huán)隊列描述隊列的數(shù)組被視為一個環(huán)

初始隊列:front=rear=0Add(x):rear=rear+1;queue[rear]=x;Q(1)

Delete(x):front=front+1;x=queue[front];

Q(1)

front:

指向隊列首元素的下一個位置（逆時針方向）。rear:

最后一個元素的位置

rearfrontfrontrear2/6/202313循環(huán)隊列的進隊和出隊空隊列:front=rear隊列為滿的條件:front=rear如何區(qū)分兩種情況:隊列為空和隊列為滿?Maximum=MaxSize-1隊列為滿的條件:front=(rear+1)%MaxSize2/6/202314公式化類Queuetemplate<classT>classQueue{//FIFO對象public: Queue(intMaxQueueSize=10); ~Queue(){delete[]queue;} boolIsEmpty()const{returnfront==rear;} boolIsFull()const{return( ((rear+1)%MaxSize==front)?1:0);} TFirst()const;//返回隊首元素

TLast()const;//返回隊尾元素

Queue<T>&Add(constT&x); Queue<T>&Delete(T&x);private: intfront;//與第一個元素在反時針方向上相差一個位置

intrear;//指向最后一個元素

intMaxSize;//隊列數(shù)組的大小

T*queue;//數(shù)組};2/6/202315Queue-構(gòu)造函數(shù)template<classT>Queue<T>::Queue(intMaxQueueSize){//創(chuàng)建一個容量為MaxQueueSize的空隊列MaxSize=MaxQueueSize+1;queue=newT[MaxSize];front=rear=0;}frontrear2/6/202316求隊首、隊尾元素template<classT>TQueue<T>::First()const{//返回隊列的第一個元素//如果隊列為空，則引發(fā)異常OutOfBoundsif(IsEmpty())throwOutOfBounds();returnqueue[(front+1)%MaxSize];}template<classT>TQueue<T>::Last()const{//返回隊列的最后一個元素//如果隊列為空，則引發(fā)異常OutOfBoundsif(IsEmpty())throwOutOfBounds();returnqueue[rear];}17操作‘Add’template<classT>Queue<T>&Queue<T>::Add(constT&x){//把x添加到隊列的尾部if(IsFull())throwNoMem();rear=(rear+1)%MaxSize;queue[rear]=x;return*this;}18操作‘Delete’template<classT>Queue<T>&Queue<T>::Delete(T&x){//刪除第一個元素，并將其送入xif(IsEmpty())throwOutOfBounds();front=(front+1)%MaxSize;x=queue[front];return*this;}2/6/2023196.4鏈表描述可以使用單向鏈表來實現(xiàn)一個隊列。思考：鏈表中使用幾個指針？需要兩個變量front和rear來分別跟蹤隊列的兩端。206.4鏈表描述使用鏈表來描述一個隊列兩種選擇:表頭為

front

，表尾為

rear

表頭為

rear

，表尾為

front0……21鏈表描述HeadTailHeadTail圖6-7鏈接隊列思考：性能相同嗎？22向鏈表隊列中添加元素圖

6-8(a)的時間復(fù)雜性?圖

6-8(b)的時間復(fù)雜性?圖

6-8(a)

向圖

6-7(a)中插入元素

圖

6-8(b)向圖

6-7(b)中插入元素

23從鏈表隊列中刪除元素圖

6-9(a)的時間復(fù)雜性?圖

6-9(b)的時間復(fù)雜性?圖

6-9(a)從圖

6-7(a)中刪除元素圖

6-9(b)從圖

6-7(b)中刪除元素24隊列的鏈表描述如何實現(xiàn)隊列的鏈表描述?定義LinkedQueue為一個基類把類LinkedQueue定義為chain類（見程序3-8）的一個派生類2/6/202325鏈表隊列的類定義template<classT>classLinkedQueue{//FIFO對象public:LinkedQueue(){front=rear=0;}//構(gòu)造函數(shù)~LinkedQueue();//析構(gòu)函數(shù)boolIsEmpty()const{return((front)?false:true);}boolIsFull()const;TFirst()const;//返回第一個元素TLast()const;//返回最后一個元素LinkedQueue<T>&Add(constT&x);LinkedQueue<T>&Delete(T&x);private:Node<T>*front;//指向第一個節(jié)點Node<T>*rear;//指向最后一個節(jié)點};2/6/202326~LinkedQueue-刪除所有節(jié)點template<classT>LinkedQueue<T>::~LinkedQueue(){//隊列析構(gòu)函數(shù)，刪除所有節(jié)點Node<T>*next;while(front){next=front->link;deletefront;front=next;}}2/6/202327判斷隊列是否已滿template<classT>boolLinkedQueue<T>::IsFull()const{//判斷隊列是否已滿Node<T>*p;try{p=newNode<T>;deletep;returnfalse;}catch(NoMem){returntrue;}}2/6/202328返回隊列的隊首隊尾元素template<classT>TLinkedQueue<T>::First()const{//返回隊列的第一個元素//如果隊列為空，則引發(fā)異常OutOfBoundsif(IsEmpty())throwOutOfBounds();returnfront->data;}template<classT>TLinkedQueue<T>::Last()const{//返回隊列的最后一個元素//如果隊列為空，則引發(fā)異常OutOfBoundsif(IsEmpty())throwOutOfBounds();returnrear->data;}2/6/202329把x添加到隊列的尾部template<classT>LinkedQueue<T>&LinkedQueue<T>::Add(constT&x){//把x添加到隊列的尾部//不捕獲可能由new引發(fā)的NoMem異常//為新元素創(chuàng)建鏈表節(jié)點Node<T>*p=newNode<T>;p->data=x;p->link=0;if(