一.队列是什么？🧐🧐🧐
和栈相反，队列( queue)是一种先进先出( First In First Out, FIFO) 的线性表。它只允许在表的一端进行插人，而在另一端删除元素。这和日常生活中的排队是一致的， 最早进入队列的元素最早离开。在队列中，允许插入的一端称为队尾( rear)，允许删除的一端则称为队 头( front) 。假设队列为q=(a1,a2, .,an)，那么，a就是队头元素， a,则是队尾元素。队列中的元素是按照a, a, … a,的顺序进人的，退出队列也只能按照这个次序依次退出，也就是说，只有在a,a., an，都离开队列之后，a,才能退出队列。
二、队列与线性表的关系🆚🆚🆚
与栈一样队列也是一种重要的线性结构。从数据结构角度看，队列也是线性表，其特殊性在于队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可称为具有限定性的数据结构。但从数据类型角度看，它是和线性表不相同的两类重要的抽象数据类型。
三、队列的基本操作🔬🔬🔬
1.队列的储存结构结构💻
typedef struct Qnode { Elemtype data; struct Qnode* next; }QNode, * QueuePrt;//建立链表 typedef struct { QueuePrt front; QueuePrt rear;//指向头和尾的两个指针 }LinkQueue;//建立队列
2.队列的初始化✨
InitQueue(LinkQueue* q) { q->front = q->rear = (QueuePrt)malloc(sizeof(QNode));//创建头结点 if (!q->front) exit(0); q->front->next = NULL; }//初始队列
其实就是链表中的创建头结点
3. 入队🚗
InsertQueue(LinkQueue *q, Elemtype e) { QueuePrt p; p = (QueuePrt)malloc(sizeof(QNode));//创建结点 if (p == NULL) exit(0); p->data = e;//赋值 p->next = NULL;// q->rear->next = p;//头指针指向下一个结点 q->rear = p; }
4.出队🚅
DeletQueue(LinkQueue* q, Elemtype* e) { QueuePrt p; if (q->front == q->rear) return 0; *e = p->data; q->front->next = p->next; if (q->rear == p) q->rear = q->front; free(p); }
5.清空与销毁🆘
DesteoyQueue(LinkQueue* q) { while (q->rear = q->front->next) { free(q->front); q->front = q->rear; } }
总结🎆🎆🎆
队列是一种先进先出的线性表。它只允许在表的一端进行插人， 而在另一端进行删除。队列也有两种存储表示，顺序表示(循环队列)和链式表示( 链队)。队列的主要操作是进队和出队，对于顺序表示的循环队列的进队和出队操作要注意判断队满或队空。凡是涉及队头或队尾指针的修改都要将其对MAXQSIZE求模。
#include<stdio.h> #include<stdlib.h> typedef int Elemtype;//定义类型 typedef struct Qnode { Elemtype data; struct Qnode* next; }QNode, * QueuePrt;//建立链表 typedef struct { QueuePrt front; QueuePrt rear;//指向头和尾的两个指针 }LinkQueue;//建立队列 InitQueue(LinkQueue* q) { q->front = q->rear = (QueuePrt)malloc(sizeof(QNode));//创建头结点 if (!q->front) exit(0); q->front->next = NULL; }//初始队列 InsertQueue(LinkQueue *q, Elemtype e) { QueuePrt p; p = (QueuePrt)malloc(sizeof(QNode));//创建结点 if (p == NULL) exit(0); p->data = e;//赋值 p->next = NULL;// q->rear->next = p;//头指针指向下一个结点 q->rear = p; } DeletQueue(LinkQueue* q, Elemtype* e) { QueuePrt p; if (q->front == q->rear) return 0; *e = p->data; q->front->next = p->next; if (q->rear == p) q->rear = q->front; free(p); } DesteoyQueue(LinkQueue* q) { while (q->rear = q->front->next) { free(q->front); q->front = q->rear; } }
