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

在這里插入圖片描述

創(chuàng)建結(jié)構(gòu)體

這是一個嵌套結(jié)構(gòu)體。

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

在這里插入圖片描述

int main()
{
//創(chuàng)建結(jié)構(gòu)體變量q
//需要傳q的地址過去。
	Queue q;

	return 0;
}

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

typedef int QDataType;
//節(jié)點結(jié)構(gòu)體
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;
//頭指針和尾指針的結(jié)構(gòu)體
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

初始化結(jié)構(gòu)體

才開始還沒有創(chuàng)建隊列的空間，所以只需要初始化第一個結(jié)構(gòu)體就ok了。隊列初始狀態(tài)需要對頭和隊尾指向同一位置，且都是空。

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

銷毀隊列結(jié)構(gòu)體

這次我把銷毀結(jié)構(gòu)體放在初始化結(jié)構(gòu)體的后面，原因是內(nèi)存泄漏很嚴重，但是經(jīng)常會忘記銷毀結(jié)構(gòu)體。創(chuàng)建意味著就要銷毀，二者對立，所以排在初始化的后面，理所應當。

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

入隊

入隊的時候，會創(chuàng)建新的節(jié)點。最好最好把新開的newnode節(jié)點初始化。把他的next置為空，方便后期求隊列長度函數(shù)，和出隊函數(shù)的循環(huán)條件的書寫。

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結(jié)構(gòu)體不可能為空,所以需要斷言

還需要斷言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;
}

返回隊列的長度

長度不可能為負數(shù)，所以返回類型為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;
}

到此這篇關于C語言隊列的實現(xiàn)全解析的文章就介紹到這了,更多相關C語言隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: