文章目录

  • 前言
  • 一、队列基本变量的了解
  • 二、队列的基本操作
    • 2.1队列的初始化（QueueInit）
    • 2.2入队（QueuePush）
    • 2.3判断是否为空队（QueueEmpty）
    • 2.4出队（QueuePop）
    • 2.5队列的队头数据（QueueFront）
    • 2.6队列的队尾数据（QueueBack）
    • 2.7队列大小（QueueSize）
    • 2.8队列的销毁（QueueDestroy）

前言

提示：以下是本篇文章正文内容，下面案例可供参考
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头

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

一、队列基本变量的了解

typedef int QDataType;//队列数据类型typedef struct QueueNode {QDataType data;//数据域struct QueueNode* next;//指针域}QNode;//先建立一个结点typedef struct Queue {QNode* head;//头QNode* tail;//尾int size;//队列数量}Queue;//将头与尾还有数量封装在一起能更好操作

二、队列的基本操作

2.1队列的初始化（QueueInit）

void QueueInit(Queue* pq) {assert(pq);pq->head = pq->tail = NULL;//刚开始没有数据，所以头尾都为NULLpq->size = 0;//数量}

2.2入队（QueuePush）

void QueuePush(Queue* pq,QDataType x) {assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL) {perror("malloc error");return;}//判断是否为有效空间newnode->data = x;newnode->next = NULL;//初始化新结点if (pq->head == NULL) {assert(!pq->tail);pq->head = pq->tail = newnode;//之所以要分开判断是因为//我们也要保证只有一个数据时//head与tail指向同一个//如果只有else虽然也能够正常插入//但是tail一直指向NULL}else {pq->tail->next = newnode;//在尾巴后面接上也就是入队pq->tail = pq->tail->next;//尾巴改变，指向新加入的数据}pq->size++;//数据+1}

2.3判断是否为空队（QueueEmpty）

bool QueueEmpty(Queue* pq) {assert(pq);return pq->size==0;//数量为0返回为真，真为空，假为不空}

2.4出队（QueuePop）

void QueuePop(Queue* pq) {assert(pq);assert(!QueueEmpty(pq)); if (pq->head->next == NULL) {free(pq->head);//只有一个元素//直接将尾巴与头置空pq->head = pq->tail = NULL;}else {QNode* Next = pq->head->next;//记录队头下一个结点free(pq->head);//释放队头pq->head = Next;//队头指向下一个位置}pq->size--;//数量减少}

2.5队列的队头数据（QueueFront）

QDataType QueueFront(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));//判断是否为空队列return pq->head->data;//直接去队头数据}

2.6队列的队尾数据（QueueBack）

QDataType QueueBack(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));//判断是否为空队列return pq->tail->data;}

2.7队列大小（QueueSize）

int QueueSize(Queue* pq) {assert(pq);return pq->size;}

2.8队列的销毁（QueueDestroy）

void QueueDestroy(Queue* pq) {assert(pq);QNode* cur = pq->head;//记录当前结点while (cur) {QNode* Next = cur->next;//当前结点的下一个结点free(cur);//释放当前节点cur = Next;//让当前结点指向下一个结点}pq->head = pq->tail = NULL;//最后头尾都NULLpq->size = 0;}