C語言超詳細講解隊列的實現(xiàn)及代碼
前言
隊列的概念
- 隊列：只允許在一端進行插入數(shù)據(jù)操作，在另一端進行刪除數(shù)據(jù)操作的特殊線性表，隊列具有先進先出FIFO(First In First Out)
- 入隊列：進行插入操作的一端稱為隊尾
- 出隊列：進行刪除操作的一端稱為隊頭
隊列和前文所學的棧還是有一定區(qū)別的，隊列明確指出先進先出。假如說一個隊列的入隊順序為A B C D，那么出隊順序一定為A B C D，因為無論你是在A進去再出來，然后B進去再出來接著CD進去再出來或者類似的，都不會影響它最終的出隊順序A B C D。這點和棧還是有區(qū)別的，畢竟棧是后進先出。
隊列的結構
隊列的應用場景
隊列：
- 公平排隊
- 廣度優(yōu)先遍歷 ……
棧：
- 解決括號匹配
- 逆波蘭表達式求解
- 遞歸改非遞歸 ……
隊列的實現(xiàn)
- 在實現(xiàn)之前，首先得考慮用哪種結構好，是用數(shù)組結構還是鏈式結構呢？上文的棧我們使用的是數(shù)組結構，難道隊列也要用嗎？
- 其實不然。應該使用鏈式結構。前文棧刪除數(shù)據(jù)不需要挪動數(shù)據(jù)，使用數(shù)組結構即可滿足需求，而隊列在刪除數(shù)據(jù)時需要把后面的數(shù)據(jù)挪到前面，使用鏈式結構非常容易實現(xiàn)，只需改變節(jié)點指向即可，而數(shù)組結構想要實現(xiàn)挪動數(shù)據(jù)則非常麻煩。綜上，使用鏈式結構是最優(yōu)的。此外，單鏈表即可滿足需求，不需要使用其余較為復雜的鏈式結構。
創(chuàng)建隊列結構
思路：
這里要定義兩個結構體，除了要定義1個鏈式結構來記錄各個節(jié)點外，還要定義一個結構來記錄隊頭和隊尾。以此方便后續(xù)的隊尾入數(shù)據(jù)，隊頭出數(shù)據(jù)。
Queue.h 文件：
//創(chuàng)建隊列結構
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;隊列初始化
思路：
隊列可以為空，但是管理頭指針和尾指針的結構體不能為空，所以一開始就要斷言。其次，在插入數(shù)據(jù)前，隊列肯定是空的，所以直接把頭指針和尾指針置空即可。
Queue.h 文件：
//初始化隊列 void QueueInit(Queue* pq);
Queue.c 文件：
//初始化隊列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}隊列銷毀
思路：
銷毀隊列就是把隊列的每個數(shù)據(jù)都銷毀掉，那么需要遍歷鏈表進行挨個銷毀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ù)時，首先要考慮特殊情況，當刪到只剩一個數(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均不能為空
//特殊：當刪到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就++。這種遍歷的思想不復雜，但時間復雜度達到O(N)，不是太好，想要O(1)的話可以直接在當初定義結構體時多定義一個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即可，結構與上文一樣。
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)建隊列結構
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均不能為空
//特殊：當刪到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;
}到此這篇關于C語言超詳細講解隊列的實現(xiàn)及代碼的文章就介紹到這了,更多相關C語言 隊列的實現(xiàn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了C++ std::bind用法詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-09-09
下面小編就為大家?guī)硪黄獪\談c++中的while(cin)問題。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-05-05
這篇文章主要介紹了C語言中進程信號集的相關操作函數(shù)詳解,包括sigismember函數(shù)和sigfillset函數(shù)以及sigemptyset函數(shù)的用法,需要的朋友可以參考下2015-09-09
C++ read函數(shù)讀入int整形數(shù)據(jù)
這篇文章主要介紹了C++ read函數(shù)讀入int整形數(shù)據(jù)的相關資料,需要的朋友可以參考下2016-07-07
這篇文章主要介紹了C語言Static?關鍵字解析，C語言中staic關鍵字很簡單，簡單到你的任何一個項目中可以不寫一個staic關鍵字也是沒有問題的。寫這篇章主要是一下自己的staic的理解和應用，當然在章開頭依舊要照本宣科簡述一下static關鍵字,需要的朋友可以參考一下2022-02-02
引用（reference）就是C++對C語言的重要擴充。引用就是某一變量（目標）的一個別名，對引用的操作與對變量直接操作完全一樣2022-05-05
對性能來說，許多的問題都需要和出現(xiàn)頻率及本身執(zhí)行一次的開銷掛鉤，有些問題雖然看似比較開銷較大，但是很少會執(zhí)行到，那也不會對程序有大的影響；同樣一個很小開銷的函數(shù)執(zhí)行很頻繁，同樣會對程序的執(zhí)行效率有很大影響。本章中作者主要根據(jù)臨時對象來闡述這樣一個觀點2022-08-08
在c++中，vector是一個十分有用的容器，下面通過本文給大家介紹C++中vector容器使用詳細說明,需要的朋友可以參考下2016-10-10
QtCharts 組件是QT中提供圖表繪制的模塊，用來繪制常規(guī)圖形，本文就詳細的介紹了QChart的使用，以及柱狀圖，折線圖等常用的圖形的實現(xiàn)，感興趣的可以了解一下2021-11-11
本篇文章主要介紹了C++讀入XML文件，讀取和設置xml配置文件是最常用的操作,TinyXML是一個開源的解析XML的C++解析庫，感興趣的小伙伴們可以參考一下。2016-12-12