[数据结构]队列

1.队列的概念及结构

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

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

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

2.队列的实现

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

以下是队列的创建:

空队列:

空队列插入第一个元素:

入队列和出队列

接下来是代码实现,这里我还是选用比较容易实现的链表来实现队列,个人认为类似单链表.

代码示例:

//Queue.h#pragma once#include#include#include#includetypedef int QDataType;typedef struct QueueNode{int val;struct QueueNode* next;}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);bool QueueEmpty(Queue* pq);int QueueSize(Queue* pq);

//Queue.c#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->val = x;newnode->next = NULL;if (pq->ptail){pq->ptail->next = newnode;pq->ptail = newnode;}else{pq->phead = pq->ptail = newnode;}pq->size++;}// 出队列void QueuePop(Queue* pq){assert(pq);assert(pq->phead != NULL);if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;}QDataType QueueFront(Queue* pq){assert(pq);// 暴力检查 assert(pq->phead != NULL);return pq->phead->val;}QDataType QueueBack(Queue* pq){assert(pq);// 暴力检查 assert(pq->ptail != NULL);return pq->ptail->val;}bool QueueEmpty(Queue* pq){assert(pq);return pq->size == 0;}int QueueSize(Queue* pq){assert(pq);return pq->size;}

#include"Queue.h"int main(){Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);printf("%d ", QueueFront(&q));QueuePop(&q);QueuePush(&q, 3);QueuePush(&q, 4);while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}QueueDestroy(&q);return 0;}

运行结果: