目录

什么是队列：

队列的操作：

        队列的节点结构体定义：

队列的初始化：

队列的销毁：

队尾入队列：

队头出队列：

获取队列中有效元素的个数：

检测队列是否为空：

获取队列头部元素：

获取队列尾部元素：

完整代码：

什么是队列：

队列：类似于栈，

与栈不同的有，栈只能从固定的一端进栈或出栈，

而队列，只能从一端插入数据（入队）从另一端删除数据（出队）

进行插入数据的一端（入队）称为队尾，进行删除数据（出队）的一端称为队头。

队列的操作：

        队列的节点结构体定义：

这里的队列实现采用单链表实现。

typedef int QDatatype;
//这是一个个的节点，存数据并且和下一个节点连接
typedef struct QueueNode
{
	struct QueueNode* next;
	QDatatype Data;
}QNode;

我们再来定义一个结构体来存储这个队列的头，尾指针和这个链表的大小size，这些用一个结构体封装起来以便简化传参，但是注意访问头指针就不能单独用了，必须通过结构体来访问。

typedef struct	Queue
{
	QNode* phead ;
	QNode* ptail ;
	int size;
}Queue;

队列的初始化：

思路：

将这个队列的头指针和尾指针都初始化为NULL，并且将size初始化为0。

这里的传参就不需要传三个了，因为上面我们将它们封装在了一个结构体中，所以只需要传这个结构体的指针就可以访问到这三个变量了。

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

队列的销毁：

有初始化就要有销毁。

思路：

这里和以前单链表或双向链表差不多（毕竟是通过单链表实现的），所以就直接遍历这个队列，释放上一个，最后置空即可。

void QDestroy(Queue* pq)
{
	assert(pq);
    
    QNode* cur = pq->phead;
    while(cur)
    {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}

队尾入队列：

思路：

首先malloc一个新节点（newnode），然后将这个新节点里的值设置为我要入队列的值，这个新节点里的下一个指针指向空。

然后判断头尾指针是否为空，如果为空就证明这个队列里面啥都没有，就可以直接将这个队列的头指针与尾指针都赋为新节点。

否则就证明这个队列里面有节点，这个时候将尾指针的下一个指向新节点，并且之后更新一下尾节点，将新的尾节点指向新插入的节点。

最后别忘了将size加一。

void QPush(Queue* pq, QDatatype x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

	newnode->Data = x;
	newnode->next = NULL;

	if (pq->phead == NULL)
	{
		assert(pq->ptail == NULL);

		pq->phead = pq->ptail = newnode;
	}
	else {
		pq->ptail->next = newnode;
		//更新一下
		pq->ptail = newnode;
	}
	pq->size++;
}

队头出队列：

思路：

首先要保证这个队列不为空并且头指针不为空。

然后判断：

如果头指针的下一个节点为空，（或者头指针等于尾指针）

就证明这个队列只有这一个节点，释放这个节点后，将头尾指针置为空。

否则就证明这个队列不只有一个节点，

那么就按单链表的头删即可。

最后记得size减一。

void QPop(Queue* pq)
{
	assert(pq);
	assert(pq->phead != NULL);
	
	//if (pq->phead == pq->ptail)
	if(pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else {
		QNode* del = pq->phead;
		pq->phead = pq->phead->next;
		free(del);
		del = NULL;
	}
	pq->size--;
}

获取队列中有效元素的个数：

思路：

直接通过结构体访问size，然后返回即可。

int QSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

检测队列是否为空：

思路：

如果为空返回非零结果，如果非空返回0。

采用bool类型返回值，判断size的值是否为0.

bool QEmpty(Queue* pq)
{
	assert(pq);

	return pq->size == 0;
}

获取队列头部元素：

思路：

首先要判断队列不能够为空，然后返回头指针所找到的值即可。

QDatatype QFront(Queue* pq)
{
	assert(pq);
	assert(!QEmpty(pq));

	return pq->phead->Data;
}

获取队列尾部元素：

和上面一样，只是一个找头，一个找尾。

QDatatype QBack(Queue* pq)
{
	assert(pq);
	assert(!QEmpty(pq));

	return pq->ptail->Data;
}

完整代码：

Queue.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int QDatatype;
//这是一个个的节点，存数据并且和下一个节点连接
typedef struct QueueNode
{
	struct QueueNode* next;
	QDatatype Data;
}QNode;
//存放头尾指针和size，指向这个链式结构的头，尾，size这些的。
//多个变量用一个结构体封装起来，可以简化传参
//访问头指针就不能单独用了，必须通过结构体来访问
typedef struct	Queue
{
	QNode* phead ;
	QNode* ptail ;
	int size;
}Queue;

void QInit(Queue* pq);
void QDestroy(Queue* pq);
void QPush(Queue* pq, QDatatype x);
void QPop(Queue* pq);
int QSize(Queue* pq);
bool QEmpty(Queue* pq);
QDatatype QFront(Queue* pq);
QDatatype QBack(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"

//初始化队列
void QInit(Queue* pq)
{
	assert(pq);
	
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
void QDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
//队尾入队列
void QPush(Queue* pq, QDatatype x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

	newnode->Data = x;
	newnode->next = NULL;

	if (pq->phead == NULL)
	{
		assert(pq->ptail == NULL);

		pq->phead = pq->ptail = newnode;
	}
	else {
		pq->ptail->next = newnode;
		//更新一下
		pq->ptail = newnode;
	}
	pq->size++;
}
//队头出队列
void QPop(Queue* pq)
{
	assert(pq);
	assert(pq->phead != NULL);
	
	//if (pq->phead == pq->ptail)
	if(pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else {
		QNode* del = pq->phead;
		pq->phead = pq->phead->next;
		free(del);
		del = NULL;
	}
	pq->size--;
}
// 获取队列中有效元素个数
int QSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QEmpty(Queue* pq)
{
	assert(pq);

	return pq->size == 0;
}
//获取队列头部元素
QDatatype QFront(Queue* pq)
{
	assert(pq);
	assert(!QEmpty(pq));

	return pq->phead->Data;
}
//获取队列尾部元素
QDatatype QBack(Queue* pq)
{
	assert(pq);
	assert(!QEmpty(pq));

	return pq->ptail->Data;
}

text.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"

int main()
{
	Queue q;
	QInit(&q);

	QPush(&q, 1);
	QPush(&q, 2);
	QPush(&q, 3);
	QPush(&q, 4);
	QPush(&q, 5);
	int ret = QSize(&q);
	printf("size = %d\n", ret);
	while (!QEmpty(&q))
	{
		printf("%d ", QFront(&q));
		QPop(&q);
	}
	printf("\n");

	QDestroy(&q);
	return 0;
}

测试结果：