数据结构--队列(C语言实现)

文章目录 一、简介二、顺序结构的队列三、顺序结构循环队列四、链式结构的队列五、总结

一、简介

队列（Queue）是一种常见的数据结构，遵循“先进先出”（FIFO, First In First Out）的原则。队列的应用非常广泛，例如任务调度、缓冲区管理、广度优先搜索等。

队列通常支持以下几种基本操作：

入队（enqueue）：将元素添加到队列的末尾。出队（dequeue）：移除队列的第一个元素，并返回它。查看队首元素（getHead）：返回队列的第一个元素，但不移除它。判断队列是否为空（IsEmpty）：检查队列是否为空。判断队列是否满了（IsFull）：对于固定大小的队列。获取队列大小（getSize）：返回队列中元素的数量。 二、顺序结构的队列

顺序结构的队列，在C语言中可以借助数组 加队头、队尾指针 来实现。假设队列为 q = (a1, a2, …, an)，那么，a1 就是队头元素，an 就是队尾元素。队列中的元素是按照 a1, a2, …, an 的顺序进入的，退出队列也只能按照这个次序依次退出，也就是说，只有在 a1, a2, …, an-1 都离开队列之后，an 才能退出队列。 顺序结构队列的C语言结构：

typedef struct { ElemType *data; int front; //队头指针（记录队头位置） int rear; //队尾指针（记录队尾位置） }Queue; (1) 初始化队列（动态分配） Queue* initQueue(void) { Queue *q = (Queue*)malloc(sizeof(Queue)); if(NULL == q) { perror("malloc Error: "); return NULL; } q->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE); if(NULL == q->data) { free(q); q = NULL; perror("malloc Error: "); return NULL; } /* 队头、队尾指针初始值为0 */ q->front = 0; q->rear = 0; return q; } (2) 销毁队列 void destoryQueue(Queue *Q) { if(Q) { if(Q->data) { free(Q->data); Q->data = NULL; } free(Q); Q = NULL; } } (3)判断是否空 bool isEmpty(Queue *Q) { /* 队头指针和队尾指针相等，说明是空队列 */ if(Q->front == Q->rear) { return 1; } else { return 0; } } (4)判断是否满 bool isFull(Queue *Q) { /* rear到了数组末尾元素位置，且front在数组首元素位置，则队列是真的满了 */ if(Q->rear >= MAXSIZE) { if(Q->front > 0) { /* 移动队列到数组首元素位置 */ int step = Q->front; for (int i = Q->front; i <= Q->rear; ++i) { Q->data[i - step] = Q->data[i]; } Q->front = 0; Q->rear = Q->rear - step; return false; } else { return true; } } else { return false; } } (5)入队 int equeue(Queue *Q, ElemType elem) { if(isFull(Q)) { printf("queue is full\n"); return -1; } /* 先插入元素，再移动队尾指针 */ Q->data[Q->rear] = elem; Q->rear++; return 0; } (6)出队 ElemType dequeue(Queue *Q, ElemType *elem) { if(isEmpty(Q)) { printf("queue is empty\n"); return -1; } /* 先取出元素，再移动队头指针 */ *elem = Q->data[Q->front]; Q->front++; return 0; } (7)获取队头元素 int getHead(Queue *Q, ElemType *elem) { if(isEmpty(Q)) { printf("queue is empty\n"); return -1; } *elem = Q->data[Q->front]; return 0; } (8)获取大小 int getSize(Queue *Q) { return (Q->rear - Q->front); } (9)完整代码 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> //顺序结构队列 #define MAXSIZE 3 typedef int ElemType; typedef struct { ElemType *data; int front; //队头指针（记录队头位置） int rear; //队尾指针（记录队尾位置） }Queue; /***************************************************************** * 函数功能 : 初始化队列 * 参数 : void * 返回值 : 成功：Queue* 指针，失败：NULL ******************************************************************/ Queue* initQueue(void) { Queue *q = (Queue*)malloc(sizeof(Queue)); if(NULL == q) { perror("malloc Error: "); return NULL; } q->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE); if(NULL == q->data) { free(q); q = NULL; perror("malloc Error: "); return NULL; } /* 队头、队尾指针初始值为0 */ q->front = 0; q->rear = 0; return q; } /***************************************************************** * 函数功能 : 销毁 * 参数 : Q(in):队列 * 返回值 : void ******************************************************************/ void destoryQueue(Queue *Q) { if(Q) { if(Q->data) { free(Q->data); Q->data = NULL; } free(Q); Q = NULL; } } /***************************************************************** * 函数功能 : 判断队列是否为空 * 参数 : Q(in):队列 * 返回值 : 空：true, 非空：false ******************************************************************/ bool isEmpty(Queue *Q) { /* 队头指针和队尾指针相等，说明是空队列 */ if(Q->front == Q->rear) { return 1; } else { return 0; } } /***************************************************************** * 函数功能 : 判断队列是否满 * 参数 : Q(in):队列 * 返回值 : 满：true, 没满：false ******************************************************************/ bool isFull(Queue *Q) { /* rear到了数组末尾元素位置，且front在数组首元素位置，则队列是真的满了 */ if(Q->rear >= MAXSIZE) { if(Q->front > 0) { /* 移动队列到数组首元素位置 */ int step = Q->front; for (int i = Q->front; i <= Q->rear; ++i) { Q->data[i - step] = Q->data[i]; } Q->front = 0; Q->rear = Q->rear - step; return false; } else { return true; } } else { return false; } } /***************************************************************** * 函数功能 : 入队 * 参数 : Q(in):队列 * 返回值 : 成功：0，失败：-1 ******************************************************************/ int equeue(Queue *Q, ElemType elem) { if(isFull(Q)) { printf("queue is full\n"); return -1; } /* 先插入元素，再移动队尾指针 */ Q->data[Q->rear] = elem; Q->rear++; return 0; } /***************************************************************** * 函数功能 : 出队 * 参数 : Q(in):队列 * 参数 : elem(out):出队元素值 * 返回值 : 成功：0，失败：-1 ******************************************************************/ ElemType dequeue(Queue *Q, ElemType *elem) { if(isEmpty(Q)) { printf("queue is empty\n"); return -1; } /* 先取出元素，再移动队头指针 */ *elem = Q->data[Q->front]; Q->front++; return 0; } /***************************************************************** * 函数功能 : 获取队头元素 * 参数 : Q(in):队列 * 参数 : elem(out):队头元素值 * 返回值 : 成功：0，失败：-1 ******************************************************************/ int getHead(Queue *Q, ElemType *elem) { if(isEmpty(Q)) { printf("queue is empty\n"); return -1; } *elem = Q->data[Q->front]; return 0; } /***************************************************************** * 函数功能 : 获取队列大小 * 参数 : Q(in):队列 * 返回值 : 队列大小 ******************************************************************/ int getSize(Queue *Q) { return (Q->rear - Q->front); } //测试 int main(int argc, char const *argv[]) { //初始化队列 Queue *queue = initQueue(); printf("queue size:%d\n",getSize(queue)); //入队 equeue(queue, 10); equeue(queue, 20); equeue(queue, 30); equeue(queue, 40); //已经满了 printf("queue size:%d\n",getSize(queue)); //出队 ElemType elem; dequeue(queue, &elem); printf("dequeue: %d\n",elem); dequeue(queue, &elem); printf("dequeue: %d\n",elem); dequeue(queue, &elem); printf("dequeue: %d\n",elem); dequeue(queue, &elem); //已经空了 printf("queue size:%d\n",getSize(queue)); equeue(queue, 10); //获取队头 getHead(queue, &elem); printf("queue head:%d\n", elem); //销毁 destoryQueue(queue); return 0; } 三、顺序结构循环队列

顺序结构循环队列的相比于非循环队列的好处在于，判断队列是否满时，不用移动队列。

(1) 初始化队列（动态分配） Queue* initQueue() { Queue *q = (Queue*)malloc(sizeof(Queue)); if(NULL == q) { perror("malloc Error: "); return NULL; } q->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE); if(NULL == q->data) { perror("malloc Error: "); free(q); q = NULL; return NULL; } q->front = 0; q->rear = 0; return q; } (2) 销毁队列 void destoryQueue(Queue *Q) { if(Q) { if(Q->data) { free(Q->data); Q->data = NULL; } free(Q); Q = NULL; } } (3)判断是否空 bool isEmpty(Queue *Q) { if (Q->front == Q->rear) { return true; } else { return false; } } (4)判断是否满 bool isFull(Queue *Q) { /* 按照队尾指针指向队尾元素的下一个元素方式，这个判满公式会有一个空闲 */ if ((Q->rear + 1) % MAXSIZE == Q->front) { return true; } return false; } (5)入队 int equeue(Queue *Q, ElemType elem) { if(isFull(Q)) { printf("queue is full\n"); return -1; } Q->data[Q->rear] = elem; Q->rear = (Q->rear + 1) % MAXSIZE; return 0; } (6)出队 int dequeue(Queue *Q, ElemType *elem) { if(isEmpty(Q)) { printf("queue is empty\n"); return -1; } *elem = Q->data[Q->front]; Q->front = (Q->front + 1) % MAXSIZE; return 0; } (7)获取队头元素 int getHead(Queue *Q, ElemType *elem) { if(isEmpty(Q)) { printf("queue is empty\n"); return -1; } *elem = Q->data[Q->front]; return 0; } (8)获取大小 int getSize(Queue *Q) { if(Q->rear < Q->front) { return (Q->rear + MAXSIZE - Q->front); } else { return (Q->rear - Q->front); } } (9)完整代码 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> //顺序结构循环队列 #define MAXSIZE 4 typedef int ElemType; typedef struct { ElemType *data; int front; int rear; }Queue; /***************************************************************** * 函数功能 : 初始化队列 * 参数 : void * 返回值 : 成功：Queue* 指针，失败：NULL ******************************************************************/ Queue* initQueue() { Queue *q = (Queue*)malloc(sizeof(Queue)); if(NULL == q) { perror("malloc Error: "); return NULL; } q->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE); if(NULL == q->data) { perror("malloc Error: "); free(q); q = NULL; return NULL; } q->front = 0; q->rear = 0; return q; } /***************************************************************** * 函数功能 : 销毁 * 参数 : Q(in):队列 * 返回值 : void ******************************************************************/ void destoryQueue(Queue *Q) { if(Q) { if(Q->data) { free(Q->data); Q->data = NULL; } free(Q); Q = NULL; } } /***************************************************************** * 函数功能 : 判断队列是否为空 * 参数 : Q(in):队列 * 返回值 : 空：true, 非空：false ******************************************************************/ bool isEmpty(Queue *Q) { if (Q->front == Q->rear) { return true; } else { return false; } } /***************************************************************** * 函数功能 : 判断队列是否满了 * 参数 : Q(in):队列 * 返回值 : 满：true, 没满：false ******************************************************************/ bool isFull(Queue *Q) { /* 按照队尾指针指向队尾元素的下一个元素方式，这个判满公式会有一个空闲 */ if ((Q->rear + 1) % MAXSIZE == Q->front) { return true; } return false; } /***************************************************************** * 函数功能 : 入队 * 参数 : Q(in):队列 * 参数 : elem(in):入队元素 * 返回值 : 成功：0，失败：-1 ******************************************************************/ int equeue(Queue *Q, ElemType elem) { if(isFull(Q)) { printf("queue is full\n"); return -1; } Q->data[Q->rear] = elem; Q->rear = (Q->rear + 1) % MAXSIZE; return 0; } /***************************************************************** * 函数功能 : 出队 * 参数 : Q(in):队列 * 参数 : elem(out):出队元素 * 返回值 : 成功：0，失败：-1 ******************************************************************/ int dequeue(Queue *Q, ElemType *elem) { if(isEmpty(Q)) { printf("queue is empty\n"); return -1; } *elem = Q->data[Q->front]; Q->front = (Q->front + 1) % MAXSIZE; return 0; } /***************************************************************** * 函数功能 : 获取队头元素 * 参数 : Q(in):队列 * 参数 : elem(out):队列头元素 * 返回值 : 成功：0，失败：-1 ******************************************************************/ int getHead(Queue *Q, ElemType *elem) { if(isEmpty(Q)) { printf("queue is empty\n"); return -1; } *elem = Q->data[Q->front]; return 0; } /***************************************************************** * 函数功能 : 获取队列大小 * 参数 : Q(in):队列 * 返回值 : 队列大小 ******************************************************************/ int getSize(Queue *Q) { if(Q->rear < Q->front) { return (Q->rear + MAXSIZE - Q->front); } else { return (Q->rear - Q->front); } } //测试 int main(int argc, char const *argv[]) { //初始化队列 Queue *queue = initQueue(); printf("queue size:%d\n",getSize(queue)); //入队 equeue(queue, 10); equeue(queue, 20); equeue(queue, 30); equeue(queue, 40); //已经满了 printf("queue size:%d\n",getSize(queue)); //出队 ElemType elem; dequeue(queue, &elem); printf("dequeue: %d\n",elem); dequeue(queue, &elem); printf("dequeue: %d\n",elem); dequeue(queue, &elem); printf("dequeue: %d\n",elem); dequeue(queue, &elem); //已经空了 printf("queue size:%d\n",getSize(queue)); equeue(queue, 10); //获取队头 getHead(queue, &elem); printf("queue head:%d\n", elem); //销毁 destoryQueue(queue); return 0; } 四、链式结构的队列

