【循环队列的简单知识】队列其实也是链表，这里讲的是顺序表示。队列，顾名思义，就是排队的队形。按照专业一点就是FIFO(first in first out) 原则，从对列头出列，从对尾入列。
因为循环队列最利用效率，也稍微增加了难度，所以要记住循环队列的表示方法。
其实很多数据结构都有很多种写法，重要是理解其思想，代码完成只是让自己更加透彻的掌握，每一种实现方式都是按其思想一步一步完成的。
先贴出结构体：
typedef struct queue {
int*Base;
//数组头指针
int front;
//对头
int rear;
//队尾。。实际就是数组下标
int size;
//队列长度
}Queue;
如果不同的数据类型 int *Base 的类型记得换，还有好多地方 ，记得就行了。
之所以用循环队列，是因为对头只能出，对尾只能入，这样就变成了上面的位置空出后就一直空着了，造成了很大的浪费啊。
我之前学的时候循环队列的时候就觉得很晕，主要是当时我的确太渣了，现在理解了其中的道理，感觉还是挺好玩的。循环的意思并没有违背对头对尾的概念，就像我在一个圆圈上开了俩个洞，一个标为头，一个标为尾，所以不管转或不转，我的标志就在那儿。
我们这样想，假如这个循环的圈圈，有6个位置，但是我们只装5个数（代码有注释），
e→ d →c →b→ a头
↑|
————————
下标是 4 3 2 1 0等到装满的时候便不能装了，然后出对是不，那么这时候a下标为0从头出去了，那么对头就变成 q->front = (q->front+1) % q->size;
成为了1，然后有数f来入队，那么此时对尾变成了 q->rear = (q->rear +1)% q->size;
成为了0，看到了没，就因为简单的取余的操作，我的下标永远在0-4间循环，就成为了循环队列。 好了，也许和我当初学的时候想的不一样，以后还是觉得把刚学的知识，马上写出感受才好，新鲜又贴近最真实的感觉。
#include
#include
#include typedef struct queue { int *Base;
//数组头指针
int front;
//对头
int rear;
//队尾。。实际就是数组下标
int size;
//队列长度
}Queue;
void InitQueue(Queue *q, int size) {
q->size = size;
q->Base = (int *)malloc(sizeof(int)*q->size);
//分配内存空间
if(NULL == q->Base) {
printf("failed!\n");
exit(-1);
}
q->front = 0;
q->rear = 0;
//初始化队列里没有元素 下标为0
}void DestroyQueue(Queue *q) {
q->front = 0;
q->rear = 0;
q->size = 0;
free(q->Base);
//回收空间
q->Base = NULL;
}void clearQueue(Queue *q) {
q->front = 0;
q->rear = 0;
}bool isEmpty(Queue *q) {
if(q->front == q->rear ) {//空队列里面肯定头尾在一起
printf("empty!\n");
return true;
}else
return false;
}
bool isFull(Queue *q) {
if((q->rear+1)%q->size == q->front) {
// 循环队列当取余头尾相等时代表队列已满,+1代表空余一个就表示已满否则取余就无意思
printf("Full!\n");
return true;
}
else
return false;
}
bool getHead(Queue *q, int *e) { if(isEmpty(q)) {
printf("no head element\n");
return false;
}else {
*e = q->Base[q->front];
printf("the head is :%d\n ",*e);
return true;
}
}int length(Queue *q) {
return (q->rear - q->front +q->size) % q->size;
// return (q->rear - q->front ) % q->size;
//这样容易造成长度为负数（因为是循环队列 对头队尾不知道那个比较大）
}
//出对入队只要记着队尾入队，对头出对即可。
bool enQueue(Queue *q, int item) {
if(isFull(q)){
return false;
}
else {
q->Base[q->rear] = item;
q->rear = (q->rear +1)% q->size;
}
return true;
}
bool deQueue(Queue *q, int *item) {
if(isEmpty(q))
return false;
else {
*item = q->Base[q->front];
q->front = (q->front+1) % q->size;
} return true;
}
//测试程序
int main() {
int temp;
Queue q;
InitQueue(&q,5);
printf("%d\n",isEmpty(&q));
enQueue(&q,1);
deQueue(&q,&temp);
enQueue(&q,2);
enQueue(&q,8);
deQueue(&q,&temp);
enQueue(&q,18);
enQueue(&q,3);
deQueue(&q,&temp);
enQueue(&q,4);
enQueue(&q,5);
printf("the length:%d \n",length(&q));
int a;
getHead(&q,&a);
for(int i =1 ;
i <=4;
i++) {
int item;
deQueue(&q,&item);
printf("%d ",item);
}
DestroyQueue(&q);
//队列已经销毁 任何操作都没用了
//enQueue(&q,1);
getHead(&q,&a);
return 0;
} 推荐阅读
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历
- 数据结构|C++技巧（用class类实现链表）
- 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
- 算法|算法-二分查找
- 数据结构学习指导|数据结构初阶（线性表）
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- java|ObjectOrientedProgramming - 面向对象的编程（多态、抽象类、接口）- Java - 细节狂魔