數據結構

鏈式隊列

以鏈表為基礎實現鏈式隊列

1.思路：

如果打算以鏈表作為基礎來實現隊列的操作，可以避免記憶體浪費以及避免記憶體成片移動，只需要確定隊頭和隊尾即可，一般把鏈表頭部作為隊頭，可以實現頭刪，把鏈表尾部作為隊尾，可以實現尾插。

2.圖示：

3.代碼：

/*****************************************************************************************************************
*	
*	file name	:	LinkedQueue.c
*	author	 	:	[email protected]
*	data  	 	:	2024/04/26
*	function	:	以鏈表為基礎實現鏈式隊列的介面程式
*	note	 	:	None
* 	
*  	CopyRight (c)	2024	[email protected] 	All Right Reseverd
*
* ****************************************************************************************************************/

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

//指的是鏈式隊列中的元素的數據類型，用戶可以根據需要進行修改
typedef int  DataType_t;

//構造記錄鏈式隊列LinkedQueue的結點,鏈表中所有結點的數據類型應該是相同的
typedef struct LinkedQueue
{
	
    DataType_t  		 data;    //結點的數據域
	struct LinkedQueue	*next;    //結點的指針域	

}LQueue_t;

/*****************************************************************************************************************
*	
*	func name	:	LQueue_Create
*	function	:	創建一個空鏈式隊列，空鏈式隊列應該有一個隊列頭結點，對鏈式隊列進行初始化
*	argument	:	None
*	retval		:	LQueue_t
*	note		:	None
*	author	 	:	[email protected]
*	data  	 	:	2024/04/26
* 	
*
* ****************************************************************************************************************/
//創建一個空鏈式隊列，空鏈式隊列應該有一個隊列頭結點，對鏈式隊列進行初始化
LQueue_t * LQueue_Create(void)
{
	//1.創建一個隊列頭結點並對隊列頭結點申請記憶體
	LQueue_t *Head = (LQueue_t *)calloc(1,sizeof(LQueue_t));
	if (NULL == Head)
	{
		perror("Calloc memory for HeadQueue is Failed");
		exit(-1);
	}

	//2.對隊列頭結點進行初始化，隊列頭結點是不存儲有效內容的！！！
	Head->next = NULL;

	//3.把隊列頭結點的地址返回即可
	return Head;
}

/*****************************************************************************************************************
*	
*	func name	:	LQueue_NewNode
*	function	:	創建新的隊列結點，並對新隊列結點進行初始化
*	argument	:	
*					@data
*	retval		:	LQueue_t
*	note		:	None
*	author	 	:	[email protected]
*	data  	 	:	2024/04/26
* 	
*
* ****************************************************************************************************************/
//創建新的隊列結點，並對新隊列結點進行初始化
LQueue_t * LQueue_NewNode(DataType_t data)
{
	//1.創建一個新隊列結點並對新隊列結點申請記憶體
	LQueue_t *New = (LQueue_t *)calloc(1,sizeof(LQueue_t));
	if (NULL == New)
	{
		perror("Calloc memory for NewNodeQueue is Failed");
		return NULL;
	}

	//2.對新結點的數據域和指針域進行初始化
	New->data = data;
	New->next = NULL;

	return New;
}

/*****************************************************************************************************************
*	
*	func name	:	LQueue_Enqueue
*	function	:	對鏈式隊列進行尾部插入操作，稱為入隊
*	argument	:	
*					@data
*					@Head
*	retval		:	bool
*	note		:	None
*	author	 	:	[email protected]
*	data  	 	:	2024/04/26
* 	
*
* ****************************************************************************************************************/
//入隊（尾插）
bool LQueue_Enqueue(LQueue_t *Head,DataType_t data)
{
	//1.創建新的結點，並對新結點進行初始化
	LQueue_t *New = LQueue_NewNode(data);
	if (NULL == New)
	{
		printf("can not insert new node for Queue\n");
		return false;
	}
	//2.判斷鏈表是否為空，如果為空，則直接插入即可
	if (NULL == Head->next)
	{
		Head->next = New;
		return true;
	}

	//3.如果鏈表為非空，則把新結點插入到鏈表的尾部
    while (Head->next)
    {
        Head = Head->next;
    }
    Head->next = New;			//把尾結點的next指針指向新節點

	return true;
}

/*****************************************************************************************************************
*	
*	func name	:	LQueue_Dequeue
*	function	:	對鏈式隊列進行頭部刪除操作，稱為出隊
*	argument	:	
*					@Head
*	retval		:	DataType_t
*	note		:	None
*	author	 	:	[email protected]
*	data  	 	:	2024/04/26
* 	
*
* ****************************************************************************************************************/
//出隊（頭刪）
DataType_t LQueue_Dequeue(LQueue_t *Head)
{
    DataType_t temp = 0;

    //1.判斷當前鏈式隊列是否為空，為空則直接退出
	if (Head->next == NULL)
	{
		printf("current linkedqueue is empty!\n");
		return -1;
	}

    //2.如果當前鏈式隊列為非空，則刪除當前鏈式隊列的頭結點
    LQueue_t *Phead = Head->next;       //備份頭結點地址

    Head->next = Head->next->next;      //把頭結點的next指針指向首結點的直接後繼

    Phead->next = NULL;                 //把首結點的next指針指向NULL

    temp = Phead->data;                 //出隊首結點的數據域

    return temp;
}

/*****************************************************************************************************************
*	
*	func name	:	LQueue_Print
*	function	:	遍歷鏈式隊列的元素
*	argument	:	
*					@Head
*	retval		:	void
*	note		:	None
*	author	 	:	[email protected]
*	data  	 	:	2024/04/26
* 	
*
* ****************************************************************************************************************/
//遍歷鏈式隊列的元素
void LQueue_Print(LQueue_t *Head)
{
	//對鏈式隊列的頭文件的地址進行備份
	LQueue_t *Phead = Head;
	
	//判斷頭結點的next指針是否指向NULL，若next指針指向NULL則退出
	while(Phead->next)
	{
		//把隊列頭結點的直接後繼作為新的隊列頭結點
		Phead = Phead->next;

		//輸出隊列現在頭結點的數據域
		printf("%d->",Phead->data);
	}

}


int main(int argc, char const *argv[])
{
	LQueue_t *Head = LQueue_Create();

    //入隊
    LQueue_Enqueue(Head,1);
    LQueue_Enqueue(Head,20);
    LQueue_Enqueue(Head,3);
    LQueue_Enqueue(Head,5);
    LQueue_Enqueue(Head,85);
    LQueue_Print(Head);
    printf("\n");
	printf("\n");

    //出隊
    printf("%d\n",LQueue_Dequeue(Head));
    printf("%d\n",LQueue_Dequeue(Head));
    printf("\n");

    //遍歷
    LQueue_Print(Head);
    printf("\n");


	return 0;
}

4.結果驗證：