队列分析公式化描述

1第6章队列(QUEUES)2本章内容6.1抽象数据类型6.2公式化描述6.3链表描述6.4应用2/6/20233队列的实现队列的应用本章重点46.1抽象数据类型定义:队列（queue）是一个线性表，其插入和删除操作分别在表的不同端进行。添加新元素的那一端被称为队尾（rear）.删除元素的那一端被成为队首（front）.队列是一个先进先出（first-in-first-out,FIFO）的线性表

e1,e2,e3,…,ei,…,en-1,en↑↑frontrear2/6/20235队列66.1队列的抽象数据类型描述抽象数据类型Queue{实例 有序线性表，一端称为front，另一端称为rear；操作

Create():创建一个空的队列；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;

时间复杂性

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

公式:location(i)=(location(1)+i–1)%Maxsize↓location(i+1)=(location(i)+1)%Maxsize循环队列abcdqueue012MaxSize-1frontrear12循环队列描述队列的数组被视为一个环

初始队列: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循环队列的进队和出队空队列:front=rear队列为满的条件:front=rear如何区分两种情况:队列为空和队列为满?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;//队列数组的大小

T*queue;//数组};2/6/202315Queue-构造函数template<classT>Queue<T>::Queue(intMaxQueueSize){//创建一个容量为MaxQueueSize的空队列MaxSize=MaxQueueSize+1;queue=newT[MaxSize];front=rear=0;}frontrear2/6/202316求队首、队尾元素template<classT>TQueue<T>::First()const{//返回队列的第一个元素//如果队列为空，则引发异常OutOfBoundsif(IsEmpty())throwOutOfBounds();returnqueue[(front+1)%MaxSize];}template<classT>TQueue<T>::Last()const{//返回队列的最后一个元素//如果队列为空，则引发异常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链表描述可以使用单向链表来实现一个队列。思考：链表中使用几个指针？需要两个变量front和rear来分别跟踪队列的两端。206.4链表描述使用链表来描述一个队列两种选择:表头为

front

，表尾为

rear

表头为

rear

，表尾为

front0……21链表描述HeadTailHeadTail图6-7链接队列思考：性能相同吗？22向链表队列中添加元素图

6-8(a)的时间复杂性?图

6-8(b)的时间复杂性?图

6-8(a)

向图

6-7(a)中插入元素

图

6-8(b)向图

6-7(b)中插入元素

23从链表队列中删除元素图

6-9(a)的时间复杂性?图

6-9(b)的时间复杂性?图

6-9(a)从图

6-7(a)中删除元素图

6-9(b)从图

6-7(b)中删除元素24队列的链表描述如何实现队列的链表描述?定义LinkedQueue为一个基类把类LinkedQueue定义为chain类（见程序3-8）的一个派生类2/6/202325链表队列的类定义template<classT>classLinkedQueue{//FIFO对象public:LinkedQueue(){front=rear=0;}//构造函数~LinkedQueue();//析构函数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;//指向第一个节点Node<T>*rear;//指向最后一个节点};2/6/202326~LinkedQueue-删除所有节点template<classT>LinkedQueue<T>::~LinkedQueue(){//队列析构函数，删除所有节点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{//返回队列的第一个元素//如果队列为空，则引发异常OutOfBoundsif(IsEmpty())throwOutOfBounds();returnfront->data;}template<classT>TLinkedQueue<T>::Last()const{//返回队列的最后一个元素//如果队列为空，则引发异常OutOfBoundsif(IsEmpty())throwOutOfBounds();returnrear->data;}2/6/202329把x添加到队列的尾部template<classT>LinkedQueue<T>&LinkedQueue<T>::Add(constT&x){//把x添加到队列的尾部//不捕获可能由new引发的NoMem异常//为新元素创建链表节点Node<T>*p=newNode<T>;p->data=x;p->link=0;if(