国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁(yè)
  2. >Toy博客

【數(shù)據(jù)結(jié)構(gòu)與算法】隊(duì)列的實(shí)現(xiàn)

2年前作者：阿亮joy.分類：Toy博客閱讀(52)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)與算法】隊(duì)列的實(shí)現(xiàn)。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

??作者：@阿亮joy.
??專欄：《數(shù)據(jù)結(jié)構(gòu)與算法要嘯著學(xué)》
??座右銘：每個(gè)優(yōu)秀的人都有一段沉默的時(shí)光，那段時(shí)光是付出了很多努力卻得不到結(jié)果的日子，我們把它叫做扎根
【數(shù)據(jù)結(jié)構(gòu)與算法】隊(duì)列的實(shí)現(xiàn)


??隊(duì)列的概念及結(jié)構(gòu)??

隊(duì)列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊(duì)列具有先進(jìn)先出FIFO(First In First Out)的原則

入隊(duì)列：進(jìn)行插入操作的一端稱為隊(duì)尾

出隊(duì)列：進(jìn)行刪除操作的一端稱為隊(duì)頭

【數(shù)據(jù)結(jié)構(gòu)與算法】隊(duì)列的實(shí)現(xiàn)

隊(duì)列的結(jié)構(gòu)在生活中非常地常見(jiàn)，比如排隊(duì)時(shí)的抽號(hào)機(jī)就是一個(gè)典型的隊(duì)列結(jié)構(gòu)。那隊(duì)列如何實(shí)現(xiàn)呢？我們一起來(lái)看一下。

??隊(duì)列的實(shí)現(xiàn)??

隊(duì)列也可以數(shù)組和鏈表的結(jié)構(gòu)實(shí)現(xiàn)，使用鏈表的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些。因?yàn)槿绻褂脭?shù)組的結(jié)構(gòu)，出隊(duì)列在數(shù)組頭上出數(shù)據(jù)，需要挪動(dòng)數(shù)據(jù)，時(shí)間復(fù)雜度為O(N)，效率會(huì)比較低。

【數(shù)據(jù)結(jié)構(gòu)與算法】隊(duì)列的實(shí)現(xiàn)

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

typedef struct Queue
{
	QNode* head; // 頭指針
	QNode* tail; // 尾指針
	int size;    // 節(jié)點(diǎn)的個(gè)數(shù)
}Queue;

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

隊(duì)列要實(shí)現(xiàn)的函數(shù)接口有：初始化隊(duì)列、銷毀隊(duì)列、數(shù)據(jù)入隊(duì)、數(shù)據(jù)出隊(duì)、返回隊(duì)頭的數(shù)據(jù)、返回隊(duì)尾的數(shù)據(jù)、判斷隊(duì)列是否為空以及隊(duì)列中數(shù)據(jù)的個(gè)數(shù)。這些接口實(shí)現(xiàn)起來(lái)也不是很難，我們一起來(lái)看一下。

Queue.c

#include "Queue.h"

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

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

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

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

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}

	// 隊(duì)列中沒(méi)有節(jié)點(diǎn)
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	// 隊(duì)列中只有一個(gè)節(jié)點(diǎn)
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
		//del = NULL;
	}

	pq->size--;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

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

	return pq->size == 0;
	//return pq->head == NULL && pq->tail == NULL;
}
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

初始化隊(duì)列

頭指針和尾指針都指向空，隊(duì)列元素個(gè)數(shù)初始化為0

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

銷毀隊(duì)列

利用while循環(huán)將申請(qǐng)的節(jié)點(diǎn)一一釋放掉，然后頭指針pq->head和尾指針pq->tail指向空，棧的數(shù)據(jù)個(gè)數(shù)置為 0pq->size = 0

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

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

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

數(shù)據(jù)入隊(duì)

1.申請(qǐng)新的節(jié)點(diǎn)newnode newnode->data = x,newnode->next = NULL
2.數(shù)據(jù)入隊(duì)：當(dāng)pq->tail == NULL時(shí)，隊(duì)列中沒(méi)有節(jié)點(diǎn)，那么頭指針和尾指針都賦值為newnode pq->head = pq->tail = newnode；當(dāng)pq->tail != NULL時(shí)，隊(duì)列中有節(jié)點(diǎn)，那么尾部鏈接上新節(jié)點(diǎn)newnode，然后newnode成為新的尾結(jié)點(diǎn)。
3.隊(duì)列數(shù)據(jù)個(gè)數(shù)加一pq->size++

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}

	// 隊(duì)列中沒(méi)有節(jié)點(diǎn)
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

	pq->size++;
}

數(shù)據(jù)出隊(duì)

1.判斷隊(duì)列是否為空
2.數(shù)據(jù)出隊(duì)：當(dāng)pq->head->next == NULL時(shí)，隊(duì)列中只有一個(gè)節(jié)點(diǎn)，釋放該節(jié)點(diǎn)，頭指針和尾指針都指向空；當(dāng)pq->head->next != NULL時(shí)，釋放讓頭指針指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，釋放原來(lái)的頭節(jié)點(diǎn)
3.隊(duì)列數(shù)據(jù)個(gè)數(shù)減一pq->size--

【數(shù)據(jù)結(jié)構(gòu)與算法】隊(duì)列的實(shí)現(xiàn)

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	// 隊(duì)列中只有一個(gè)節(jié)點(diǎn)
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
		//del = NULL;
	}

	pq->size--;
}

返回隊(duì)頭數(shù)據(jù)

先判斷隊(duì)列是否為空，不為空時(shí)，返回隊(duì)頭數(shù)據(jù)。

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

返回隊(duì)尾數(shù)據(jù)

先判斷隊(duì)列是否為空，不為空時(shí)，返回隊(duì)尾數(shù)據(jù)。

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

判斷隊(duì)列是否為空

判斷隊(duì)列是否為空有兩種方式：1.判斷pq->size等不等于 0；2.判斷頭指針pq->head和尾指針pq->tail是否等于空指針NULL

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

	return pq->size == 0;
	//return pq->head == NULL && pq->tail == NULL;
}

隊(duì)列中數(shù)據(jù)的個(gè)數(shù)

直接返回隊(duì)列數(shù)據(jù)的個(gè)數(shù)pq->size

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

	return pq->size;
}

Test.c

以下為測(cè)試函數(shù)接口的代碼，大家可以參考一下。需要注意的是，打印隊(duì)列中的數(shù)據(jù)是通過(guò)打印隊(duì)頭數(shù)據(jù)、Pop掉隊(duì)頭數(shù)據(jù)的方式來(lái)實(shí)現(xiàn)的。

#include "Queue.h"

void QueueTest()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);

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

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

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

	QueueDestroy(&q);
}

int main()
{
	QueueTest();

	return 0;
}

【數(shù)據(jù)結(jié)構(gòu)與算法】隊(duì)列的實(shí)現(xiàn)

??總結(jié)??

本篇博客主要講解了隊(duì)列的實(shí)現(xiàn)，最重要的函數(shù)接口是數(shù)據(jù)入隊(duì)和數(shù)據(jù)出隊(duì)。在下一篇博客，本人將給大家?guī)?lái)幾道 OJ 題，大家可以期待一下。以上就是本篇博客的全部?jī)?nèi)容了，如果大家覺(jué)得有收獲的話，可以點(diǎn)個(gè)三連支持一下！謝謝大家啦！??????文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-471469.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】隊(duì)列的實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來(lái)自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場(chǎng)。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

覺(jué)得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請(qǐng)作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包