第三章 队列 下.ppt

顺序队列 采用顺序存储结构的队列称为顺序队列。 在顺序队列中，需要设置两个指针： front 指示队头元素的位置； rear 指示队尾元素的位置。 初始化建空队列时，令front＝rear＝0。 每当插入新的队尾元素时，rear增1，每当删除队头元素时，front增1。 因此，在非空队列中，front始终指向队头元素，rear始终指向队尾元素的下一个位置 循环队列 为了解决队列出现“假满”的情况，可以使用循环队列来表示顺序队列。 下面我们用第二种方法实现循环队列上的六种基本操作: 少用一个存储单元，队满条件是： （rear＋1）% MaxSize = =front 其中，MaxSize 是队列的最大长度。 队空条件：front==rear 循环队列的类型定义 # define MAXQSIZE 100 // 最大队列长度 Typedef struct { QElemType * base; int front; int rear; }SqQueue; base: 初始化时，队列的存储空间地址 front: 头指针，当队列不空时，指向队头元素 rear：尾指针，当队列不空时，指向队尾元素 注意：front、rear都是整数，用指针形式表示是为了直观、方便理解 循环队列的基本操作实现 构造一个空队列 求队列长度 入队列 出队列 （1）构造一个空队列： Status InitQueue ( SqQueue Q) { Q.base = ( QElemType * ) realloc ( MAXSIZE * sizeof ( QElemType )) If ( !Q.base ) exit (OVERFLOW ); Q.front = Q.rear = 0; // 头指针、尾指针的初值 return OK; } （2）求队列Q的长度：即Q中元素的个数 int QueueLength ( SqQueue Q ) { return (Q.rear - Q.front +MAXSIZE ) %MAXSIZE; } （3）入队列：插入元素e为新的队尾元素 Status EnQueue (SqQueue Q, QElemType e) { if ((Q.rear +1 )%MAXSIZE = = Q.front ) return ERROR; //队列满 Q.base[Q.rear] = e; // 把元素e插在队尾 Q.rear = ( Q.rear + 1) %MAXSIZE; // 修改尾指针，指向e的下一个位置 return OK； } 注意：在队尾插入元素时，一定要判断队列是否已满，若满，则不能插入。 （4）出队列：若队列不空，则删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR Status DeQueue (SqQueue Q, QElemType e) { if (Q.front = = Q.rear ) return ERROR; // 队列空 e = Q.base[Q.front]; //队头元素在[Q.front]分量中 Q.front = ( Q.front + 1 ) % MAXSIZE; //修改头指针 return OK; } 注意：在删除队头元素时，一定要判断队列是否为空，若为空，则不能进行删除操作。 * 队列也是一种操作受限的线性表，它只允许在表的一端进行插入，而在另一端删除元素。 允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。 例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。 当队列中没有元素时称为空队列。 队 列 在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an ，也就是说队列的修改是依先进先出的原则进行的。 下图是队列的示意图： a1　a2　…　an 出队 入队 队头 队