欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言超詳細(xì)講解隊列的實現(xiàn)及代碼

 更新時間:2022年04月11日 10:41:37   作者:三分苦  
隊列(Queue)與棧一樣,是一種線性存儲結(jié)構(gòu),它具有如下特點:隊列中的數(shù)據(jù)元素遵循“先進(jìn)先出”(First?In?First?Out)的原則,簡稱FIFO結(jié)構(gòu)。在隊尾添加元素,在隊頭刪除元素

前言

隊列的概念

  • 隊列:只允許在一端進(jìn)行插入數(shù)據(jù)操作,在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表,隊列具有先進(jìn)先出FIFO(First In First Out)
  • 入隊列:進(jìn)行插入操作的一端稱為隊尾
  • 出隊列:進(jìn)行刪除操作的一端稱為隊頭

隊列和前文所學(xué)的棧還是有一定區(qū)別的,隊列明確指出先進(jìn)先出。假如說一個隊列的入隊順序為A B C D,那么出隊順序一定為A B C D,因為無論你是在A進(jìn)去再出來,然后B進(jìn)去再出來接著CD進(jìn)去再出來或者類似的,都不會影響它最終的出隊順序A B C D。這點和棧還是有區(qū)別的,畢竟棧是后進(jìn)先出。

隊列的結(jié)構(gòu)

隊列的應(yīng)用場景

隊列:

  • 公平排隊
  • 廣度優(yōu)先遍歷 ……

棧:

  • 解決括號匹配
  • 逆波蘭表達(dá)式求解
  • 遞歸改非遞歸 ……

隊列的實現(xiàn)

  • 在實現(xiàn)之前,首先得考慮用哪種結(jié)構(gòu)好,是用數(shù)組結(jié)構(gòu)還是鏈?zhǔn)浇Y(jié)構(gòu)呢?上文的棧我們使用的是數(shù)組結(jié)構(gòu),難道隊列也要用嗎?
  • 其實不然。應(yīng)該使用鏈?zhǔn)浇Y(jié)構(gòu)。前文棧刪除數(shù)據(jù)不需要挪動數(shù)據(jù),使用數(shù)組結(jié)構(gòu)即可滿足需求,而隊列在刪除數(shù)據(jù)時需要把后面的數(shù)據(jù)挪到前面,使用鏈?zhǔn)浇Y(jié)構(gòu)非常容易實現(xiàn),只需改變節(jié)點指向即可,而數(shù)組結(jié)構(gòu)想要實現(xiàn)挪動數(shù)據(jù)則非常麻煩。綜上,使用鏈?zhǔn)浇Y(jié)構(gòu)是最優(yōu)的。此外,單鏈表即可滿足需求,不需要使用其余較為復(fù)雜的鏈?zhǔn)浇Y(jié)構(gòu)。

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

思路:

這里要定義兩個結(jié)構(gòu)體,除了要定義1個鏈?zhǔn)浇Y(jié)構(gòu)來記錄各個節(jié)點外,還要定義一個結(jié)構(gòu)來記錄隊頭和隊尾。以此方便后續(xù)的隊尾入數(shù)據(jù),隊頭出數(shù)據(jù)。

Queue.h 文件:

//創(chuàng)建隊列結(jié)構(gòu)
typedef int QDataType; //方便后續(xù)更改存儲數(shù)據(jù)類型,本文以int為例
 //創(chuàng)建隊列節(jié)點
typedef struct QueueNode
{
	QDataType data; //存儲數(shù)據(jù)
	struct QueueNode* next; //記錄下一個節(jié)點
}QNode;
 //保存隊頭和隊尾
typedef struct Queue
{
	QNode* head; //頭指針
	QNode* tail; //尾指針
}Queue;

隊列初始化  

思路:

隊列可以為空,但是管理頭指針和尾指針的結(jié)構(gòu)體不能為空,所以一開始就要斷言。其次,在插入數(shù)據(jù)前,隊列肯定是空的,所以直接把頭指針和尾指針置空即可。

Queue.h 文件:

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

Queue.c 文件:

//初始化隊列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

隊列銷毀  

思路:

銷毀隊列就是把隊列的每個數(shù)據(jù)都銷毀掉,那么需要遍歷鏈表進(jìn)行挨個銷毀free。首先定義一個cur指針為pq->head,用來保存第一個數(shù)據(jù),遍歷cur,如果不為空,就free。最后把tail和head置空即可。

Queue.h 文件:

//銷毀隊列
void QueueDestory(Queue* pq);

