如何做百度秒收录网站,手机net网站开发,网站建设营销公司,重庆营销型网站建设公司队列 队列是什么#xff0c;先联想一下队#xff0c;排队先来的人排前面先出#xff0c;后来的人排后面后出#xff1b;队列的性质也一样#xff0c;先进队列的数据先出#xff0c;后进队列的后出#xff1b;就像图一的样子#xff1a; 图1 如图1#xff0c;1号元素是… 队列 队列是什么先联想一下队排队先来的人排前面先出后来的人排后面后出队列的性质也一样先进队列的数据先出后进队列的后出就像图一的样子 图1 如图11号元素是最先进的开始出队时那么他就是最先出的然后12进队就应该排在最后面等待前面的所有元素出队完成后才能出队有个专业的名词叫FIFO(first in first out)翻译过来就是先进先出的意思 队列的数据结构 数据结构 结构定义 结构操作 队列的结构定义就是 物理结构 一个存储数据的数据域这里我们用的是数组一个头指针一个尾指针头指针指向下个出队的元素的位置尾指针指向最后一个元素的位置然后还有队列的长度元素个数 那么用结构体封装他的物理结构代码如下 typedef struct Queue {int size, cnt, head, tail;//4个变量分别是队列长度元素个数头指针尾指针//因为用的是数组所以头尾指针直接用一个int变量就可以存贮了void *data;//数据域
} Queue; 逻辑结构 他的逻辑结构就是先进先出需要去维护这个性质如果破坏了性质就不能算做数据结构了因为你破坏了它的结构定义所以一定不要破坏数据结构的结构定义 结构操作 说完了结构定义来看下队列它是如何出队入队的 现在出队一个元素那么Head指针就应该指向下一个位置也就是位置1那么headhead 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.htypedef 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;
}
