隊(duì)列分析公式化描述

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

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

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

6.2公式化描述

公式:

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

: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)空隊(duì)列: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公式化描述平移隊(duì)列queue[0..rear-front+1]←queue[front..rear];rear=rear+1;queue[rear]=x;

時(shí)間復(fù)雜性

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

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

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

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

Q(1)

front:

指向隊(duì)列首元素的下一個(gè)位置（逆時(shí)針方向）。rear:

最后一個(gè)元素的位置

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

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

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

intrear;//指向最后一個(gè)元素

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

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

front

，表尾為

rear

表頭為

rear

，表尾為

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

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

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

6-8(a)

向圖

6-7(a)中插入元素

圖

6-8(b)向圖

6-7(b)中插入元素

23從鏈表隊(duì)列中刪除元素圖

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

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

6-9(a)從圖

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

6-9(b)從圖

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