队列基本概念、循环队列.docx

《队列基本概念、循环队列.docx》由会员分享，可在线阅读，更多相关《队列基本概念、循环队列.docx（2页珍藏版）》请在第一文库网上搜索。

1、队列基本概念、循环队列线性结构的两种常见应用：队列定义：一种可以实现“先进先出”的存储结构，即“一端入，一端出“，队首(front)出队，队尾(rear)入队(注：若front指向队首，则rear指向队尾最后一个有效元素的下一个元素；若rear指向队尾，则front指向队首第一个有效元素的下一个元素)分类：链式队列一用链表实现静态队列一用数组实现，静态队列通常都必须是循环队列循环队列：1 .静态队列为什么必须是循环队列？为了减少内存浪费。如果用传统意义的数组实现队列，无论入队还是出队，rear和front指针只能+不能-；比F元素下标小的的数组元素下标就浪费了。2 .循环队列需要几个参数来确定

2、？两个参数：front,rear两个参数在不同场合有不同的含义3 .循环队列各个参数的含义1)队列初始化front和rear的值都是零,初始化时队列就是空的。2)队列非空front代表队列的第一个元素rear代表了最后一个有效元素的下一个元素3)队列空front和rear的值相等，但是不一定是零4 .循环队列入队伪算法需要判断r是否指向数组最后一个元素。两步完成：1)将值存入r所指向的位置2)将r后移，正确写法是rear=(rear+1)%数组长度错误写法：rear=rear+1;若rear已经在规定范围的队尾，就不能直接+1,否则越界5 .循环队列出队伪算法front=(front+1)%数组长度，比如出队数组元素下标是0,数组长度是5,则front作为队首指向（0+1）%5=1,那么此时队首下标是16 .如何判断循环队列是否为空？如果front与rear的值相等，则队列一定为空7 .如何判断循环队列是否已满？方法一：多增加一个表标识的参数方法二（常用）：少用一个队列中的元素（才一个，不影响的），比如一共有N个元素的位置,规定N-I个为满，如果rear和front紧挨着（r的下一个位置是f）,则队列已满。用C语言描述：if（r+1）%数组长度尸二D队列已满e1se队列不满