数据结构——队列

typedef int QDataType;
 
//队列节点
typedef struct QueueNode {
	QDataType data;
	struct QueueNode* next;
}QNode;
 
//队列结构
typedef struct Queue {
	QNode* phead;//头节点
	QNode* ptail;//尾节点
	int sz;
}Queue;
 
//初始化队列
void QueueInit(Queue* pq);
 
//入队列(队尾)
void QueuePush(Queue* pq,QDataType x);
 
//出队列(队头)
void QueuePop(Queue* pq);
 
//获取队列头部元素
QDataType QueueFront(Queue* pq);
 
//获取队列尾部元素
QDataType QueueBack(Queue* pq);
 
//获取队列有效元素个数
int QueueSize(Queue* pq);
 
//判断队列是否为空
bool QueueEmpty(Queue* pq);
 
//销毁队列
void QueueDestroy(Queue* pq);

2.1 队列结构

由于我们用链表来实现队列，为了更好的完成队列操作，我们定义了一个结构体来表示队列的队头和队尾。

//队列结构
typedef struct Queue {
	QNode* phead;//头节点
	QNode* ptail;//尾节点
	int sz;
}Queue;

2.2 队列的初始化

void QueueInit(Queue* pq) {
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->sz = 0;
}

我们把队列的头和尾都置为空，队长置为零。

2.4 入队列

void QueuePush(Queue* pq, QDataType x) {
	assert(pq);
 
	//创建新节点
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
	}
	newNode->data = x;
	newNode->next = NULL;
 
    //从队尾插入
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newNode;
	}
	else
	{
		pq->ptail->next= newNode;
		pq->ptail = newNode;
	}
	
	//长度加一
	pq->sz++;
 
}

我们先创建要插入的新的节点，然后从队列的队尾插入(即链表的尾插)，最后队列长度加一。

2.5 出队列

void QueuePop(Queue* pq) {
	assert(pq);
	assert(pq->phead != NULL);//队列不为空
 
 
	if (pq->phead == pq->ptail)
	{
		free(pq->ptail);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;;
		free(pq->phead);
		pq->phead = next;
	}
	pq->sz--;
}

出队列从队头开始出去，但是我们这里需要分成两种情况讨论，第一种就是队列只有一个元素，我们要把头尾同时置为空，不然有野指针出现。第二种就是链表的头删操作。

2.6 获取队列尾部元素

QDataType QueueBack(Queue* pq) {
	assert(pq);
	assert(pq->phead != NULL);
 
	return pq->ptail->data;
}

我们先判断队列是否为空，然后直接返回尾部节点元素即可。

2.7 获取队列头部元素

QDataType QueueFront(Queue* pq) {
	assert(pq);
	assert(pq->phead != NULL);
 
	return pq->phead->data;
 
 
}

我们先判断队列是否为空，然后直接返回头部节点元素即可。

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

2.9 判断队列是否为空

bool QueueEmpty(Queue* pq) {
 
	assert(pq);
 
	return pq->phead == NULL;
 
}

直接返回，如果头节点等于空，即返回true，反之返回false。

2.10 销毁队列

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->sz = 0;
}

和链表销毁差不多，我们要依次销毁每一个创建的节点。

三、完整代码实现

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
 
typedef int QDataType;
 
//队列节点
typedef struct QueueNode {
	QDataType data;
	struct QueueNode* next;
}QNode;
 
//队列结构
typedef struct Queue {
	QNode* phead;//头节点
	QNode* ptail;//尾节点
	int sz;
}Queue;
 
//初始化队列
void QueueInit(Queue* pq);
 
//入队列(队尾)
void QueuePush(Queue* pq,QDataType x);
 
//出队列(队头)
void QueuePop(Queue* pq);
 
//获取队列头部元素
QDataType QueueFront(Queue* pq);
 
//获取队列尾部元素
QDataType QueueBack(Queue* pq);
 
//获取队列有效元素个数
int QueueSize(Queue* pq);
 
//判断队列是否为空
bool QueueEmpty(Queue* pq);
 
//销毁队列
void QueueDestroy(Queue* pq);

Queue.c

#include"Queue.h"
 
//初始化队列
void QueueInit(Queue* pq) {
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->sz = 0;
}
 
//入队列(队尾)
void QueuePush(Queue* pq, QDataType x) {
	assert(pq);
 
	//创建新节点
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
	}
	newNode->data = x;
	newNode->next = NULL;
 
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newNode;
	}
	else
	{
		pq->ptail->next= newNode;
		pq->ptail = newNode;
	}
	
	//长度加一
	pq->sz++;
 
}
 
//出队列(队头)
void QueuePop(Queue* pq) {
	assert(pq);
	assert(pq->phead != NULL);
 
 
	if (pq->phead == pq->ptail)
	{
		free(pq->ptail);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;;
		free(pq->phead);
		pq->phead = next;
	}
	pq->sz--;
}
 
//获取队列头部元素
QDataType QueueFront(Queue* pq) {
	assert(pq);
	assert(pq->phead != NULL);
 
	return pq->phead->data;
 
 
}
 
//获取队列尾部元素
QDataType QueueBack(Queue* pq) {
	assert(pq);
	assert(pq->phead != NULL);
 
	return pq->ptail->data;
}
 
//获取队列有效元素个数
int QueueSize(Queue* pq) {
 
	assert(pq);
 
	return pq->sz;
}
 
//判断队列是否为空
bool QueueEmpty(Queue* pq) {
 
	assert(pq);
 
	return pq->phead == NULL;
 
}
 
//销毁队列
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->sz = 0;
}

test.c

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