①版本1(数据采用顺序表存储方法)：注：本文只给出C语言实现代码，涉及到的数据结构相关概念请自行阅读相关书籍或参考其他博文；
实现顺序存储版队列，即容量大小固定，包含入队、出队、查询队头元素等操作。
#include②版本2(增加自动扩容)：#include #include typedef struct Queue { int *data; //存储的数据 //head头下标，tail尾下标size队列元素个数 int head, tail, size; int capacity; //队列容量 } Queue; Queue *init(int n) { //初始化 Queue *q = (Queue *)malloc(sizeof(Queue)); q->data = (int *)malloc(sizeof(int) * n); q->capacity = n; q->head = q->tail = 0; //初始化方式一;方式二可用tail指向队尾元素的下一个位置 q->size = 0; return q; } void clear(Queue *q) { //删除队列 if (q == NULL) return ; free(q->data); free(q); return ; } int empty(Queue *q) {//判空 //return q->head == q->tail; //判断队列是否为空 return q->size == 0; } int front(Queue *q) {//查询队首元素 return q->data[q->head]; } int push(Queue *q, int val) {//入队 if (q == NULL) return 0; if (q->size == q->capacity) { printf("faile to expand!n"); return 0; } q->data[q->tail++] = val; if (q->tail == q->capacity) q->tail = 0; q->size++; return 1; } int pop(Queue *q) {//出队 if (q == NULL) return 0; if (empty(q)) return 0; q->head++; if (q->head == q->capacity) q->head = 0; q->size--; return 1; } void output(Queue *q) {//打印队列元素 if (q == NULL) return ; printf("Queue(%d): [", q->size); for(int i = q->head, j = 0; j < q->size; j++) { j && printf(","); printf("%d", q->data[(i + j) % q->capacity]); } printf("]n"); return ; } int main(int argc, int **argv) { srand(time(0)); #define MAX_N 20 Queue *q = init(MAX_N); for (int i = 0; i < MAX_N; i++) { int op = rand () % 4; int val = rand() % 100; switch(op) { case 0: case 1: case 2: { printf("push %d to the Queue = %dn", val, push(q, val)); } break; case 3: { if(!empty(q)) { printf("pop %d from the Queue = ", front(q)); printf("%dn", pop(q)); } } break; } output(q); } #undef MAX_N clear(q); return 0; }
实现顺序存储版队列，即容量大小固定，包含入队、出队、查询队头元素等操作。
#include③ 版本3(数据采用链式存储方法)：#include #include #define COLOR(a, b) " 33[" #b "m" a "33[0m" #define RED(a) COLOR(a, 31) #define GREEN(a) COLOR(a, 32) typedef struct Queue { int *data; int head, tail, size; int capacity; //队列容量 } Queue; Queue *init(int n) { Queue *q = (Queue *)malloc(sizeof(Queue)); q->data = (int *)malloc(sizeof(int) * n); q->capacity = n; q->head = q->tail = 0; //初始化方式一;方式二可用tail指向队尾元素的下一个位置 q->size = 0; return q; } void clear(Queue *q) { if (q == NULL) return ; free(q->data); free(q); return ; } int empty(Queue *q) { //return q->head == q->tail; //判断队列是否为空 return q->size == 0; } int front(Queue *q) { return q->data[q->head]; } int expand(Queue *q) { int extr_size = q->capacity; int *temp; while (extr_size) { //可用calloc, 不建议用realloc, 队列是一个有序的序列，拷贝完后进行值拷贝 //realloc拷贝过程可能出问题。因为头指针可能在尾指针后面，拷贝过来处理不好有bug temp = (int *)malloc(sizeof(int) * (q->capacity + extr_size)); if (temp) break; //申请新内存成功则进行下一步操作； extr_size >>= 1; //申请新内存不成功则将申请空间减小一半； } if (temp == NULL) return 0; //将数据拷贝到新申请的空间 for (int i = q->head, j = 0; j < q->size; j++) { temp[j] = q->data[(i + j) % q->capacity]; } free(q->data);//释放旧内存空间； q->data = temp; q->head = 0, q->tail = q->size; q->capacity += extr_size; printf(GREEN("expand successfully! the size is %dn"), q->capacity); return 1; } int push(Queue *q, int val) { if (q == NULL) return 0; if (q->size == q->capacity) { if (!expand(q)) { printf(RED("faile to expand!n")); return 0; } } q->data[q->tail++] = val; if (q->tail == q->capacity) q->tail = 0; q->size++; return 1; } int pop(Queue *q) { if (q == NULL) return 0; if (empty(q)) return 0; q->head++; if (q->head == q->capacity) q->head = 0; q->size--; return 1; } void output(Queue *q) { if (q == NULL) return ; printf("Queue(%d): [", q->size); for(int i = q->head, j = 0; j < q->size; j++) { j && printf(","); printf("%d", q->data[(i + j) % q->capacity]); } printf("]n"); return ; } int main(int argc, int **argv) { srand(time(0)); #define MAX_N 20 Queue *q = init(1); for (int i = 0; i < MAX_N; i++) { int op = rand () % 4; int val = rand() % 100; switch(op) { case 0: case 1: case 2: { printf("push %d to the Queue = %dn", val, push(q, val)); } break; case 3: { if(!empty(q)) { printf("pop %d from the Queue = ", front(q)); printf("%dn", pop(q)); } } break; } output(q); } #undef MAX_N clear(q); return 0; }
实现链式存储版队列，即容量根据数据量自动调整，包含入队、出队、查询队头元素等操作。
#include#include #include typedef struct Node { int data; struct Node *next; } Node; typedef struct Queue { Node head, *tail;//虚拟头节点 int length;//链队列元素个数 } Queue; Node *getNewNode(int); Queue *init_queue(); void clear_node(Node *); void clear(Queue *); int push(Queue *, int); int pop(Queue *); int empty(Queue *); int front(Queue *); void output(Queue *); Node *getNewNode(int val) { Node *node = (Node *)malloc(sizeof(Node)); node->data = val; node->next = NULL; return node; } Queue *init_queue() { Queue *q = (Queue *)malloc(sizeof(Queue)); q->head.next = NULL; q->tail = &(q->head); q->length = 0; return q; } int empty(Queue *q) { return q->length == 0;//判断队列是否为空，用q->tail == NULL,栈空的时候会出错 } int front(Queue *q) { return q->head.next->data; } int push(Queue *q, int val) { if (q == NULL) return 0; Node *temp = getNewNode(val); q->tail->next = temp; q->tail = temp; q->length += 1; return 1; } int pop(Queue *q) { if (q == NULL) return 0; if (empty(q)) return 0; Node *temp = q->head.next; q->head.next = temp->next; clear_node(temp); q->length -= 1; if (q->length == 0) q->tail = &(q->head); //没有改句在队列只有一个节点的时候删除了该节点会丢失tail return 1; } void clear_node(Node *node) { if (node == NULL) return; free(node); return; } void clear(Queue *q) { if (q == NULL) return; Node *p = q->head.next, *temp; while (p != NULL) { temp = p->next; clear_node(p); p = temp; } free(q); return ; } void output(Queue *q) { if (q == NULL) return; printf("Queue(%d) : [", q->length); for (Node *p = q->head.next; p != NULL; p = p->next) { p != q->head.next && printf(", "); printf("%d", p->data); } printf("]n"); return; } int main() { srand(time(0)); Queue *q = init_queue(); #define MAX_OP 20 for (int i = 0; i < MAX_OP; i++) { int op = rand() % 4; int val = rand() % 100; switch(op) { case 1: case 2: { printf("push %d to the Queue = %dn", val, push(q, val)); } break; case 0: case 3: { if(!empty(q)) { printf("pop %d from the Queue = ", front(q)); printf("%dn", pop(q)); } } break; } output(q), printf("n"); } #undef MAX_OP clear(q); return 0; }
