队列的实现

概念与结构

概念：只允许在⼀端进行插入数据操作，在另⼀端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)。

入队列：进行插入操作的⼀端称为队尾。

出队列：进行删除操作的⼀端称为队头。

队列底层结构选型

队列也可以数组和链表的结构实现，使用链表的结构实现更优⼀些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

队列的代码实现：

Queue.h #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int QDataType; typedef struct QueueNode {     QDataType data;     struct QueueNode* next; }QueueNode; typedef struct Queue {     QueueNode* phead;     QueueNode* ptail;     int size; }Queue; void QueuePrint(Queue* pq); void QueueInit(Queue* pq); //尾插 void QueueBush(Queue* pq, QDataType x); bool QueueEmpty(Queue* pq); void QueuePop(Queue* pq); QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); int QueueSize(Queue* pq); void QueueDestroy(Queue* pq);

Queue.c #define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" void QueueInit(Queue* pq) {     assert(pq);     pq->phead = pq->ptail = NULL;     pq->size = 0; } void QueueBush(Queue* pq, QDataType x) {     assert(pq);     QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));     if (newnode == NULL)     {         perror("malloc fail!");         exit(1);     }     newnode->data = x;     newnode->next = NULL;     if (pq->phead == NULL)     {         pq->phead = pq->ptail = newnode;     }     else     {         pq->ptail->next = newnode;         pq->ptail = pq->ptail->next;     }     pq->size++; } void QueuePrint(Queue*pq) {     while (pq->ptail)     {         printf("%d->", pq->ptail->data);         pq->ptail = pq->ptail->next;     } } bool QueueEmpty(Queue* pq) {     assert(pq);     return pq->phead == NULL && pq->ptail == NULL; } void QueuePop(Queue* pq) {     assert(pq);     assert(!QueueEmpty(pq));     if (pq->phead == pq->ptail)     {         free(pq->phead);         pq->phead = pq->ptail = NULL;     }     else     {         QueueNode* 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; } void QueueDestroy(Queue* pq) {     assert(pq);     assert(!QueueEmpty(pq));     QueueNode* pcur = pq->phead;     while (pcur)     {         QueueNode* next = pcur->next;         free(pcur);         pcur = next;     }     pq->phead = pq->ptail = NULL;     pq->size = 0; }

 text.c #define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" void QueueText01() {     Queue q;     QueueInit(&q);     QueueBush(&q, 1);     QueueBush(&q, 2);     QueueBush(&q, 3);     QueueBush(&q, 4);     //QueuePop(&q);     //QueuePop(&q);     //QueuePop(&q);     //QueuePrint(&q);     //QueuePop(&q);     //QueuePrint(&q); } int main() {     QueueText01();     return 0; }