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;// 初始化队列的头指针和尾指针为NUL
	pq->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;// 将队列的头指针和尾指针置为NUL
	pq->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;// 将新节点的指针域置为NULL

	if (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)// 如果队列为空，则将尾指针也置为NULL
		pq->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 设计循环队列。