队列的结构概念和实现

一、队列的结构和概念

什么是队列？
队列就是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出

如上图所示，第一个人先来，排在第一位就可以第一个走，也叫先进先出
但是想要近来就只能排队在后面等候

二、队列的实现

队列和栈一样都可以用链表和数组实现，但是对于队列来说，链表更好，因为用数组在对头出数据的话效率太低。

三、队列的实现函数

• 1.队列的初始化

void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;}

• 2.队列的销毁
  `

void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* cur = pq->phead;while (cur){cur = pq->phead->next;free(pq->phead);pq->phead = cur;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

链表的销毁需要一个一个节点的销毁，无法直接销毁

• 3.队列的判空

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

• 4.队列的插入

void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail");return;}newnode->val = x;newnode->next = NULL;if (pq->ptail){pq->ptail->next= newnode;pq->ptail = newnode;}else{pq->phead = pq->ptail = newnode;}pq->size++;
}

每一个节点的开辟用malloc就行，这点与数组不一样，数组是realloc扩容

• 5.队列的删除

void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead!=NULL);if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;}

• 6.取队列的头

QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;}

• 7.取队列的尾巴

QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}

• 8.队列的长度

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

四、队列的思维导图

先赞后看，养成习惯！！！^ _ ^<3 ❤️ ❤️ ❤️
码字不易，大家的支持就是我坚持下去的动力。点赞后不要忘了关注我哦！

如有错误请您指正批评!