队列的介绍
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。队列具有先进先出的特点：进行插入操作的一端称为队尾，进行删除操作的一端称为队头。
文件分装
对应文件的代码
queue.h
#pragma once //头文件的声明 #include<stdio.h> #include<stdlib.h> #include<assert.h> //节点存储的数据类型 typedef int QDataType; // 链式结构：表示队列 typedef struct QListNode { struct QListNode* _pnext; QDataType _data; }QNode; // 队列的结构 typedef struct Queue { QNode* _head; QNode* _tail; }Queue; // 初始化队列 void QueueInit(Queue* q); // 队尾入队列 void QueuePush(Queue* q, QDataType data); // 队头出队列 void QueuePop(Queue* q); // 获取队列头部元素 QDataType QueueFront(Queue* q); // 获取队列队尾元素 QDataType QueueBack(Queue* q); // 获取队列中有效元素个数 int QueueSize(Queue* q); // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q); // 销毁队列 void QueueDestroy(Queue* q);
queue.c
#include"queue.h" // 初始化队列 void QueueInit(Queue* q) { //断言，保证指针的有效性 assert(q); //把指向第一个和最后一个节点的指针初始化为NULL q->_head = q->_tail = NULL; } // 队尾入队列 void QueuePush(Queue* q, QDataType data) { assert(q); //新开辟一个新的节点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); //对新的节点初始化 newnode->_data = data; newnode->_pnext = NULL; //1.队列没有节点的情况 if (q->_tail == NULL) { q->_head = q->_tail = newnode; } else//2.队列已经有节点的情况 { q->_tail->_pnext = newnode; q->_tail = newnode; } } // 队头出队列 void QueuePop(Queue* q) { assert(q); //1.队列只有一个节点的情况 //释放了空间后还要把原来指向第一个和最后一个节点的指针置为NULL if (q->_head->_pnext == NULL) { free(q->_head); q->_head = q->_tail = NULL; } //2.队列至少一个节点的情况 else { //释放第一个节点前要保留第二个节点的地址 QNode* next = q->_head->_pnext; //释放第一个节点 free(q->_head); //之前的第二个节点变为第一个节点 q->_head = next; } } // 获取队列头部元素 QDataType QueueFront(Queue* q) { assert(q); return q->_head->_data; } // 获取队列队尾元素 QDataType QueueBack(Queue* q) { assert(q); return q->_tail->_data; } // 获取队列中有效元素个数 int QueueSize(Queue* q) { assert(q); QNode* cur = q->_head; int n = 0; //遍历队列 while (cur) { n++; cur = cur->_pnext; } return n; } // 检测队列是否为空，如果为空返回1，如果非空返回0 int QueueEmpty(Queue* q) { assert(q); return q->_head == NULL ? 1 : 0; } // 销毁队列 void QueueDestroy(Queue* q) { assert(q); QNode* cur = q->_head; //遍历队列 while (cur) { //销毁之前保留后一个节点的地址 QNode* next = cur->_pnext; free(cur); cur = next; } //防止野指针 q->_head = q->_tail = NULL; }
trest.c
#include"queue.h" int main() { //测试 Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } return 0; }
