佇列

佇列的概念及結構

佇列：只允許在一端進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表，佇列具有先進先出FIFO(First In First Out)

入佇列：進行插入操作的一端稱為隊尾

出佇列：進行洗掉操作的一端稱為隊頭

佇列的實作

佇列也可以陣列和鏈表的結構實作，使用鏈表的結構實作更優一些，因為如果使用陣列的結構，出佇列在陣列頭上出資料（就會挪動資料），效率會比較低

代碼模塊

佇列節點

typedef int QDatatype;

typedef struct QueueNode
{
	QDatatype data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;

佇列初始化函式QueueInit

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

對列銷毀函式QueueDestroy

//佇列銷毀函式
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur != NULL)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

入隊函式QueuePush

//入隊函式
void QueuePush(Queue* pq, QDatatype x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->data = x;
	newnode->next = NULL;
	if (!pq->head)
		pq->head = pq->tail = newnode;
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

出隊函式QueuePop

//出隊函式
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	QueueNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;
	if (!next)
		pq->tail = NULL;
}

佇列判空函式QueueErase

//佇列判空函式
bool QueueErase(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

取隊頭函式QueueFront

//取隊頭函式
QDatatype QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueErase(pq));
	return pq->head->data;
}

取隊尾函式QueueBack

//取對尾函式
QDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueErase(pq));
	return pq->tail->data;
}

取隊長函式QueueSize

//佇列長度函式
int QueueSize(Queue* pq)
{
	assert(pq);
	int n = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		n++;
		cur = cur->next;
	}
	return n;
}

測驗

void test1()
{
	Queue q;
	//把佇列結構體指標給過去，佇列里的東西隨便改
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePop(&q);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	//遍歷佇列
	while (!QueueErase(&q))
	{
		printf("%d ",QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
	QueueDestroy(&q);

代碼

Queue.h

#pragma once

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

typedef int QDatatype;

typedef struct QueueNode
{
	QDatatype data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;

//佇列初始化函式
extern void QueueInit(Queue* pq);
//佇列銷毀函式
extern void QueueDestroy(Queue* pq);
//入隊函式
extern void QueuePush(Queue* pq, QDatatype x);
//出隊函式
extern void QueuePush(Queue* pq);
//取對頭函式
extern QDatatype QueueFront(Queue* pq);
//取對尾函式
extern QDatatype QueueBack(Queue* pq);
//佇列長度函式
extern int QueueSize(Queue* pq);
//佇列判空函式
extern bool QueueErase(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"


//佇列初始化函式
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}
//佇列銷毀函式
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur != NULL)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
//入隊函式
void QueuePush(Queue* pq, QDatatype x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->data = x;
	newnode->next = NULL;
	if (!pq->head)
		pq->head = pq->tail = newnode;
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
//出隊函式
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	QueueNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;
	if (!next)
		pq->tail = NULL;
}
//取隊頭函式
QDatatype QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueErase(pq));
	return pq->head->data;
}
//取對尾函式
QDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueErase(pq));
	return pq->tail->data;
}
//佇列長度函式
int QueueSize(Queue* pq)
{
	assert(pq);
	int n = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		n++;
		cur = cur->next;
	}
	return n;
}
//佇列判空函式
bool QueueErase(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"

void test1()
{
	Queue q;
	//把佇列結構體指標給過去，佇列里的東西隨便改
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePop(&q);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	//遍歷佇列
	while (!QueueErase(&q))
	{
		printf("%d ",QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
	QueueDestroy(&q);
}

int main()
{
	test1();
	return 0;
}