【线性表】之队列

队列

队列的概念

队列只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的FIFO(First in First Out)。

入队列：进行插入操作的一端称为队尾。

出队列：进行删除操作的一端称为队头。

同样可以使用链表或者数组

数组：不是适合，队头出数据需要挪动数据。

链表：适合单链表，单链表头删效率很高。

结构定义

typedef int QueueDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QueueDataType data;
}QueueNode;
//单链表除了尾插还要尾删，所以不会加这个
typedef struct Queue
{
	QueueNode* tail;
	QueueNode* head;
}Queue;

初始化

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->tail = pq->head = NULL;
}

销毁

void QueueDestory(Queue* pq)
{
	assert(pq);
    //定义一个新结点
	QueueNode* cur = pq->head;
	while (cur)
	{
        //依次保存下一个结点，然后删除这个结点
		QueueNode* curNext = cur->next;
		free(cur);
		cur = curNext;
	}
	pq->head = pq->tail = NULL;
}

队尾入

void QueuePush(Queue* pq, QueueDataType x)
{
	assert(pq);
    //创建新结点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	//创建失败
    if (newnode == NULL)
	{
		printf("malloc is fail\n");
		exit(-1);
	}
    //链接
	newnode->data = x;
	newnode->next = NULL;
	//如果插入前是空的
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
          //插到后面
		pq->tail->next = newnode;
      	  //称为新的尾巴
		pq->tail = newnode;
	}
}

队头出

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);//队列是不等于空的
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		//先保存下一个结点
		QueueNode* nextNode = pq->head->next;
		free(pq->head);
		pq->head = nextNode;
	}
}

队头出

QueueDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}

队头数据

QueueDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}

队尾数据

QueueDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}

是否为空

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

返回数据个数

int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

全部代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
//结构定义
typedef int QueueDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QueueDataType data;
}QueueNode;
//单链表除了尾插还要尾删，所以不会加这个
typedef struct Queue
{
	QueueNode* tail;
	QueueNode* head;
}Queue;
//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->tail = pq->head = NULL;
}
//销毁
void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* curNext = cur->next;
		free(cur);
		cur = curNext;
	}
	pq->head = pq->tail = NULL;
}
//队尾入
void QueuePush(Queue* pq, QueueDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		printf("malloc is fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
//队头出
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);//队列是不等于空的
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		//先保存一下下一个结点
		QueueNode* nextNode = pq->head->next;
		free(pq->head);
		pq->head = nextNode;
	}
}
//队头数据
QueueDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}
//队尾数据
QueueDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}
//是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
//返回数据个数
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
void Test1()
{
	Queue pq;
	QueueInit(&pq);
	QueuePush(&pq, 1);
	QueuePush(&pq, 2);
	QueuePush(&pq, 3);
	QueuePush(&pq, 4);
    //为空是假的才成立，进入循环(不为空，进入循环)
	while (!QueueEmpty(&pq))
	{
		//取队头的数据然后删除
		printf("%d ", QueueFront(&pq));
		QueuePop(&pq);
	}
	QueueDestory(&pq);
}
int main(void)
{
	Test1();
	return 0;
}