06.【数据结构-C语言】队列（先进先出，队列实现：入队列、出队列、获取队头or队尾元素，队列实现代码，队列相关题目）

目录

1. 队列的概念及结构

2. 队列的实现（链表）

2.1 队列的实现方式

2.2 队列结构体声明

2.3 初始化&销毁

2.4 入队列（尾插）

2.5 出队列（头删）

2.6 取队头&取队尾

2.7 判空

2.8 获取队列元素个数

3. 队列实现完整版代码

4. 队列相关题目

---

1. 队列的概念及结构

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

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

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

2. 队列的实现（链表）

2.1 队列的实现方式

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

2.2 队列结构体声明

        队列声明和单链表类似，新增一个队列结构体，用来保存队列的头、尾、大小。

        新增结构体作用：1.方便取队头和队尾数据；2.避免二级指针的调用，更容易理解。

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;	// 队列节点的指针QDataType val;	// 队列节点val
}QNode;typedef struct Queue
{QNode* phead;	// 队列头QNode* ptail;	// 队列尾int size;		// 队列大小
}Queue;

2.3 初始化&销毁

        销毁和单链表销毁相同。

// 初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}
// 销毁
void QueueDestory(Queue* pq)
{assert(pq);while (pq->phead){QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

2.4 入队列（尾插）

        对phead和ptail的修改，在phead为空和不为空时不同。

// 尾插
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL){perror("malloc");return;}newNode->next = NULL;newNode->val = x;if(pq->phead == NULL){pq->phead = newNode;pq->ptail = newNode;}else{pq->ptail->next = newNode;pq->ptail = pq->ptail->next;}pq->size++;
}

2.5 出队列（头删）

        只剩一个节点时要同时对phead和ptail修改。

// 头删
void QueuePop(Queue* pq)
{assert(pq && pq->size > 0);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--;
}

2.6 取队头&取队尾

        判断队列是否为空，不为空再进行取队头or队尾操作。

// 取队头
QDataType QueueFront(Queue* pq)
{assert(pq && pq->size > 0);return pq->phead->val;
}
// 取队尾
QDataType QueueBack(Queue* pq)
{assert(pq && pq->size > 0);return pq->ptail->val;
}

2.7 判空

// 队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

2.8 获取队列元素个数

// 队列大小
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

3. 队列实现完整版代码

        【免费】队列-C语言实现完整版代码资源-CSDN下载

4. 队列相关题目

        1. 用两个队列实现栈。（push进非空队列，pop时导数据剩最后一个直接pop掉，此时空队列和非空队列互换）225. 用队列实现栈 - 力扣（LeetCode）

        2. 用两个栈实现队列。（一个push栈，一个pop栈）232. 用栈实现队列 - 力扣（LeetCode）

        3. 循环队列。（数组 & 链表：方法1.多开一个空间，区分满和空；方法2.使用size判断满和空）622. 设计循环队列 - 力扣（LeetCode）