队列精华总结

队列遵循的原则是先进先出

打印的数无论按什么时间出都是一样的

 queue.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int queuedata;
typedef struct queuenode
{
	struct queuenode*next;
	queuedata data;
}qnode;


//定义一个结构体，需要有一个头节点，和尾节点
typedef struct queue
{
	qnode*head;
	qnode*tail;

}queue;

//我们需要初始化一下
//我们可以需要用带哨兵位的头，这个主要是解决二级指针的问题
void queueinit(queue* pq);

//销毁,动态开辟必备，否则内存泄露
void queuedestroy(queue*pq);

//他的push是在队尾入，出是在队头出
void queuepush(queue*pq, queuedata x);

//队头出
void queuepop(queue*pq);

//取的是队头的数据
queuedata  queuefront(queue*pq);
//取队尾的数据
queuedata queueback(queue*pq);
//计算有多少个数据
int queuesize(queue*pq);

//对这个队列进行判空 

bool queueempty(queue*pq);

queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"queue.h"
void queueinit(queue* pq)//传过来的是结构体的指针，所以我们传一级就可以了
{
	assert(pq);
	pq->head=pq->tail=NULL;//都初始化为空//但我们在单链表中不加tail这个尾巴节点，
	                       //因为tail可以解决尾插，但是解决不了尾删,就很麻烦
}

//队尾入
void queuepush(queue*pq, queuedata x)
{
	assert(pq);
	//我们要入数据，一开始tail和head的都是空的
	qnode*newnode = (qnode*)malloc(sizeof(qnode));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)//假如说尾巴也是空，就没办法把newnode插进去，也就是说还没有节点，
	{
		pq->head = pq->tail = newnode;//那么他们就是指向的是同一个，所以这个newnode既是头也是尾
	}
//否则，我们就插入一个节点，就链接一个节点，将tail指向他
	else
	{
		pq->tail->next = newnode;//把尾巴的next指向他，进行链接，头一直不变，尾巴在变多
		pq->tail= newnode;//
	}
}

//队头出，相当于头删
void queuepop(queue*pq)
{
	assert(pq);//指针不为空
	assert(pq->head);//链表为空就错了
	//一个节点
	if (pq->head->next == NULL)//即只有一个节点
	{
		free(pq->head);
		pq->head = pq->head = NULL;//释放掉之后，把他们都置空
	}
	//多个节点
	else
	{
		qnode*next = pq->head->next;//要保存住下一个节点，否则就找不到他了
		free(pq->head);//head不用置空
		pq->head = next;//head要指向新的节点
		//假如到最后都删除完了，tail就变成一个野指针
	}
}

bool queueempty(queue*pq)
{
	assert(pq);
	return pq->head == NULL;//假如说他为空就是真，就是没有节点了，假如说他不为空就为假，用来后面打印判断用
}

//取队头的数据
queuedata  queuefront(queue*pq)
{
	assert(pq);
	assert(pq->head);//头也不能为空
	return pq->head->data;
}

//取队尾的数据
queuedata  queueback(queue*pq)
{
	assert(pq);
	assert(pq->head);//头也不能为空
	return pq->tail->data;
}

int queuesize(queue*pq)
{
	assert(pq);
	int sz = 0;
	qnode*cur = pq->head;
	while (cur)//不为空才是队的，假如说是不等于tail的话就会少算一个
	{
		++sz;
		cur = cur->next;

	}
	return sz;
}

void queuedestroy(queue*pq)
{
	assert(pq);
	qnode*cur = pq->head;
	while (cur)
	{
		qnode*next = cur->next;//要找到cur的下一个，否则就找不到下一个节点的 位置了
		//再free掉
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;//删除完后，再把head和tail置成空
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"queue.h"

int main()
{
	queue q;
	queueinit(&q);
	queuepush(&q, 1);
	queuepush(&q, 2);
	
	queuepush(&q, 3);
	queuepush(&q, 4);
	queuepush(&q, 5);
	queuepush(&q, 6);
	while (!queueempty(&q))//用我们写的函数来作为循环判断的条件，而不用自己写的东西，保证准确性
	{
		printf("%d ", queuefront(&q));
		//再删掉对头的数据
		queuepop(&q);
	}
	queuedestroy(&q);
	return 0;
}