学信息学奥赛循环队列

来源：海口童程童美少儿编程培训学院时间：2023/6/2 14:37:21

　　循环队列：

　　用一个数组，加分别指向队首，队尾的指针，实现循环队列。

　　初始时：队首和队尾指向相同

　　元素入队时，入队一个元素尾指针+1

　　元素入队时，入队一个元素尾指针+1

　　当尾指针指向数组较后一个元素，头指针未指向个元素时，实际上前面还有空的空间可以存储元素，称为“假溢出”

　　此时，可以将头指针指向前面空的元素，继续存储，这样就实现了数组空间的循环利用。

　　如上图，当1位置也存储了元素后，队列不能再存储元素，头指针和尾指针指向相同的位置，这样就和队列空的判断条件一样，无法判断是队列满还是队列空，

　　一般情况下，采取少存一个元素，来区别队列满还是空。另外一种方式，在程序中置一个标志位，用标志位来区别队列满和空的状态。

　　由上面的分析得知，循环队列元素出队和入队时，头指针和尾指针都加1。

　　循环队列的基本操作：

　　1、判断队列空 head == tail

　　2、入队位置计算 tail=(tail+1)% N N表示数组元素的长度

　　3、出队位置计算 head=(head+1)% N

　　4、判断队列满 (tail+1) % N =tail

　　5、求队列长度 (tail-head+N) % N

　　出队和入队位置计算为以及求队列长度为什么都%N?当head和tail为7时，加1%N=0，就是个元素，tail-head<0也需要+N%N增加位置为正。

　　循环队列的C++代码实现：

　　#include

　　using namespace std;

　　const int N=6; //队列长度

　　int a[N]; //队列数组

　　int head; //头指针的位置

　　int tail; //尾指针的位置

　　void init(); //初始化

　　void add(int x); //队列入队

　　int out(); //队列出队

　　bool iffull(); //判断队列满

　　bool ifempty(); //判断队列为空

　　int alen(); //求当前队列的长度

　　int main()

　　{

　　init();

　　add(11);

　　add(12);

　　add(13);

　　cout<

　　cout<

　　cout<

　　cout<

　　return 0;

　　}

　　int alen()

　　{

　　return (tail - head +N) % N;

　　}

　　bool ifempty()

　　{

　　return head == tail;

　　}

　　bool iffull()

　　{

　　return (tail+1) % N == front;

　　}

　　int out()

　　{

　　if (ifempty())

　　{

　　cout<<"队列已空，不能出队"<

　　return 0;

　　}

　　int x = a[head];

　　head = (head+1) % N;

　　return x;

　　}

　　void add(int x)

　　{

　　if (iffull())

　　{

　　cout<<"队列已满，不能加入"<

　　return ;

　　}

　　a[tail] = x;

　　tail = (tail+1) % N;

　　}

　　void init()

　　{

　　head =0;

　　tail =0;

　　}

　　信息学奥赛循环队列相关题目：

　　1、设循环队列中数组的下标范围是l-n,其头指针和尾指针分别为f和r，则其元素个数为()

　　A.r-f， B.r-f+1 C.(r-f) % n+1 D.(r-f+n)% n

　　2、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3，则当队列删除一个元素，再加两个元素后，rear和front的值分别是()

　　A.1和5 B.2和4 C.4和2 D.5和1

　　3、循环队列中rear和font的值是15和32，队列长度是60，则队列中的元素有()

　　A.42 B.16 C.17 D 43

　　作者：noipbar

　　链接：https://www.jianshu.com/p/045b6fbb846e

　　来源：简书

　　著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

尊重原创文章，转载请注明出处与链接：http://www.peixun360.com/963/news/628452/违者必究！ 以上就是海口童程童美少儿编程培训学院 小编为您整理 学信息学奥赛循环队列的全部内容。