💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 ：阿然成长日记 👈点击可跳转
🚩 不能则学，不知则问，耻于问人，决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍
文章目录
一、队列的定义：
一、队列的基本概念
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列是一种先进先出 （First In FirstOut）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头
二、链式结构队列的模拟实现
1.结构图;
使用单向链表
初始状态:（队空条件）：Q->front == Q->rear == 0。
进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。
出队操作：队不空时，先取队头元素值，再将队头指针加1。
2.队列的结构体
在这里我使用的是单链表的形式来模拟队列。
//定义data数据类型 typedef int QueueDataType; //定义节点 typedef struct QueueNode { struct QueueNode* next; QueueDataType data; }QNode; //定义队列 typedef struct QueueList { //头指针 QNode* head; //尾指针 QNode* tail; //链表长度 int size; }QList;
3.初始化
这里没有设置头节点，初始化时，两个指针都指向空。
//初始化 void QueueInit(QList* p) { assert(p); p->head = p->tail = NULL; p->size = 0; }
4.销毁队列
需要注意 由于动态分配的内存空间 ，在使用完队列之后，要把申请的空间及时的释放掉。具体做法就是遍历单链表，释放每一个节点。的遍历每一个节点，并对节点进行释放
//销毁队列 void QueueDestroy(QList* p) { assert(p); QNode* cur = p->head; while (cur) { QNode* next = cur->next; free(cur); cur = cur->next; } p->head = p->tail = NULL; p->size = 0; }
5.入队（尾插）
注意为空时的插入，与存在节点时，分情况讨论
//入队（尾插） void QueuePush(QList* p, QueueDataType x) { assert(p); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail\n"); exit(-1); } newnode->data = x; newnode->next = NULL; if (p->head == NULL) { p->head = p->tail = newnode; } else { p->tail->next = newnode; p->tail = p->tail->next; } p->size++; }
6.出队（头删）
//出队（头删） void QueuePop(QList* p) { assert(p); assert(!IsEmpty(p)); //当只有一个节点时 if (p->head->next == NULL) { free(p->head); p->head = p->tail = NULL; } //当有两个或两个以上节点 else { QNode* phead = p->head->next; free(p->head); p->head->next = phead; } p->size--; }
7.获取队头
//获取队头 QueueDataType QueueHead(QList* p) { assert(p); assert(!IsEmpty(p)); return p->head->data; }
8.获取队尾
//获取队尾 QueueDataType QueueTail(QList* p) { assert(p); assert(!IsEmpty(p)); return p->tail->data; }
9.判断是否为空
//判断是否为空 bool IsEmpty(QList* p) { assert(p); return p->head == NULL; }
9.判断是否为空
//判断是否为空 bool IsEmpty(QList* p) { assert(p); return p->head == NULL; }
10.获取队列长度
//获取队列长度 int QueueSize(QList* p) { return p->size; }
