日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C語言?隊列的實現全解析_C 語言

作者：_奇奇 ? 更新時間： 2022-06-02 編程語言

隊列的實現

基本概念

隊列：只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表，隊列具有先進先出

FIFO(First In First Out)

入隊列：進行插入操作的一端稱為隊尾 出隊列：進行刪除操作的一端稱為隊頭

在這里插入圖片描述

隊列也可以數組和鏈表的結構實現，使用鏈表的結構實現更優一些，因為如果使用數組的結構，出隊列在數組頭上出數據，效率會比較低需要挪動數據O(N)。而鏈表結構頭刪只需要O(1)。尾插定義一個尾指針，也只需要O(1)。

在這里插入圖片描述

創建結構體

這是一個嵌套結構體。

實參q的地址傳給了形參pq。pq就是一個指向結構體Queue的指針。Queue里面的head是指向隊列對頭的指針，tail是指向隊尾的指針。

在這里插入圖片描述

int main()
{
//創建結構體變量q
//需要傳q的地址過去。
	Queue q;

	return 0;
}

定義一個尾指針tail方便入隊的尾插。頭指針head方便出隊時的頭刪。

typedef int QDataType;
//節點結構體
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;
//頭指針和尾指針的結構體
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

初始化結構體

才開始還沒有創建隊列的空間，所以只需要初始化第一個結構體就ok了。隊列初始狀態需要對頭和隊尾指向同一位置，且都是空。

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

銷毀隊列結構體

這次我把銷毀結構體放在初始化結構體的后面，原因是內存泄漏很嚴重，但是經常會忘記銷毀結構體。創建意味著就要銷毀，二者對立，所以排在初始化的后面，理所應當。

void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

入隊

入隊的時候，會創建新的節點。最好最好把新開的newnode節點初始化。把他的next置為空，方便后期求隊列長度函數，和出隊函數的循環條件的書寫。

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	assert(newnode);
	//下面兩個初始化很有必要
	newnode->data = x;
	newnode->next = NULL;

	if (pq->tail == NULL)
	{
		assert(pq->head == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

出隊

因為Queue結構體不可能為空,所以需要斷言

還需要斷言pq->head和tail都不為空。

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail);

	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;
	}
}

判斷隊列是否為空

為空返回true，為假返回false

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

	return pq->head == NULL;
}

訪問對頭的值

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;
}

返回隊列的長度

長度不可能為負數，所以返回類型為size_t

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

	return size;
}

Queue.h

#pragma once

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

typedef int QDataType;

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

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

	//size_t size;
}Queue;

void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
bool QueueEmpty(Queue* pq);
size_t QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);

Queue.c

#include "Queue.h"

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

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

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

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	assert(newnode);

	newnode->data = x;
	newnode->next = NULL;

	if (pq->tail == NULL)
	{
		assert(pq->head == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail);

	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;
	}
}

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


	return pq->head == NULL;
}

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

	return size;
}

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;
}

Test.c

void TestQueue()
{
	Queue q;
	QueueInit(&q);

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

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

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

int main()
{

	TestQueue();

	return 0;
}

原文鏈接：https://blog.csdn.net/qq2466200050/article/details/123784401

欄目分類
最近更新