C语言实现循环队列的构建、入队、出队、扩容、遍历等操作 |
您所在的位置：网站首页 › 队列的入队操作包括 › C语言实现循环队列的构建、入队、出队、扩容、遍历等操作 |
C语言实现循环队列的构建、入队、出队、扩容、遍历等操作
|
C语言实现循环队列的构建、入队、出队、扩容、遍历等操作
一 队列的定义和初始化
在C++的STL中有queue可以直接使用，小编这里采用C语言实现队列的基本操作，毕竟学会自己“造轮子”而不是拿来主义，可以更深刻的体会队列的性质。 队列最大的性质就是先进先出，元素只可以从队尾入队，从队首出队列。至于队列和循环队列之间的区别，不及，我们后面会说。 话不多说，我们直接看数据结构定义： typedef struct queue { int *data; //数据域 int head, tail, cnt, size; //head，tail表示队首和队尾指针，cnt表示队列中元素个数，size表示数组大小 } Queue; //队列中队尾指针我们这里表示下一个可以插入元素的位置，而不是队列中队尾元素的下标 Queue *init(int size) { Queue *q = (Queue *)malloc(sizeof(Queue)); q->data = (int *)malloc(sizeof(int) * size); q->head = q->tail = q->cnt = 0; q->size = size; return q; } 二 元素入队列 将元素从队尾放入队列，很简单，直接将元素放入队列的尾部，队尾指针后移，同时队列元素个数加一 示意图如下： 将元素出队列，操作和元素入队列类似，将head指针后移，当到达数组最后一个元素的下标时，将head指向0 示意图如下： 代码逻辑较为简单，因此此处直接粘贴代码，不再赘述 bool empty(Queue *q) { //判队列空 return q->cnt == 0; } int front(Queue *q) { //取队首元素 return q->data[q->head]; } void output(Queue *q) { //遍历输出 if (!q) return ; printf("queue(%d) = [", q->cnt); for (int i = 0, j = q->head; i cnt; i++) { if (i) printf(", "); printf("%d", q->data[(i + j) % q->size]); } printf("]\n"); } void clear(Queue *q) { //删除队列 if (!q) return ; free(q->data); free(q); } 五 总代码献上 #include using namespace std; typedef struct queue { int *data; int head, tail, cnt, size; } Queue; Queue *init(int size) { Queue *q = (Queue *)malloc(sizeof(Queue)); q->data = (int *)malloc(sizeof(int) * size); q->head = q->tail = q->cnt = 0; q->size = size; return q; } bool empty(Queue *q) { return q->cnt == 0; } int front(Queue *q) { return q->data[q->head]; } bool expand(Queue *q) { int extra_size = q->size; int *old_data = q->data; while (extra_size) { q->data = (int *)malloc(sizeof(int) * (q->size + extra_size)); if (q->data) break; extra_size /= 2; } if (!q->data) return false; for (int i = 0, j = q->head; i cnt; i++) { q->data[i] = old_data[(i + j) % q->size]; } q->head = 0, q->tail = q->cnt; q->size += extra_size; free(old_data); return true; } bool push(Queue *q, int val) { if (!q) return q; if (q->cnt == q->size) { if (expand(q)) printf("expand success!\n"); else { printf("expand failed\n"); return false; } } q->data[q->tail++] = val; if (q->tail == q->size) q->tail = 0; q->cnt++; return true; } bool pop(Queue *q) { if (!q || q->cnt == 0) return false; q->head++; if (q->head == q->size) q->head = 0; q->cnt--; return true; } void output(Queue *q) { if (!q) return ; printf("queue(%d) = [", q->cnt); for (int i = 0, j = q->head; i cnt; i++) { if (i) printf(", "); printf("%d", q->data[(i + j) % q->size]); } printf("]\n"); } void clear(Queue *q) { if (!q) return ; free(q->data); free(q); } int main() { #define MAX_OP 20 srand(time(0)); Queue *q = init(1); int val, op; for (int i = 0; i |
但是这里有一个问题，我们现在是用一个数组来存储元素，那么随着元素的入队出队，head和tail指针将会不断的后移，当数组最后一个空格已经存入元素，此时若我们想要再存入元素，数组是不是已经满了呢？我们现在是不是要重新申请一片数组空间，再将现在的元素复制过去呢？ 显然不是，因为随着元素出队列，head向后移动，所以数组的前面部分是空的，我们可以利用这一部分来存储元素，其实这就是循环队列，而不是普通的队列 (是不是感觉很简单？) 示意图如下： 
对应实现代码为：
实现代码如下：【本文地址】