媒介
- 在上一篇博客中，我们详细探讨了栈这种数据结构，今天，让我们深入了解另一种与栈类似重要的数据结构 —— 队列。
一、队列的概念
- 队列只允许在一端举行插入数据操纵，在另一端举行删除数据操纵的特殊线性表。队列遵照先进先出的原则
- 入队列：举行插入操纵的一端称为队尾。
- 出队列：举行删除操纵的一端称为队头。
[/table]
实现简单，逻辑清晰；可直接通过索引随机访问元素，时间复杂度为 O (1)。
需预先确定队列大小。若队列元素超数组大小，扩容操纵复杂且耗时
可动态调整大小，无需预先确定队列长度；队头和队尾的插入、删除操纵时间复杂度为 O (1)
每个节点需额外存储指针，占用空间。
无法直接通过索引访问元素，随机访问服从低
| 今天我们来详细讲解一下基于链表实现的队列 [table] |
二、队列的操纵
（一）界说队列结构
- //定义队列结点的结构
- typedef struct QueueNode
- {
- QDataType data;
- struct QueueNode* next;
- }QueueNode;
- 队列结点结构中的data成员用于存储队列中的实际数据
- 接下来，我们界说队列结构体本身
- //定义队列的结构
- typedef struct Queue
- {
- QueueNode* phead; //队头
- QueueNode* ptail; //队尾
- }Queue;
- // 初始化队列
- void initQueue(Queue *pq) {
- pq->phead = NULL;
- pq->ptail = NULL;
- }
- 在使用队列之前，我们需要对其举行初始化操纵，将队头和队尾指针都设置为 NULL，表现队列为空。
- // 初始化队列
- void initQueue(Queue *pq) {
- pq->phead = NULL;
- pq->ptail = NULL;
- }
- // 入队操作
- void enqueue(Queue *pq, int x) {
- Node *newNode = (Node *)malloc(sizeof(Node));
- newNode->data = x;
- newNode->next = NULL;
- if (pq->ptail == NULL)
- {
- // 队列为空的情况
- pq->phead = newNode;
- pq->ptail = newNode;
- }
- else
- {
- pq->ptail->next = newNode;
- pq->ptail = newNode;
- }
- }
- 先创建一个新节点，给它分配内存空间，
- 把要入队的元素值赋给新节点的 data，并把 next 设为 NULL。
- 然后看队列是不是空的，如果空，新节点就既是队头又是队尾；
- 如果不空，就把新节点接到队尾节点背面，并更新队尾指针指向新节点
（四）出队列操纵
- //出队列
- int dequeue(Queue* pq)
- {
- assert(pq->phead != NULL);
- Node* temp = pq->phead;
- int x = temp->data;
- if (pq->phead == pq->ptail)
- {
- pq->phead = NULL;
- pq->ptail = NULL;
- }
- else
- {
- pq->phead = pq->phead->next;
- }
- free(temp);
- return x;
- }
- 从队列的队头取出一个元素并删掉对应的节点。
- 先检查队列不能是空的，然后把队头节点的数据存起来，
- 接着看队列是不是只有一个元素，
- 如果是就把队头和队尾指针都设为 NULL；
- 如果不止一个元素，就更新队头指针指向下一个节点，
- 末了释放原来队头节点的内存并返回取出的元素值。
（五）获取队头元素
- // 获取队头元素
- int front(Queue* pq)
- {
- assert(pq->phead != NULL);
- return pq->phead->data;
- }
- 能获取队列的队头元素的值，但不把这个元素从队列里取出来。
- 先得确保队列不是空的，然后直接返回队头节点的 data 值就行
（六）检查队列是否为空
- int isEmpty(Queue *pq)
- {
- return pq->front == NULL;
- }
- 如果是就说明队列为空，返回相应结果，如许在其他操纵前可以先检查下队列状态，避免在空队列上做无效操纵
（七）销毁队列
- // 释放队列内存
- void freeQueue(Queue* pq)
- {
- Node* current = pq->phead;
- Node* next;
- while (current != NULL)
- {
- next = current->next;
- free(current);
- current = next;
- }
- pq->phead = NULL;
- pq->ptail = NULL;
- }
- 在队列用完后用来释放它占用的内存资源。
- 从队头开始，逐个遍历队列里的节点，释放每个节点的内存，
- 末了把队头和队尾指针都设为 NULL，让队列回到初始的空状态
（三）本文所有代码
1.Queue.h文件
- #pragma once#include <stdio.h>#include <stdlib.h>#include <assert.h>// 链表节点结构体typedef struct Node { int data; struct Node* next;} Node;// 队列结构体typedef struct Queue { Node* phead; Node* ptail;} Queue;// 初始化队列void initQueue(Queue* pq) { pq->phead = NULL; pq->ptail = NULL;}//入队列void enqueue(Queue* pq, int x){ Node* newnode = (Node*)malloc(sizeof(Node)); newnode->data = x; newnode->next = NULL; if (pq == NULL) { pq->phead = newnode; pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; }}
- //出队列
- int dequeue(Queue* pq)
- {
- assert(pq->phead != NULL);
- Node* temp = pq->phead;
- int x = temp->data;
- if (pq->phead == pq->ptail)
- {
- pq->phead = NULL;
- pq->ptail = NULL;
- }
- else
- {
- pq->phead = pq->phead->next;
- }
- free(temp);
- return x;
- }
- // 获取队头元素
- int front(Queue* pq)
- {
- assert(pq->phead != NULL);
- return pq->phead->data;
- }
- // 检查队列是否为空int isEmpty(Queue* pq) { return (pq->phead != NULL) ? 0 : 1;}// 释放队列内存
- void freeQueue(Queue* pq)
- {
- Node* current = pq->phead;
- Node* next;
- while (current != NULL)
- {
- next = current->next;
- free(current);
- current = next;
- }
- pq->phead = NULL;
- pq->ptail = NULL;
- }
- #include "Queue.h"
- #include <stdio.h>
- int main() {
- Queue myQueue;
- initQueue(&myQueue);
- // 先输入一串数据来初始化队列
- int num;
- printf("请输入一串整数，以空格分隔，用于初始化队列，输入非整数结束输入：\n");
- // 逐个读取输入的数据并将其入队
- while (scanf_s("%d", &num) == 1) {
- enqueue(&myQueue, num);
- }
- // 清除输入缓冲区中的剩余字符（例如换行符等）
- while (getchar() != '\n');
- int choice, value;
- do {
- printf("请选择操作：\n");
- printf("1. 入队\n");
- printf("2. 出队\n");
- printf("3. 获取队头元素\n");
- printf("4. 检查队列是否为空\n");
- printf("5. 退出\n");
- scanf_s("%d", &choice);
- switch (choice) {
- case 1:
- printf("请输入要入队的值：");
- scanf_s("%d", &value);
- enqueue(&myQueue, value);
- break;
- case 2:
- if (!isEmpty(&myQueue)) {
- printf("出队元素: %d\n", dequeue(&myQueue));
- }
- else {
- printf("队列为空，无法出队\n");
- }
- break;
- case 3:
- if (!isEmpty(&myQueue)) {
- printf("当前队头元素: %d\n", front(&myQueue));
- }
- else {
- printf("队列为空，无队头元素\n");
- }
- break;
- case 4:
- if (isEmpty(&myQueue)) {
- printf("队列为空\n");
- }
- else {
- printf("队列不为空\n");
- }
- break;
- case 5:
- printf("退出程序\n");
- break;
- default:
- printf("无效的选择，请重新输入\n");
- }
- } while (choice != 5);
- // 释放队列内存
- freeQueue(&myQueue);
- return 0;
- }
|