链式结构的队列，和链表相似，不同的是：队列是先进先出。所以，用链表头端作为队头，链表尾端作为队尾，入队就是链表的尾插法，出队就是删除头节点指向的节点。

C语言栈结构实现：

typedef struct QueueNode { ElemType data; struct QueueNode *next; }QueueNode; typedef struct { QueueNode *front; //队头 QueueNode *rear; //队尾 }Queue; (1) 初始化队列 Queue* initQueue() { Queue *q = (Queue*)malloc(sizeof(Queue)); if(NULL == q) { perror("malloc Error: "); return NULL; } /* 头节点 */ QueueNode *node = (QueueNode*)malloc(sizeof(QueueNode)); if(NULL == node) { perror("malloc Error: "); free(q); q = NULL; return NULL; } node->data = 0; node->next = NULL; /* 队头、队尾都等于头节点 */ q->front = node; q->rear = node; return q; } (2)判断是否空 bool isEmpty(Queue *Q) { /* 队头等于队尾，说明是空队列 */ if (Q->front == Q->rear) { return true; } else { return false; } } (3)入队 int equeue(Queue *Q, ElemType elem) { QueueNode *node = (QueueNode*)malloc(sizeof(QueueNode)); if(NULL == node) { perror("malloc Error: "); return -1; } //尾插法 node->data = elem; node->next = NULL; Q->rear->next = node; Q->rear = node; //移动队尾指针 } (4)出队 int dequeue(Queue *Q, ElemType *elem) { if(isEmpty(Q)) { printf("queue is empty\n"); return -1; } /* 删除头节点指向的节点 */ QueueNode *node = Q->front->next; *elem = node->data; Q->front->next = node->next; if (Q->rear == node) //如果是队尾，删完就就是空队列 { Q->rear = Q->front; } free(node); return 0; } (5)获取队头元素 int getHead(Queue *Q, ElemType *elem) { if(isEmpty(Q)) { printf("queue is empty\n"); return -1; } *elem = Q->front->next->data; return 0; } (6)完整代码 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> //链表结构队列 typedef int ElemType; typedef struct QueueNode { ElemType data; struct QueueNode *next; }QueueNode; typedef struct { QueueNode *front; //队头 QueueNode *rear; //队尾 }Queue; /***************************************************************** * 函数功能 : 初始化队列 * 参数 : void * 返回值 : 成功：Queue* 指针，失败：NULL ******************************************************************/ Queue* initQueue() { Queue *q = (Queue*)malloc(sizeof(Queue)); if(NULL == q) { perror("malloc Error: "); return NULL; } /* 头节点 */ QueueNode *node = (QueueNode*)malloc(sizeof(QueueNode)); if(NULL == node) { perror("malloc Error: "); free(q); q = NULL; return NULL; } node->data = 0; node->next = NULL; /* 队头、队尾都等于头节点 */ q->front = node; q->rear = node; return q; } /***************************************************************** * 函数功能 : 判断队列是否为空 * 参数 : Q(in):队列 * 返回值 : 空：true, 非空：false ******************************************************************/ bool isEmpty(Queue *Q) { /* 队头等于队尾，说明是空队列 */ if (Q->front == Q->rear) { return true; } else { return false; } } /***************************************************************** * 函数功能 : 入队 * 参数 : Q(in):队列 * 参数 : elem(in):入队元素 * 返回值 : 成功：0，失败：-1 ******************************************************************/ int equeue(Queue *Q, ElemType elem) { QueueNode *node = (QueueNode*)malloc(sizeof(QueueNode)); if(NULL == node) { perror("malloc Error: "); return -1; } //尾插法 node->data = elem; node->next = NULL; Q->rear->next = node; Q->rear = node; //移动队尾指针 } /***************************************************************** * 函数功能 : 出队 * 参数 : Q(in):队列 * 参数 : elem(out):出队元素 * 返回值 : 成功：0，失败：-1 ******************************************************************/ int dequeue(Queue *Q, ElemType *elem) { if(isEmpty(Q)) { printf("queue is empty\n"); return -1; } /* 删除头节点指向的节点 */ QueueNode *node = Q->front->next; *elem = node->data; Q->front->next = node->next; if (Q->rear == node) //如果是队尾，删完就就是空队列 { Q->rear = Q->front; } free(node); return 0; } /***************************************************************** * 函数功能 : 获取队头元素 * 参数 : Q(in):队列 * 参数 : elem(out):队列头元素 * 返回值 : 成功：0，失败：-1 ******************************************************************/ int getHead(Queue *Q, ElemType *elem) { if(isEmpty(Q)) { printf("queue is empty\n"); return -1; } *elem = Q->front->next->data; return 0; } int main(int argc, char const *argv[]) { //初始化队列 Queue *queue = initQueue(); //入队 equeue(queue, 10); equeue(queue, 20); equeue(queue, 30); //出队 ElemType elem; dequeue(queue, &elem); printf("dequeue: %d\n",elem); dequeue(queue, &elem); printf("dequeue: %d\n",elem); dequeue(queue, &elem); printf("dequeue: %d\n",elem); dequeue(queue, &elem); //已经空了 equeue(queue, 10); //获取队头 getHead(queue, &elem); printf("queue head:%d\n", elem); return 0; } 五、总结

队列是一种非常有用的数据结构，它在许多算法和程序设计中都有广泛的应用。