【数据结构和算法初阶(C语言)】队列实操（概念实现+oj题目栈和队列的双向实现，超级经典！！！）

news/2024/7/27 11:58:22/文章来源:https://blog.csdn.net/m0_71503225/article/details/136651799

1. 队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，

队列具有先进先出 FIFO(First In First Out)

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

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

2.队列结构存在的意义

①公平排队

比如医院或者银行的排号

②BFSL广度优先

3.队列实现的结构选择

数组和链表都可以实现队列，但是链表的头插尾插，头删尾删要方便些，所以首选链表

单向还是双向：选择单向，双向的优势是方便找前一个1节点，没有这个需求。（找尾不是因为双向，双向循环方便找尾）

是否需要带哨兵位的链表：哨兵位是为了解决二级指针（可以将头尾指针封装为结构体进行传参，这样就可以改变真实的指针了，所以哨兵位可要可不要），尾插少一次判断。

选择单向不循环链表即可实现。

4.队列实现

typedef  int QdataType;typedef struct QListNode
{struct QListNode* next;QdataType data;
}QNode;//将头尾指针封装为一个结构体，解决传递二级指针的问题typedef struct Queue
{QNode* head;QNode* tail;int size;//保存链表的大小
}Queue;

5.队列对数据的处理

5.1队列初始化

void QUeueInit(Queue* pq)//初始化队列
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}

5.2队尾入数据

void QueuePush(Queue* pq, QdataType x)//队列增加数据
{assert(pq);//首先传入的这个结构体要存在//申请到节点来创建QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc");}//新节点初始化newnode->data = x;newnode->next = NULL;//准备插入，看一下是不是第一次插入if (pq->tail == NULL){pq->head = pq->tail = newnode;pq->size++;}else{pq->tail->next = newnode;pq->tail = pq->tail->next;pq->size++;}
}

5.3队头出数据

void QueuepPop(Queue* pq, QdataType x)//队列删除元素
{assert(pq);assert(pq->size != 0);if (pq->head->next == NULL)//因为不是带哨兵位的，删除到最后一个位置防止尾指针成为野指针，单独处理{free(pq->head);pq->head = pq->tail = NULL;pq->size--;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;pq->size--;}}

5.4获取队列尾部元素

QdataType QueueBack(Queue* pq)//获取队列前后面元素
{assert(pq);assert(!QueueEmpty);return pq->tail->data;
}

5.5获取队列头部元素

QdataType QueueFront(Queue* pq)//获取队列前面元素
{assert(pq);assert(!QueueEmpty);return pq->head->data;
}

5.6获取队列中元素个数

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

5.7检测队列是否为空

bool QueueEmpty(Queue* pq)//检测队列是否为空
{assert(pq);return pq->head == NULL;
}

5.8销毁队列

void QueueDestory(Queue* pq)//销毁队列
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = cur->next;}pq->head = pq->tail = NULL;pq->size = 0;
}