🌟一、队列的概念及结构：
队列:只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，***队列具有先进先出FIFO(First In First Out)***
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头
🌟二、队列实现的两种方式：
数组队列
链式队列
🌟三、队列的实现：
🌏3.1队列结构：
需要定义两个结构体，一个是整个队列中每个节点的结构一个是队头指针、队尾指针和数据个数
typedef int QDataType; typedef struct QUeueNode//每个节点的结构 { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; //初始化 void QueueInit(Queue*pq); //释放 void QueueDestroy(Queue* pq); //尾插(入队) void QueuePush(Queue* pq,QDataType x); //头删(出队) void QueuePop(Queue* pq); //队头数据 QDataType QueueFront(Queue* pq); //队尾数据 QDataType QueueBack(Queue* pq); //数据个数 int QueueSize(Queue* pq); //判空 bool QueueEmpty(Queue* pq);
🌏3.2初始化：
void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; }
🌏3.3释放(类似单链表)：
💫3.3.1代码：
void QueueDestroy(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; }
💫3.3.2流程图：
🌏3.4入队(类似单链表尾插)：
💫3.4.1代码：
void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; if (pq->ptail == NULL) { assert(pq->phead==NULL); pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; }
💫3.4.2流程图：
🌏3.5出队(类似单链表头删)：
💫3.5.1代码：
void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq));//这里是判断pq->phead不为空 //一个队列 if (pq->phead->next == NULL) { free(pq->phead); pq->phead = NULL; pq->ptail = NULL; } //多个队列 else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; }
💫3.5.2流程图：
🌏3.6队头数据：
QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->phead->data; }
🌏3.7队尾数据：
QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->ptail->data; }
🌏3.8数据个数：
int QueueSize(Queue* pq) { assert(pq); return pq->size; }
🌏3.9判空：
bool QueueEmpty(Queue* pq) { assert(pq); return pq->size==0; }
🌟四、完整代码：
//Queue.h #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<assert.h> #include<stdbool.h> #include<stdlib.h> typedef int QDataType; typedef struct QUeueNode//每个节点的结构 { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; //初始化 void QueueInit(Queue*pq); //释放 void QueueDestroy(Queue* pq); //尾插(入队) void QueuePush(Queue* pq,QDataType x); //头删(出队) void QueuePop(Queue* pq); //队头数据 QDataType QueueFront(Queue* pq); //队尾数据 QDataType QueueBack(Queue* pq); //数据个数 int QueueSize(Queue* pq); //判空 bool QueueEmpty(Queue* pq); //Queue.c #define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; } void QueueDestroy(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 QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; if (pq->ptail == NULL) { assert(pq->phead==NULL); pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); //一个队列 if (pq->phead->next == NULL) { free(pq->phead); pq->phead = NULL; pq->ptail = NULL; } //多个队列 else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; } QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->phead->data; } QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->ptail->data; } int QueueSize(Queue* pq) { assert(pq); return pq->size; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->size==0; } //Test.c #define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" void TestQueue() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } printf("\n"); QueueDestroy(&q); } int main() { TestQueue(); return 0; }
😽总结
😽Ending,今天的栈和队列(下)的内容就到此结束啦~，如果后续想了解更多，就请关注我吧。
