文档介绍：1第五章队列 何谓队列队列数据结构规定:在有序列表中数据的输出、输入是分别由不同端进行处理,输出端称为前端( front) , 输入端称为后端( rear) , 这样会使得先存入的数据会先被取出,也就是具有先进先出 FIFO 的特性。 2 队列的应用也很多,下面列出几个较常见的: 。 2. 优先队列,此种队列在取出元素时是根据所存元素的某项特性值或优先权而取出具最小或最大数值的元素。 3. 操作系统中的工作调度,若工作的优先权相同,则采用先到先做的原则。 “ spooling ” (假脱机,信息暂存, 当信息需进一步处理时,对其进行暂时存贮), 先将输出数据写在磁盘上,再由打印机把先存入者先处理的顺序将数据输出。队列和堆栈一样也可使用两种结构:数组结构和链表结构。 3抽象数据类型 Queue 元素:无限制,由应用决定结构:保持元素先进先出的特性。操作: (1)void I nit(Queue &Q)// 初始化生成一个空栈(2)void Addqueue(Element e,Queue &Q)/ 入队操作(3)void Delqueue(Elment & e,Queue &Q)// 出队操作(4)Element Top(Queue Q)// 读队首元素值(5)bool Empty(Queue Q)// 判队列空操作(6)bool Full(Queue Q)// 判队列满操作 4 用数组仿真队列队列本身是有序列表,若使用数组的结构来存储队列的结构,则队列结构数组的声明如下: struct queue { int queue[MaxSize ]; int front ; int rear ; } 其中 MaxSize 是该队列的最大容量。因为队列的输出、输入分别从前后端来处理,因此需要两个变量 front 和 rear 分别记录队列前后端的索引值, front 会随着数据输出而变动,而 rear 则是随着数据输入而改变。 5初始化队列 void init(queue &q) { =-1; =-1; } 6判断队列空 empty 函数 bool empty(queue q) { return( == ); } 7判断队列满 full 函数 bool full(queue q) { return ( ==maxsize-1); } 8 当我们将数据存入队列时称为“ addqueue ”, addqueue 的处理主要有两个步骤: (1) 将队尾指针往前移: rear+1 ; (2) 若尾指针 rear 小于等于队列的最大索引值 MaxSize- 1, 则将数据存入 rear 所指的数组元素中,否则无法存入数据。 9入队 addqueue 函数 void addqueue(queue & q,char x) { ++; [ ]=x; } 10 从队列中取出数据项称为“ delqueue ”, delqueue 的操作可分为 4个步骤: (1) 检查队列中是否有数据存在。 (2) 若头指针 front 等于尾指针 rear , 则表示队列中无数据。(3) 若头指针 front 不等于尾指针 rear , 则将队列头指针往前移 front+1 。(4) 取出队头指针所指的数组元素内容。