佇列的概念及結構

佇列的實作方式

陣列佇列

鏈式佇列

鏈式佇列的實作

初始化佇列

入佇列

出佇列

獲取佇列頭部元素

獲取佇列尾部元素

獲取佇列中有效元素個數

檢測佇列是否為空

銷毀佇列

實作佇列的全部代碼

測驗用例

佇列的概念及結構

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

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

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

佇列的實作方式

實作佇列有兩種方式：1.用陣列實作，2.用鏈表實作，

陣列佇列

缺點：元素出佇列時需要將后面的資料向前面挪，效率比較低，

鏈式佇列

在佇列中保存指向隊頭隊尾的兩個指標，出隊時只需將指向隊頭的指標指向原隊頭的下一個，入隊時直接在隊尾的后面入即可

故使用鏈表的結構實作會更優一點，

鏈式佇列的實作

首先創建該佇列中單個元素的結構體，然后創建一個佇列結構體，包含指向頭、尾兩個指標，

typedef int QDataType;

typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

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

下面給出需要實作的介面：

//初始化佇列
void QueueInit(Queue* pq);

//入佇列
void QueuePush(Queue* pq, QDataType x);
//出佇列
void QueuePop(Queue* pq);

//獲取佇列頭部元素
QDataType QueueFront(Queue* pq);
//獲取佇列隊尾元素
QDataType QueueBack(Queue* pq);

//獲取佇列中有效元素個數
int QueueSize(Queue* pq);

//檢測佇列是否為空，如果為慷訓傳非零結果，如果非慷訓傳0
bool QueueEmpty(Queue* pq);

//銷毀佇列
void QueueDestroy(Queue* pq);

初始化佇列

佇列初始化只需將指向頭、尾的兩個指標指向空即可，

void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
}

入佇列

首先申請空間創建該元素，如果佇列中無元素，則將該元素作為佇列的頭和尾；如果佇列中有元素，則直接將該元素連接到佇列的尾處，并將佇列的尾指標指向該元素，

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		printf("malloc 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);//若佇列為空，無元素可出佇列，直接報錯

	//1.一個元素
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
    //2.多個元素
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

獲取佇列頭部元素

獲取元素時先檢測佇列是否有元素，若無元素則直接報錯，有元素則回傳頭指標指向節點的資料，

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->data;
}

獲取佇列尾部元素

與獲取隊頭元素相類似，

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail);

	return pq->tail->data;
}

獲取佇列中有效元素個數

從隊頭開始遍歷整個佇列并計數即可，遍歷時應創建一個新的變數進行遍歷，保證不改變頭指標，

int QueueSize(Queue* pq)
{
	assert(pq);

	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

檢測佇列是否為空

如果為慷訓傳非零結果，如果非慷訓傳0

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

	return pq->head == NULL;
}

銷毀佇列

佇列中每個元素都為新開辟的節點，故需要逐個銷毀，將所有節點銷毀完后將頭、尾指標指向空，

void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
}

實作佇列的全部代碼

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

typedef int QDataType;

typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

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

//初始化佇列
void QueueInit(Queue* pq);

//隊尾入
void QueuePush(Queue* pq, QDataType x);
//隊頭出
void QueuePop(Queue* pq);

//獲取佇列頭部元素
QDataType QueueFront(Queue* pq);
//獲取佇列隊尾元素
QDataType QueueBack(Queue* pq);

//獲取佇列中有效元素個數
int QueueSize(Queue* pq);

//檢測佇列是否為空，如果為慷訓傳非零結果，如果非慷訓傳0
bool QueueEmpty(Queue* pq);

//銷毀佇列
void QueueDestroy(Queue* pq);

void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		printf("malloc 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);

	//1.一個
	//2.多個
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail);

	return pq->tail->data;
}

int QueueSize(Queue* pq)
{
	assert(pq);

	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

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

	return pq->head == NULL;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
}

測驗用例

void TestQueue()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
    printf("%d ", QueueBack(&q));

	QueuePop(&q);
	printf("%d ", QueueFront(&q));
	QueuePop(&q);
	printf("%d ", QueueFront(&q));

	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);

    printf("QueueSize:%d\n", QueueSize(&q));

	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");

	QueueDestroy(&q);
}

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

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/342207.html

標籤：其他

上一篇：引發C++軟體例外的常見原因分析

下一篇：【資料結構初階】堆疊

（C語言）手撕資料結構之——佇列

佇列的概念及結構

佇列的實作方式

陣列佇列

鏈式佇列

鏈式佇列的實作

初始化佇列

入佇列

出佇列

獲取佇列頭部元素

獲取佇列尾部元素

獲取佇列中有效元素個數

檢測佇列是否為空

銷毀佇列

實作佇列的全部代碼

測驗用例