3.4.1 队列的定义排队的基本规则是新来者排在队伍末尾排在队伍前面的人先得到服务期问不允许插队。“队列”也是一个有序线性表但队列的插入和删除操作是分别在线性表的两个不同端点进行的。队列的抽象数据类型定义为:类型名称:队列。数据对象集:一个有0个或多个元素的有穷线性表。操作集:对于一个长度为正整数MaxSize的队列QeQueue,记队列中的任一元素X∈Ele-mentType队列的基本操作主要有:(1) Queue CreateQueue(int MaxSize):生成空队列,其最大长度为 MaxSize;(2) bool IsFull(Queue Q):判断队列Q是否已满。若是返回true;否则返回false;(3) bool AddQ(Queue Q,ElementType X):将元素X压人队列Q。若队列已满,返回false;否则将数据元素X插人到队列Q并返回true;(4) bool IsEmpty(Queue Q):判断队列Q是否为空,若是回true;否则返回false;(5)ElementType DeleteQ(Queue Q):删除并返回队列头元素。若队列为空,返回错误信息;否则将队列头数据元素从队列中删除并返回。3.4.2队列的实现1.队列的顺序存储实现队列最简单的表示方法是用数组。数组存储队列的一般方法将队列头放数组下标小的位置而将队列尾放在数组下标大的位置并用两个变量Front 和Rear分别指示队列的头和尾。一般Front和Rear先初始化为-1。当有元素人队,Rear向右移动一格(加1),放入队尾元素;当有元素出队先将Front向右移动一格(加1),再删除队头元素。随着入队出队的进行会使整个队列整体向后移动队尾指针已经移到了最后再有元素入队就会出现溢出而事实上此时队中并未真的“满员”这种现象称为“假溢出”为了解决队尾溢出而实际上数组仍然有空余空间的问题一般在队列的顺序存储结构中采用循环队列的方式。当插人和删除操作的作用单元达到数组的末端后用公式“Rear(或Front)%数组长度”取余运算就可以实现折返到起始单位。区分队列满空(Front 和Rear提供的信息量不够):方法之一是另外增设一个变量比如:记录当前队列元素个数的变量Size或者用一个变量Flag记录最后一次操作是入队还是出队。根据变量Size我们就可以直接判断队列是满还是空;根据变量Flag就可以知道当Front等于Rear时是满还是空。方法之二是少用一个元素空间把图3.14(c)(课本85页)所示的情况就视为队列满。此时的状态是队尾指针加1就会从后面赶上队头指针因此队满的条件是:(Rear1)%数组长度等于Front。队空的条件仍然是:Rear等于Front。2.队列的链式存储实现注意队列的头(Front)必须指向链表的头结点队列的尾(Rear)指向链表的尾结点用C语言描述链式队列结构如下:typedef struet Node * PtrToNode;struet Node{/*队列中的结点*/ElementType Data;PtrToNode Next;}typedef PtrToNode Position;typedef struct QNode * PtrToQNode;struct QNode {Position Front,Rear;/*队列的头、尾指针*/int MaxSize; /*队列最大容量*/}typedef PtrToQNode Queue;采用链式存储的入队和出队操作实际就是在一个链表的尾部插入结点或者在头部删除结点。(实例见课本87、88页) 3.4队列
3.4.1 队列的定义排队的基本规则是新来者排在队伍末尾排在队伍前面的人先得到服务期问不允许插队。“队列”也是一个有序线性表但队列的插入和删除操作是分别在线性表的两个不同端点进行的。队列的抽象数据类型定义为:类型名称:队列。数据对象集:一个有0个或多个元素的有穷线性表。操作集:对于一个长度为正整数MaxSize的队列QeQueue,记队列中的任一元素X∈Ele-mentType队列的基本操作主要有:(1) Queue CreateQueue(int MaxSize):生成空队列,其最大长度为 MaxSize;(2) bool IsFull(Queue Q):判断队列Q是否已满。若是返回true;否则返回false;(3) bool AddQ(Queue Q,ElementType X):将元素X压人队列Q。若队列已满,返回false;否则将数据元素X插人到队列Q并返回true;(4) bool IsEmpty(Queue Q):判断队列Q是否为空,若是回true;否则返回false;(5)ElementType DeleteQ(Queue Q):删除并返回队列头元素。若队列为空,返回错误信息;否则将队列头数据元素从队列中删除并返回。3.4.2队列的实现1.队列的顺序存储实现队列最简单的表示方法是用数组。数组存储队列的一般方法将队列头放数组下标小的位置而将队列尾放在数组下标大的位置并用两个变量Front 和Rear分别指示队列的头和尾。一般Front和Rear先初始化为-1。当有元素人队,Rear向右移动一格(加1),放入队尾元素;当有元素出队先将Front向右移动一格(加1),再删除队头元素。随着入队出队的进行会使整个队列整体向后移动队尾指针已经移到了最后再有元素入队就会出现溢出而事实上此时队中并未真的“满员”这种现象称为“假溢出”为了解决队尾溢出而实际上数组仍然有空余空间的问题一般在队列的顺序存储结构中采用循环队列的方式。当插人和删除操作的作用单元达到数组的末端后用公式“Rear(或Front)%数组长度”取余运算就可以实现折返到起始单位。区分队列满空(Front 和Rear提供的信息量不够):方法之一是另外增设一个变量比如:记录当前队列元素个数的变量Size或者用一个变量Flag记录最后一次操作是入队还是出队。根据变量Size我们就可以直接判断队列是满还是空;根据变量Flag就可以知道当Front等于Rear时是满还是空。方法之二是少用一个元素空间把图3.14(c)(课本85页)所示的情况就视为队列满。此时的状态是队尾指针加1就会从后面赶上队头指针因此队满的条件是:(Rear1)%数组长度等于Front。队空的条件仍然是:Rear等于Front。2.队列的链式存储实现注意队列的头(Front)必须指向链表的头结点队列的尾(Rear)指向链表的尾结点用C语言描述链式队列结构如下:typedef struet Node * PtrToNode;struet Node{/*队列中的结点*/ElementType Data;PtrToNode Next;}typedef PtrToNode Position;typedef struct QNode * PtrToQNode;struct QNode {Position Front,Rear;/*队列的头、尾指针*/int MaxSize; /*队列最大容量*/}typedef PtrToQNode Queue;采用链式存储的入队和出队操作实际就是在一个链表的尾部插入结点或者在头部删除结点。(实例见课本87、88页)