队列（循环队列）----C语言
线性结构：有且只有一个根节点，且每个节点最多有一个直接前驱和一个直接后继的非空数据结构
非线性结构：不满足线性结构的数据结构
队列
队列一般分为两类：链式队列和顺序队列
链式队列---链式队列即用链表实现的队列
顺序队列---顺序队列是用数组实现的队列，顺序队列通常必须是循环队列
1、基本概念：
队列是指允许在一端进行插入，在另一端进行删除的线性表，又称“先进先出”的线性表
队列是一种特殊的线性结构，它只允许在队列的首部（head）进行删除操作，这称为出队
队尾：允许插入的一端，用尾指针指向队尾元素的后一位置
队首：允许删除的一端，用头指针指向头元素
循环队列（顺序队列）的实现：
#include <stdio.h> #define LENGTH 11 /*定义数组最大长度 */
#define OUT 1 /* 出队 */
#define GET 2 /* 入队 */
struct queue
{
int data[LENGTH];
int head; /* 队首 */
int tail; /* 队尾 */
};
/* 循环队列的实现 */
main()
{
struct queue q;
int i;
int kk = ;
/* 初始化队列 */
q.head = q.tail = ; /*队首队尾初始化 */
/* 依次插入10个数 */
for (i = ; i < LENGTH - ; i++)
{
scanf_s("%d", &q.data[q.tail]);
q.tail = (q.tail + ) % LENGTH;
}
while ()
{
if (q.head == q.tail)
{
printf("队列已空");
break;
}
printf("出队：1\n入队：2\n");
scanf_s("%d", &kk);
if (kk == OUT)
{ q.head = (q.head + ) % LENGTH;
}
else if (kk == GET)
{
if (q.head == (q.tail + ) % LENGTH)
{
printf("队列已满");
break;
}
printf("输入入队元素：\n");
scanf_s("%d", &q.data[q.tail]);
q.tail = (q.tail + ) % LENGTH;
} if (q.tail != q.head)
{
printf("队列中剩余元素：");
for (i = q.head; ;)
{
printf("%d ", q.data[i]);
i = (i + ) % LENGTH;
if(i == q.tail)
{
putchar('\n');
break;
}
}
}
} return ;
}
2、为什么顺序队列通常必须是循环队列
循环队列是针对顺序队列中最大内存空间有限的一种解决方法，当队列（数组）不可再插入新元素但队列的实际可用空间并未占满的问题的一种合理的解决方案
3、与普通顺序队列的区别
普通顺序队列在插入新元素（入队）时为q.tail++，删除旧元素（出队）时为q.head++（q.tail和q.head都为int型，但为了描述方便这里说成指针），在出队后再想插入新元素且此时q.tail在数组的末尾即最后一位就会出现实际可用空间并未占满但无法插入新元素的问题，强行插入会造成数组越界，也不宜继续扩大数组空间，造成了空间上的浪费
循环队列的核心在于队头指针和队尾指针的增加方式
q.head = (q.head + 1) % LENGTH;
q.tail = (q.tail + 1) % LENGTH;
这样实现了臆想上存储空间的弯曲效果，也解决了空间上的浪费（建议在纸上模拟循环队列数组的出队入队操作，以理解上面两行代码）
值得注意的是
q.head指向的是队首元素
q.tail指向的是队尾元素的后一位，浪费了一位空间，例如数组q.data[11]插入10个元素后q.tail指向的是q.data[10]即q.tail = 10；
4、循环队列的新问题
当队列为空时q.head = q.tail，当队列为满时也有q.head = q.tail造成了判断队列是空还是满的二义性
解决方法： 1.增加一个参数，使删除元素为1，插入元素为0
2.增加一个参数，记录队列的元素个数即长度
3.空出一个单元，令if(q.head == (q.tail + 1) % LENGTH)为队列为满的条件，以此解决二义性
5、注意
循环队列的头指针和尾指针的减少或增加方式
队列为满或空的判定条件
循环队列参考链接：
https://www.cnblogs.com/chenliyang/p/6554141.html 该篇比较详细
https://blog.csdn.net/smile_zhangw/article/details/80894159
（编译器：Microsoft Visual C++ 2010 Express）
最新文章
- css对齐
- Cocos2d-x游戏开发之计时器
- java项目中读取src目录下的文件
- Dictionary<Key,Value>的用法
- 建立自己的bin目录，在当前路径运行shell脚本
- 接上一篇博客（解决-Dmaven.multiModuleProjectDirectory system property is not set. Check $M2_HOME environment variable and mvn script match. ）
- Jquery 遍历数组之grep()方法介绍
- API网关Ocelot 使用Polly 处理部分失败问题
- cocos2d导入iOS原生项目
- Code::Blocks 配置
- SpringBoot学习之Json数据交互
- [再寄小读者之数学篇](2014-05-27 矩阵的迹与 Jacobian)
- Spring LocalVariableTableParameterNameDiscoverer获取方法的参数名
- Allegro PCB Design GXL (legacy) 使用slide推挤走线，走线的宽度就发生改变的原因
- ipython 编辑器 jupyter notebook如何将 ipynb 转成 py 并在 jupyter notebook 中继续引用
- JavaScript--元素对象方法setAttribute() 和appendChild()
- 解决Android中多次点击(快速点击多次 )启动多个相同界面的问题
- linux命令:文件搜索命令
- POJ-1160 Post Office （DP+四边形不等式优化）
- 3——FFMPEG之解复用器-----AVInputFormat（转）