一、介绍

特点

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

结构

二、实现

在queue.h中需要声明的头文件

#include <stdio.h>
//malloc函数用到
#include <stdlib.h>
//assert函数用到
#include <assert.h>

队列结构

在queue.h中声明

typedef int QueueData;

//队列
typedef struct QueueNode
{
	struct QueueNode* next;
	QueueData date;
}QueueNode;
//指向队列的头尾
typedef struct Queue
{
	QueueNode* _head;
	QueueNode* _tail;
}Queue;

初始化、销毁

//初始化
void Queue_init(Queue* q)
{
	assert(q);
	q->_head = q->_tail = NULL;
}
//销毁
void Queue_destory(Queue* q)
{
	assert(q);
	QueueNode* cur = q->_head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->_head = q->_tail = NULL;
}

队列输入

队列只有一端（尾端）输入

void Queue_push(Queue* q, QueueData x)
{
	assert(q);
	//申请一块空间
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		printf("内存申请失败！");
		exit(-1);
	}
	//把输入的值存入这个空间内
	newnode->date = x;
	newnode->next = NULL; 
	//让尾指针指向它，但是要是头指针也为空，那么队列是空的，将头尾都指向它
	if (q->_head == NULL)
	{
		//将头尾都指向它
		q->_head = q->_tail = newnode;
	}
	else
	{
		q->_tail->next = newnode;
		q->_tail = newnode;
	}
}

队列删除

队列只有一端（头端）删除

void Queue_pop(Queue* q)
{
	assert(q);
	//检查是否有数据需要删除
	assert(q->_head);

	QueueNode* next = q->_head->next;
	free(q->_head);
	q->_head = next;
	//如果队列头指针都是空了，指针必然已经没有值了，需要置空，防止野指针
	if (q->_head == NULL)
	{
		q->_tail = NULL;
	}
}

获取队列前、后数据

直接返回头指针尾指针指向的data

QueueData Queue_front(Queue* q)
{
	assert(q);
	assert(q->_head);

	return q->_head->date;
}
QueueData Queue_back(Queue* q)
{
	assert(q);
	assert(q->_tail);

	return q->_tail->date;

}

查看队列是否为空

int Queue_empty(Queue* q)
{
	assert(q);
	return !(q->_head);
}

查看队列中数据的个数size

int Queue_size(Queue* q)
{
	assert(q);
	//因为结构的问题，需要遍历后才能知道数量
	QueueNode* cur = q->_head;
	int size = 0;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

三、代码

queue.h文件

#pragma once

#include <stdio.h>
//malloc函数用到
#include <stdlib.h>
//assert函数用到
#include <assert.h>

typedef int QueueData;

//队列
typedef struct QueueNode
{
	struct QueueNode* next;
	QueueData date;
}QueueNode;
//指向队列的头尾
typedef struct Queue
{
	QueueNode* _head;
	QueueNode* _tail;
}Queue;
//初始化、销毁
void Queue_init(Queue* q);
void Queue_destory(Queue* q);
//进队、出队
void Queue_push(Queue* q,QueueData x);
void Queue_pop(Queue* q);
//获取队列前、后数据
QueueData Queue_front(Queue* q);
QueueData Queue_back(Queue* q);
//返回1是非空
int Queue_empty(Queue* q);
//返回队列数据的数量
int Queue_size(Queue* q);

queue.cpp文件

#include"queue.h"

//初始化、销毁
void Queue_init(Queue* q)
{
	assert(q);
	q->_head = q->_tail = NULL;
}
void Queue_destory(Queue* q)
{
	assert(q);
	QueueNode* cur = q->_head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->_head = q->_tail = NULL;
}

//进队、出队
void Queue_push(Queue* q, QueueData x)
{
	assert(q);
	//申请一块空间
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		printf("内存申请失败！");
		exit(-1);
	}
	//把输入的值存入这个空间内
	newnode->date = x;
	newnode->next = NULL; 
	//让尾指针指向它，但是要是头指针也为空，那么队列是空的，将头尾都指向它
	if (q->_head == NULL)
	{
		//将头尾都指向它
		q->_head = q->_tail = newnode;
	}
	else
	{
		q->_tail->next = newnode;
		q->_tail = newnode;
	}
}
void Queue_pop(Queue* q)
{
	assert(q);
	//检查是否有数据需要删除
	assert(q->_head);

	QueueNode* next = q->_head->next;
	free(q->_head);
	q->_head = next;
	//如果队列头指针都是空了，指针必然已经没有值了，需要置空，防止野指针
	if (q->_head == NULL)
	{
		q->_tail = NULL;
	}
}
//获取队列前、后数据
QueueData Queue_front(Queue* q)
{
	assert(q);
	assert(q->_head);

	return q->_head->date;
}
QueueData Queue_back(Queue* q)
{
	assert(q);
	assert(q->_tail);

	return q->_tail->date;

}
//返回1是非空
int Queue_empty(Queue* q)
{
	assert(q);
	return !(q->_head);
}
//返回队列数据的数量
int Queue_size(Queue* q)
{
	assert(q);
	//因为结构的问题，需要遍历后才能知道数量
	QueueNode* cur = q->_head;
	int size = 0;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

main.cpp文件

用于测试

#include"queue.h"

void test()
{
	Queue q;
	Queue_init(&q);
	Queue_push(&q, 1);
	Queue_push(&q, 2);
	Queue_push(&q, 3);
	Queue_push(&q, 4);
	printf("%d\n", Queue_front(&q));
	printf("%d\n", Queue_back(&q));


	Queue_pop(&q);
	printf("出队一个后：\n");
	printf("%d\n", Queue_front(&q));
	printf("%d\n", Queue_back(&q));

	printf("队中的数据数量size：\n");
	printf("%d\n", Queue_size(&q));

}


int main()
{
	test();


	return 0;
}