队列分析公式化描述

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

2、20215队列66.1队列的抽象数据类型描述抽象数据类型Queue 实例有序线性表，一端称为front，另一端称为rear；操作 Create (): 创建一个空的队列；IsEmpty (): 如果队列为空，则返回true，否则返回false；IsFull ( ) :如果队列满，则返回true；否则返回false；First (): 返回队列的第一个元素；Last ( ) :返回队列的最后一个元素；Add (x): 向队列中添加元素x； / enqueueDelete (x): 删除队首元素，并送入x ; / dequeue7 6.2 公式化描述 公式: location(i) = i 1第一

3、个元素: queue0, 第二个元素 : queue1 front总是为0 , rear始终是最后一个元素的位置 e1 e2 e3 en queue 0 1 2 MaxSize-1front rear 8公式化描述队列的长度: rear + 1空队列 : rear=-1Add(x): rear=rear+1;queuerear=x; O(1)Delete(x): x=queue0;queue0.rear-1 queue1.rear;rear=rear-1; Q Q(n)(n)e1 e2 e3 en queue 0 1 2 MaxSize-1front rear 9公式化描述 公式: locat

4、ion(i) = location(1) + i 1front = location(1), rear = location(last element)空队列 : rear frontDelete(x): front=front+1; Q Q(1) Add(x): when rear 0 ？ 假溢出假溢出10公式化描述平移队列queue0.rear-front+1 queuefront.rear; rear=rear+1;queuerear=x; 时间复杂性 : Q Q(n)when rear = Maxsize-1 and front 0 Add(x)？队列的移位之前 队列的移位之后11公式

5、化描述 公式 :location(i) = (location(1) + i 1) % Maxsize location(i+1) = (location(i) + 1) % Maxsize循环队列循环队列a b c d queue 0 1 2 MaxSize-1front rear 12循环队列 描述队列的数组被视为一个环 初始队列: front=rear=0Add(x): rear=rear+1;queuerear=x; Q Q(1) Delete(x): front=front +1;x=queuefront; Q Q(1) front: 指向队列首元素的下一个位置（逆时针方向）。rea

6、r: 最后一个元素的位置 rear frontfrontrear10/12/202113循环队列的进队和出队空队列: front=rear队列为满的条件: front=rear如何区分两种情况: 队列为空和队列为满? Maximum=MaxSize-1队列为满的条件: front=(rear+1) % MaxSize10/12/202114公式化类Queuetemplateclass Queue / FIFO 对象public:Queue(int MaxQueueSize = 10);Queue() delete queue;bool IsEmpty() const return front

7、= rear;bool IsFull() const return (rear + 1) % MaxSize = front) ? 1 : 0);T First() const; /返回队首元素T Last() const; / 返回队尾元素Queue& Add(const T& x);Queue& Delete(T& x);private:int front; /与第一个元素在反时针方向上相差一个位置int rear; / 指向最后一个元素int MaxSize; / 队列数组的大小T *queue; / 数组 ;10/12/202115Queue-构造函数t

8、emplateQueue:Queue(int MaxQueueSize)/ 创建一个容量为MaxQueueSize的空队列MaxSize = MaxQueueSize + 1;queue = new TMaxSize;front = rear = 0;frontrear10/12/202116求队首、队尾元素templateT Queue:First() const/ 返回队列的第一个元素/ 如果队列为空，则引发异常OutOfBoundsif (IsEmpty() throw OutOfBounds();return queue(front + 1) % MaxSize;templateT Q

9、ueue:Last() const/ 返回队列的最后一个元素/ 如果队列为空，则引发异常OutOfBoundsif (IsEmpty() throw OutOfBounds();return queuerear;17操作 AddtemplateQueue& Queue:Add(const T& x)/ 把x 添加到队列的尾部if (IsFull() throw NoMem();rear = (rear + 1) % MaxSize;queuerear = x;return *this;18操作 DeletetemplateQueue& Queue:Delete(T&am

10、p; x)/ 删除第一个元素，并将其送入xif (IsEmpty() throw OutOfBounds();front = (front + 1) % MaxSize;x = queuefront;return *this;10/12/2021196.4 链表描述n可以使用单向链表来实现一个队列。n思考：链表中使用几个指针？n需要两个变量front和rear来分别跟踪队列的两端。206.4 链表描述使用链表来描述一个队列 l两种选择: 表头为 front ，表尾为 rear 表头为 rear ，表尾为 front 021链表描述HeadTailHeadTail图6-7 链接队列n 思考：性能

11、相同吗？22向链表队列中添加元素 l图 6-8 (a)的时间复杂性?l图 6-8 (b) 的时间复杂性?l图 6-8 (a) 向图 6-7 (a)中插入元素 l图 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）的一个派生类10/12/202125链表队列的类定义t

12、emplateclass LinkedQueue / FIFO对象p u b l i c :LinkedQueue() front = rear = 0; / 构造函数LinkedQueue(); / 析构函数bool IsEmpty() constreturn (front) ? false : true);bool IsFull() const;T First() const; / 返回第一个元素T Last() const; / 返回最后一个元素LinkedQueue& Add(const T& x);LinkedQueue& Delete(T& x);p

13、rivate:Node *front; / 指向第一个节点Node *rear; /指向最后一个节点 ;10/12/202126LinkedQueue-删除所有节点templateLinkedQueue: LinkedQueue( )/ 队列析构函数，删除所有节点Node *next;while (front) next = front-link;delete front;front = next; 10/12/202127判断队列是否已满templatebool LinkedQueue:IsFull() const/ 判断队列是否已满Node *p;try p = new Node;dele

14、te p;return false;catch (NoMem) return true;10/12/202128返回队列的队首队尾元素templateT LinkedQueue:First() const/ 返回队列的第一个元素/ 如果队列为空，则引发异常O u t O f B o u n d sif (IsEmpty() throw OutOfBounds();return front-data;templateT LinkedQueue:Last() const/ 返回队列的最后一个元素/ 如果队列为空，则引发异常O u t O f B o u n d sif (IsEmpty() thr

15、ow OutOfBounds();return rear-data;10/12/202129把x 添加到队列的尾部templateLinkedQueue& LinkedQueue:Add(const T& x)/ 把x 添加到队列的尾部/ 不捕获可能由n e w引发的NoMem 异常/ 为新元素创建链表节点Node *p = new Node;p-data = x;p-link = 0;if (front) rear-link = p; /队列不为空else front = p; / 队列为空rear = p;return *this;10/12/202130删除第一个元素templateLinkedQueue& LinkedQueue:Delete(T& x)/ 删除第一个元素，并将其放入x/ 如果队列为空，则引发异常O u t O f B o u n d sif (IsEmpty() throw OutOfBounds();/ /保存第一个节点中的元素x = front-data;/ 删除第一个节点Node *p = front;front = front-link;