信息学奥赛系列教程:循环队列

循环队列:

上一次介绍了队列的基本概念、性质和操作,本次介绍循环队列。

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

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


元素入队时,入队一个元素尾指针+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 <iostream>

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<<out()<<endl;

cout<<out()<<endl;

cout<<out()<<endl;

cout<<out()<<endl;

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<<"队列已空,不能出队"<<endl;

return 0;

}

int x = a[head];

head = (head+1) % N;

return x;

}

void add(int x)

{

if (iffull())

{

cout<<"队列已满,不能加入"<<endl;

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

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,639评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,277评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,221评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,474评论 1 283
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,570评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,816评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,957评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,718评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,176评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,511评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,646评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,322评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,934评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,755评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,987评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,358评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,514评论 2 348

推荐阅读更多精彩内容

  • 队列的概念: 现实生活中,经常可以看到队列的例子,如排队买票,先来的人买了票,先离开,后面来的只有等前面离开...
    noipbar阅读 479评论 0 1
  • 本文是我自己在秋招复习时的读书笔记,整理的知识点,也是为了防止忘记,尊重劳动成果,转载注明出处哦!如果你也喜欢,那...
    波波波先森阅读 11,244评论 4 56
  • 题目类型 a.C++与C差异(1-18) 1.C和C++中struct有什么区别? C没有Protection行为...
    阿面a阅读 7,643评论 0 10
  • 【0510我在悦读】鹅芙 三期活动第10次打卡 书名:《秘密》 作者:朗达-拜恩 篇目:1-2目录 金句: ①就是...
    鹅芙阅读 267评论 0 0
  • 好久没有写日记了,这两天看到几位死党一直在写修行日记,记录自己生活中点点滴滴和心得体会,被他们的认真和坚持所感染…...
    高波_体心脑训练师阅读 556评论 7 4