初阶数据结构（C语言实现）——4.2队列

2.队列

2.1队列的概念及结构

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

2.2队列的实现

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

• 队列结构

// 链式结构：表示队列
typedef struct QListNode
{ struct QListNode* _pNext; QDataType _data; 
}QNode; 
// 队列的结构
typedef struct Queue
{ QNode* _front; QNode* _rear; 
}Queue; 

• 队列接口

// 初始化队列
void QueueInit(Queue* q); 
// 队尾入队列
void QueuePush(Queue* q, QDataType data); 
// 队头出队列
void QueuePop(Queue* q); 
// 获取队列头部元素
QDataType QueueFront(Queue* q); 
// 获取队列队尾元素
QDataType QueueBack(Queue* q); 
// 获取队列中有效元素个数
int QueueSize(Queue* q); 
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q); 
// 销毁队列
void QueueDestroy(Queue* q);

• 在VS2022中新建一个工程

Queue20250310.h（队列的类型定义、接口函数声明、引用的头文件）
Queue20250310.c（队列的接口函数的实现）
QueueTest20250310.c（主函数、测试各个接口功能）

2.2.1 初始化队列

// 初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;// 初始化队列的头指针和尾指针为NULpq->size = 0; // 初始化队列的大小为0
}

2.2.2 销毁队列

// 销毁队列
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;// 将队列的头指针和尾指针置为NULpq->size = 0;//将队列的大小置为0
}

2.2.3 队尾入队列

// 队尾入队列
void QueuePush(Queue* pq, QDataType data)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("QueueDestroy::malloc fail!");return;}newnode->data = data;// 将数据存入新节点newnode->next = NULL;// 将新节点的指针域置为NULLif (pq->head == NULL)// 如果队列为空，则新节点即为队列的头指针和尾指针{assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else //如果队列不为空，则将新节点插入到队列的尾部{//尾插pq->tail->next = newnode;pq->tail = newnode;}pq->size++;// 队列的大小加1
}

2.2.4 队头出队列

// 队头出队列
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head==NULL);QNode* next = pq->head->next;                                                                                                                                                                                                                                                          free(pq->head); // 释放原头节点的内存空间pq->head = next;if (pq->head == NULL)// 如果队列为空，则将尾指针也置为NULLpq->tail = NULL;pq->size--;
}

2.2.5获取队列头部元素

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

2.2.6 获取队列队尾元素

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

2.2.7获取队列中有效元素个数

// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

2.2.8 检测队列是否为空，如果为空返回非零结果，如果非空返回0

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;// 如果队列的头指针为NULL，则队列为空
}

3.栈和队列面试题

3.1 括号匹配问题。

括号匹配问题

3.2用队列实现栈。

用队列实现栈

3.3 用栈实现队列。

3.4 设计循环队列。