1.队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)
- 入队列：进行插入操作的一端称为队尾
- 出队列：进行删除操作的一端称为队头
2.队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数 组头上出数据，效率会比较低。
我们可以用单链表来实现：
2.1创建一个队列
先创建一个结构体封装数据之间的关系
再创建一个结构体封装队列的头和尾
2.2初始化
2.3销毁
2.4入队列
2.5出队列
2.6取队列头数据
2.7取队列尾数据
2.8判空
2.9返回队列有效元素个数
2.10访问
当队列不为空的时候，访问队头数据，访问一个pop一个
3.总代码
Queue.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> //创建 typedef int QDataType; typedef struct QueueNode { QDataType val; struct QueueNode* next; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; //把队列的头尾封装在一个结构体中 //初始化 void QInit(Queue* pq); //销毁 void QDestroy(Queue* pq); //入队列 void QPush(Queue* pq, QDataType x); //出队列 void QPop(Queue* pq); //取队头数据 QDataType QFront(Queue* pq); //取队尾数据 QDataType QBack(Queue* pq); //判空 bool QEmpty(Queue* pq); //返回队列有效元素个数 int QSize(Queue* pq);
Queue.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" //初始化 void QInit(Queue* pq) { assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; } //销毁 void QDestroy(Queue* pq) { assert(pq); QNode* cur = pq->phead; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; } //入队列 void QPush(Queue* pq, QDataType x) { assert(pq); //创建newnode QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->val = x; newnode->next = NULL; if (pq->ptail == NULL) { pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } //出队列 void QPop(Queue* pq) { assert(pq); assert(pq->phead); QNode* del = pq->phead; pq->phead = pq->phead->next; free(del); del = NULL; if (pq->phead == NULL) { pq->ptail = NULL; //防止ptail成为野指针 } pq->size--; } //取队头数据 QDataType QFront(Queue* pq) { assert(pq); assert(pq->phead); return pq->phead->val; } //取队尾数据 QDataType QBack(Queue* pq) { assert(pq); assert(pq->ptail); return pq->ptail->val; } //判空 bool QEmpty(Queue* pq) { assert(pq); return pq->phead == NULL; } //返回队列有效元素个数 int QSize(Queue* pq) { assert(pq); return pq->size; }
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" int main() { Queue Q; QInit(&Q); QPush(&Q, 1); QPush(&Q, 2); QPush(&Q, 3); QPush(&Q, 4); QPush(&Q, 5); int size = QSize(&Q); printf("%d\n", size); while (!QEmpty(&Q)) { printf("%d ", QFront(&Q)); QPop(&Q); } QDestroy(&Q); return 0; }