Queue.c 文件:

//銷毀隊列
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é)點來保存新插入的數(shù)據(jù)。但是在尾插之前要考慮如果一開始隊列沒有數(shù)據(jù),為空,那么只需要把head和tail節(jié)點指向新節(jié)點newnode節(jié)點即可。相反的,如果一開始就有數(shù)據(jù),那么只需正常尾插把tail的next指向新節(jié)點newnode,再把newnode賦給tail即可。

Queue.h 文件:

//入隊列
void QueuePush(Queue* pq, QDataType x);

 Queue.c 文件:

//入隊列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//創(chuàng)建一個新節(jié)點保存數(shù)據(jù)
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	//暴力檢測newnode,因為malloc的都要檢測
	assert(newnode);
	newnode->next = NULL;
	newnode->data = x;
	//如果一開始沒有數(shù)據(jù),為空的情況
	if (pq->tail == NULL)
	{
		assert(pq->head == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

出隊列  

思路:

特殊情況:

這里在刪除數(shù)據(jù)時,首先要考慮特殊情況,當(dāng)刪到只剩一個數(shù)據(jù)時,再刪一次,此時數(shù)據(jù)是沒了,不過head為空了,而tail變成野指針了,為了避免此現(xiàn)象的產(chǎn)生,單獨討論并置空head和tail即可。

一般情況:

此時只需要定義一個next指針保存head的下一個節(jié)點,將head移動到next即可,并把舊的head置空。

 Queue.h 文件:

//出隊列
void QueuePop(Queue* pq);

Queue.c 文件:

//出隊列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail); //tail和head均不能為空
	//特殊:當(dāng)刪到head=tail的位置時
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//一般情況
	else
	{
		//保存head的下一個節(jié)點
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

隊列判空  

思路:

如果head為空或者tail為空都是判空的條件,直接返回即可。

Queue.h 文件:

//判空
bool QueueEmpty(Queue* pq);

Queue.c 文件:

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

獲取隊列元素個數(shù)  

思路:

求元素個數(shù)其實不難,只需要定義一個cur指針為第一個數(shù)據(jù)pq->head,定義變量size來記錄個數(shù)。依次遍歷cur,不為空,size就++。這種遍歷的思想不復(fù)雜,但時間復(fù)雜度達(dá)到O(N),不是太好,想要O(1)的話可以直接在當(dāng)初定義結(jié)構(gòu)體時多定義一個size變量,專門用來記錄有效元素個數(shù),每次入隊列size++,出隊列size--。這樣實現(xiàn)是比較好的,不過為了封裝成一個獨立模塊,還是采用遍歷的方式。如下:

Queue.h 文件:

//獲取有效元素個數(shù)
size_t QueueSize(Queue* pq);

Queue.c 文件:

//獲取有效元素個數(shù)
size_t QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	size_t size = 0;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

獲取隊列頭部元素  

思路:

首先要斷言頭部不能為空,如果頭部都為空了,那還怎么能獲得頭部元素,其次直接返回頭部head的數(shù)據(jù)即可。

Queue.h 文件:

//獲取隊頭元素
QDataType QueueFront(Queue* pq);

Queue.c 文件:

//獲取隊頭元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head); //頭部不能為空
	return pq->head->data;
}

獲取隊列尾部元素  

思路:

有了獲取隊頭元素的經(jīng)驗,隊尾就更簡單了,把head換位tail即可,結(jié)構(gòu)與上文一樣。

Queue.h 文件:

//獲取隊尾元素
QDataType QueueBack(Queue* pq);

Queue.c 文件:

//獲取隊尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail); //尾部不能為空
	return pq->tail->data;
}

總代碼

Queue.h 文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
//創(chuàng)建隊列結(jié)構(gòu)
typedef int QDataType; //方便后續(xù)更改存儲數(shù)據(jù)類型,本文以int為例
 //創(chuàng)建隊列節(jié)點
typedef struct QueueNode
{
	QDataType data; //存儲數(shù)據(jù)
	struct QueueNode* next; //記錄下一個節(jié)點
}QNode;
 //保存隊頭和隊尾
typedef struct Queue
{
	QNode* head; //頭指針
	QNode* tail; //尾指針
}Queue;
 
//初始化隊列
void QueueInit(Queue* pq);
 
//銷毀隊列
void QueueDestory(Queue* pq);
 
//入隊列
void QueuePush(Queue* pq, QDataType x);
 
//出隊列
void QueuePop(Queue* pq);
 
//判空
bool QueueEmpty(Queue* pq);
 
//獲取有效元素個數(shù)
size_t QueueSize(Queue* pq);
 
//獲取隊頭元素
QDataType QueueFront(Queue* pq);
 
//獲取隊尾元素
QDataType QueueBack(Queue* pq);

Queue.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#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);
	//創(chuàng)建一個新節(jié)點保存數(shù)據(jù)
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	//暴力檢測newnode,因為malloc的都要檢測
	assert(newnode);
	newnode->next = NULL;
	newnode->data = x;
	//如果一開始沒有數(shù)據(jù),為空的情況
	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); //tail和head均不能為空
	//特殊:當(dāng)刪到head=tail的位置時
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//一般情況
	else
	{
		//保存head的下一個節(jié)點
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
 
//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
 
//獲取有效元素個數(shù)
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 文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void TestQueue()
{
	Queue q;
	QueueInit(&q);
	//插入數(shù)據(jù)
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	//打印
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
}
int main()
{
	TestQueue();
	return 0;
}

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

相關(guān)文章

  • C++ std::bind用法詳解

    C++ std::bind用法詳解

    這篇文章主要介紹了C++ std::bind用法詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-09-09
  • 淺談c++中的while(cin)問題

    淺談c++中的while(cin)問題

    下面小編就為大家?guī)硪黄獪\談c++中的while(cin)問題。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-05-05
  • C語言中進(jìn)程信號集的相關(guān)操作函數(shù)詳解

    C語言中進(jìn)程信號集的相關(guān)操作函數(shù)詳解

    這篇文章主要介紹了C語言中進(jìn)程信號集的相關(guān)操作函數(shù)詳解,包括sigismember函數(shù)和sigfillset函數(shù)以及sigemptyset函數(shù)的用法,需要的朋友可以參考下
    2015-09-09
  • C++ read函數(shù)讀入int整形數(shù)據(jù)

    C++ read函數(shù)讀入int整形數(shù)據(jù)

    這篇文章主要介紹了C++ read函數(shù)讀入int整形數(shù)據(jù)的相關(guān)資料,需要的朋友可以參考下
    2016-07-07
  • C語言Static?關(guān)鍵字解析

    C語言Static?關(guān)鍵字解析

    這篇文章主要介紹了C語言Static?關(guān)鍵字解析,C語言中staic關(guān)鍵字很簡單,簡單到你的任何一個項目中可以不寫一個staic關(guān)鍵字也是沒有問題的。寫這篇章主要是一下自己的staic的理解和應(yīng)用,當(dāng)然在章開頭依舊要照本宣科簡述一下static關(guān)鍵字,需要的朋友可以參考一下
    2022-02-02
  • c++超細(xì)致講解引用

    c++超細(xì)致講解引用

    引用(reference)就是C++對C語言的重要擴充。引用就是某一變量(目標(biāo))的一個別名,對引用的操作與對變量直接操作完全一樣
    2022-05-05
  • C++實例分析講解臨時對象與右值引用的用法

    C++實例分析講解臨時對象與右值引用的用法

    對性能來說,許多的問題都需要和出現(xiàn)頻率及本身執(zhí)行一次的開銷掛鉤,有些問題雖然看似比較開銷較大,但是很少會執(zhí)行到,那也不會對程序有大的影響;同樣一個很小開銷的函數(shù)執(zhí)行很頻繁,同樣會對程序的執(zhí)行效率有很大影響。本章中作者主要根據(jù)臨時對象來闡述這樣一個觀點
    2022-08-08
  • C++中vector容器使用詳細(xì)說明

    C++中vector容器使用詳細(xì)說明

    在c++中,vector是一個十分有用的容器,下面通過本文給大家介紹C++中vector容器使用詳細(xì)說明,需要的朋友可以參考下
    2016-10-10
  • C/C++ Qt QChart繪圖組件的具體使用

    C/C++ Qt QChart繪圖組件的具體使用

    QtCharts 組件是QT中提供圖表繪制的模塊,用來繪制常規(guī)圖形,本文就詳細(xì)的介紹了QChart的使用,以及柱狀圖,折線圖等常用的圖形的實現(xiàn),感興趣的可以了解一下
    2021-11-11
  • C++讀入XML文件示例

    C++讀入XML文件示例

    本篇文章主要介紹了C++讀入XML文件,讀取和設(shè)置xml配置文件是最常用的操作,TinyXML是一個開源的解析XML的C++解析庫,感興趣的小伙伴們可以參考一下。
    2016-12-12

最新評論