数据结构--队列与循环队列

队列

        队列是什么，先联想一下队，排队先来的人排前面先出，后来的人排后面后出；队列的性质也一样，先进队列的数据先出，后进队列的后出；就像图一的样子：

 图1

        如图1，1号元素是最先进的，开始出队时，那么他就是最先出的，然后12进队，就应该排在最后面，等待前面的所有元素出队完成后才能出队；有个专业的名词叫FIFO(first in first out)，翻译过来就是先进先出的意思；

队列的数据结构：

        数据结构 = 结构定义 + 结构操作；

        队列的结构定义就是：

       物理结构：

        一个存储数据的数据域，这里我们用的是数组；一个头指针，一个尾指针；头指针指向，下个出队的元素的位置，尾指针指向最后一个元素的位置，然后还有队列的长度，元素个数；

        那么用结构体封装他的物理结构代码如下：

typedef struct Queue {int size, cnt, head, tail;//4个变量分别是，队列长度，元素个数，头指针，尾指针//因为用的是数组，所以头尾指针，直接用一个int变量就可以存贮了void *data;//数据域
} Queue;

        逻辑结构：

        他的逻辑结构就是，先进先出，需要去维护这个性质，如果破坏了性质就不能算做数据结构了，因为你破坏了它的结构定义；所以一定不要破坏数据结构的结构定义；

结构操作：

        说完了结构定义来看下，队列它是如何出队入队的：

        现在出队一个元素，那么Head指针就应该指向下一个位置，也就是位置1，那么head++，head = 1：

         现在入队一个元素，假如入队元素12，那么Tail指针应该先Tail++，在放入新元素，不然就覆盖掉了元素11，如下图：

        可能有人会问，1不是出队了嘛，为什么在图中还有，是我画图没有画完，但是，在写代码的时候，情况就是这样的，因为这是一个数组，你只是吧头指针往后偏移了，但是那个位置的元素他还是存在的，只是不会去访问到了，那么他也相当于出队了；也就是相当于我们在数组上面维护了一个队列，他从头部减少，尾部增加的一个思想；

循环队列

        提到队列了，也不得不提循环队列，循环队列是什么，假如长度为10的队列，它入队了10个元素，也出队了10个元素，那么头尾指针现在是在同一个位置，就是下图情况：

        他现在里面是没有元素的，你现在看到的1-9是已经出队了的，10是还没有出队的，那么怎么办，那就直接让tail = 0，又从数组的头部开始 ，如图

        

         元素11入队，直接覆盖掉之前的元素1，那么下次入队就是从位置1开始，出队还是元素10先出队，然后出队后，Head指针那么也应该等于0，也从数组的头开始再次出队；

        那么如何去判断队列为空呢，在定义物理结构是吗，有一个变量记录着，队列当前的元素个数；

代码实现：

        那么思路大概讲完了，代码实现的是循环队列，来看代码实现：

        

#include <stdio.h>
#include <stdlib.h>
#include <time.h>typedef struct Queue {int size, cnt, head, tail;//4个变量分别是，队列长度，元素个数，头指针，尾指针//因为用的是数组，所以头尾指针，直接用一个int变量就可以存贮了int *data;//数据域
} Queue;Queue *init(int n) {//初始化队列，向计算机借空间Queue *q = (Queue *)malloc(sizeof(Queue));q->data = (int *)malloc(sizeof(int) * n);q->size = n;q->cnt = q->head = q->tail = 0;return q;
}
int empty(Queue *);
int front(Queue *q) {//获取队列头部元素if(empty(q)) return -1;return q->data[q->head];
}int empty(Queue *q) {//判读队列是否为空return q->cnt == 0;
}int push(Queue *q, int val) {//入队if (q->cnt == q->size) return 0;q->data[q->tail++] = val;if (q->tail == q->size) q->tail = 0;q->cnt++;return 1;
}int pop(Queue *q) {//出队if (empty(q)) return 0;q->head++;q->cnt--;if (q->head == q->size) q->head = 0;return 1;
}
void clear(Queue *q) {//有借有还if (!q) return ;free(q->data);free(q);return ;
}void output(Queue *q) {//打印队列中的元素printf("Queue(%d) :[", q->cnt);for (int i = q->head, j = 0; j < q->cnt; j++) {j && printf(" ");printf("%d", q->data[(i + j) % q->size]);}printf("]\n");return ;
}int main() {//测试srand(time(0));int op, val;Queue *q = init(5);for (int i = 0; i < 20; i++) {op = rand() % 4;         val = rand() % 100;switch (op) {case 0:case 1:case 2: {printf("%d push in Queue is %d\n", val, push(q, val));} break;case 3: {printf("%d ", front(q));printf("pop Queue is %d\n", pop(q));} break;}output(q);}clear(q);return 0;
}