【數據結構】線性表--隊列

【數據結構】線性表--隊列

  • 一.什么是隊列
  • 二.隊列的實現
    • 1.隊列結構定義：
    • 2.隊列初始化函數：
    • 3.隊列銷毀函數：
    • 4.入隊列函數（尾插）：
    • 5.出隊列函數（頭刪）：
    • 6.取隊頭元素：
    • 7.取隊尾元素：
    • 8.求隊長：
    • 9.判空：
  • 三.總結

一.什么是隊列

情景引入：
你們在用電腦時有沒有經歷過，機器有時會處于疑似死機的狀態，鼠標點什么似乎都沒用，雙擊任何快捷方式都不動彈。就當你失去耐心，打算reset時,突然它像酒醒了一樣，把你剛才單擊的所有操作全部都按順序執行了一遍。這是因為操作系統在當時可能CPU一時忙不過來，等前面的事忙完后，后面多個指令需要通過一個通道輸出，按先后次序排隊執行造成的結果。
再比如像移動、聯通、電信等客服電話，客服人員與客戶相比總是少數,在所有的客服人員都占線的情況下,客戶會被要求等待，直至有某個客服人員空下來，才能讓最先等待的客戶接通電話。這里也是將所有當前撥打客服電話的客戶進行了排隊處理。
操作系統和客服系統中,都是應用了一種數據結構來實現剛才提到的先進先出的排隊功能，這就是隊列。

概念理解：
隊列也是一種操作受限的線性表，與棧不同的是，隊列要求在一端插入數據，在另一端刪除數據（就類似于日常生活中的排隊一樣）。
我們將插入數據的一端稱為隊尾，刪除數據的一端稱為隊頭。隊列滿足FIFO（first in first out）原則。如圖所示：
在這里插入圖片描述

二.隊列的實現

隊列也有兩種表示方法：①順序存儲②鏈式存儲。

順序存儲即采用數組做為底層結構，由于在一端插入數據，另一端刪除數據，此時需要大量移動元素。

鏈式存儲可以使用單鏈表，也可以使用雙向鏈表。
使用單鏈表時，可以將鏈表頭作為隊頭，鏈表尾作為隊尾，此時刪除數據的操作即是頭刪，時間復雜度為O(1)，但是插入數據時，需要進行頻繁的尾插操作，時間復雜度為O(n)，因此可以再設立一個尾指針指向最后一個結點，避免每次尾插需要遍歷整個鏈表，優化時間復雜度為O(1)。
使用雙鏈表時，即頭插尾刪，或頭刪尾插。
本文使用單鏈表實現隊列。

1.隊列結構定義：

因為使用單鏈表來實現隊列，所以先定義出結點結構。結點需要存儲數據本身信息，以及保存下一個結點的位置信息。

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

因為隊列需要進行頻繁的尾插操作，所以再定義一個結構，用頭指針和尾指針來保存隊列的頭結點和尾結點的信息，以優化尾插操作的時間復雜度。

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

2.隊列初始化函數：

隊列初始化即將頭指針和尾指針均置為空即可。

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

3.隊列銷毀函數：

隊列的銷毀即通過頭指針來找到各個結點，將結點空間依次釋放，最后再將頭尾指針再次置空。

//銷毀函數
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;
}

4.入隊列函數（尾插）：

數據元素入隊列：先以元素的值申請一個新結點，然后通過尾指針找到最后一個結點，將新結點鏈接到最后一個結點的next指針，最后再將尾指針指向新結點。

//入隊列函數
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));//處理申請空間失敗的情況if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//隊列為空時，將頭尾指針指向同一個結點if (pq->head == NULL)pq->head = pq->tail = newnode;else{//先將新結點鏈接到隊列的隊尾pq->tail->next = newnode;//再將尾指針指向新結點pq->tail = newnode;}
}

5.出隊列函數（頭刪）：

出隊列時需要注意先判斷隊列是否為空，當隊列為空時不能出數據，可以使用assert斷言，也可以直接返回。
不為空時通過頭指針找到第一個結點，再順著找到下一個結點（若下一個結點為空，則代表此時鏈表只有一個結點，直接刪除），釋放掉第一個結點，并將頭指針指向下一個結點。

//出隊列函數
void QueuePop(Queue* pq)
{assert(pq);//隊列為空時不能出數據（或者使用斷言）if (pq->head == NULL){return;}else{//先記錄頭指針的下一個結點//需要先判斷下一個結點是不是空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;}}
}

6.取隊頭元素：

取隊頭元素也要注意判斷隊列是否為空，使用斷言判斷，不為空直接返回頭指針指向第一個結點的值。

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

7.取隊尾元素：

取隊尾元素也要注意判斷是否為空，使用斷言判斷。不為空時直接返回尾指針指向結點的值。

//取隊尾數據
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->head);//隊為空不能取數據return pq->tail->data;
}

8.求隊長：

求隊長直接用一個int變量，通過頭指針依次遍歷到尾指針，該變量++即可。

//求隊長（數據個數）
int QueueSize(Queue* pq)
{assert(pq);int size = 0;QNode* cur = pq->head;while (cur != NULL){size++;cur = cur->next;}return size;
}

9.判空：

直接看頭指針是否為空即可判斷隊列是否為空。

//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL;//隊列為空返回true，否則返回false
}

三.總結

除了上述實現的普通隊列，還有循環隊列、優先隊列、雙端隊列、阻塞隊列等隊列，感興趣可以上網搜索一下相關實現。
以下是本文全部源碼：
Queue.h:

#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>typedef int QDataType;typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}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);//取隊頭數據
QDataType QueueFront(Queue* pq);//取隊尾數據
QDataType QueueBack(Queue* pq);//求隊長（數據個數）
int QueueSize(Queue* pq);//判空
bool QueueEmpty(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));//處理申請空間失敗的情況if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//隊列為空時，將頭尾指針指向同一個結點if (pq->head == NULL)pq->head = pq->tail = newnode;else{//先將新結點鏈接到隊列的隊尾pq->tail->next = newnode;//再將尾指針指向新結點pq->tail = newnode;}
}//出隊列函數
void QueuePop(Queue* pq)
{assert(pq);//隊列為空時不能出數據（或者使用斷言）if (pq->head == NULL){return;}else{//先記錄頭指針的下一個結點//需要先判斷下一個結點是不是空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;}}
}//取隊頭數據
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->head);//隊為空不能取數據return pq->head->data;
}//取隊尾數據
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->head);//隊為空不能取數據return pq->tail->data;
}//求隊長（數據個數）
int QueueSize(Queue* pq)
{assert(pq);int size = 0;QNode* cur = pq->head;while (cur != NULL){size++;cur = cur->next;}return size;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL;//隊列為空返回true，否則返回false
}

test.c:

//測試各個函數功能
void test()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QueuePush(&q, 5);while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}QueueDestory(&q);
}int main()
{test();return 0;
}

感謝閱讀！^_^
在這里插入圖片描述

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/bicheng/81463.shtml
繁體地址，請注明出處：http://hk.pswp.cn/bicheng/81463.shtml
英文地址，請注明出處：http://en.pswp.cn/bicheng/81463.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

C語言—再學習（結構體）

C語言—再學習（結構體）

一、建立結構體 用戶自己建立由不同類型數據組成的組合型的數據結構&#xff0c;它稱為結構體。 struct Student { int num; //學號char name[20]; //名字為字符串char sex; //性別int age; //年紀float score; //分數char addr[30]; 地址為字符…
閱讀更多...
【前端基礎】10、CSS的偽元素（::first-line、::first-letter、::before、::after）【注：極簡描述】

【前端基礎】10、CSS的偽元素（::first-line、::first-letter、::before、::after）【注：極簡描述】

一、偽元素的作用 選取某個特定的元素。 二、::first-line、::first-letter ::first-line&#xff1a;針對首行文本設置屬性 ::first-letter&#xff1a;針對首字母設置屬性 三、::before、::after 在一個元素之前&#xff08;::before&#xff09;或者之后&#xff08;…
閱讀更多...
系統漏洞掃描服務：維護網絡安全的關鍵與服務原理？

系統漏洞掃描服務：維護網絡安全的關鍵與服務原理？

系統漏洞掃描服務是維護網絡安全的關鍵措施&#xff0c;能夠迅速發現系統中的潛在風險&#xff0c;有效預防可能的風險和損失。面對網絡攻擊手段的日益復雜化&#xff0c;這一服務的重要性日益顯著。 服務原理 系統漏洞掃描服務猶如一名恪盡職守的安全守護者。它運用各類掃描…
閱讀更多...
從 Excel 到 Data.olllo：數據分析師的提效之路

從 Excel 到 Data.olllo：數據分析師的提效之路

背景&#xff1a;Excel 的能力邊界 對許多數據分析師而言&#xff0c;Excel 是入門數據處理的第一工具。然而&#xff0c;隨著業務數據量的增長&#xff0c;Excel 的一些固有限制逐漸顯現&#xff1a; 操作容易出錯&#xff0c;難以審計&#xff1b; 打開或操作百萬行數據時&…
閱讀更多...
框架的源碼理解——V3中的ref和reactive

框架的源碼理解——V3中的ref和reactive

最近在研究各個框架的源碼&#xff0c;從源碼角度去理解 vue3 的 reactive 和 ref API&#xff0c;記錄下研究的成果 reactive 首先&#xff0c;reactive() 的參數必須是一個對象&#xff0c;返回值是一個 Proxy 對象&#xff0c;具有響應性。如果參數不是對象類型&#xff0…
閱讀更多...
能源數字化轉型關鍵引擎：Profinet轉Modbus TCP網關驅動設備協同升級

能源數字化轉型關鍵引擎：Profinet轉Modbus TCP網關驅動設備協同升級

在工業自動化的世界中&#xff0c;ModbusTCP和Profinet是兩個非常重要的通訊協議。ModbusTCP以其開放性和易用性&#xff0c;被廣泛應用于各種工業設備中&#xff1b;而Profinet則以其高效性和實時性&#xff0c;成為了眾多高端設備的首選。然而&#xff0c;由于這兩種協議的差…
閱讀更多...
【ant design】ant-design-vue 4.0實現主題色切換

【ant design】ant-design-vue 4.0實現主題色切換

官網&#xff1a;Ant Design Vue — An enterprise-class UI components based on Ant Design and Vue.js 我圖方便&#xff0c;直接在 app.vue 中加入的 <div class"app-content" v-bind:class"appOption.appContentClass"><a-config-provider…
閱讀更多...
一個指令，讓任意 AI 快速生成思維導圖

一個指令，讓任意 AI 快速生成思維導圖

大家好&#xff0c;我是安仔&#xff0c;一個每天都在壓榨 AI 的躺平打工人。 今天分享一個 AI 辦公小技巧&#xff0c;讓你用一個指令讓 AI 生成思維導圖。 DeepSeek、Kimi、豆包都可以哈 &#xff5e; KimiXMind 安仔經常用 XMind 來繪制思維導圖&#xff0c;但是 AI 是沒…
閱讀更多...
便捷的批量打印工具推薦

便捷的批量打印工具推薦

軟件介紹 本文介紹的軟件是一款批量打印軟件&#xff0c;名為PrintConductor。 軟件功能強大 這款批量打印軟件功能極為強大&#xff0c;它不僅能夠批量打印各種不同格式的文件&#xff0c;還可以直接打印整個文件夾。 初次使用設置 第一次打開這款軟件時&#xff0c;要記…
閱讀更多...
USRP 射頻信號 采集 回放 系統

USRP 射頻信號 采集 回放 系統

USRP 射頻信號采集回放系統 也可以叫做&#xff1a; 利用寬帶RF錄制和回放系統實現6G技術研究超寬帶射頻信號采集回放系統使用NI USRP平臺實現射頻信號錄制和回放操作演示USRP也能實現多通道寬帶信號流盤回放了&#xff01; 對于最簡單的實現方法就是使用LabVIEW進行實現 采…
閱讀更多...
MFC 調用海康相機進行軟觸發

MFC 調用海康相機進行軟觸發

初始化相機類文件 #pragma once #include "MvCameraControl.h" class CMvCamera { public:CMvCamera();~CMvCamera();//初始化相機int InitCamera();int SaveCurrentImage(CString filePath);//關閉相機void CloseCamera();//設置int SetEnumValue(IN const char* s…
閱讀更多...
虛擬主播肖像權保護，數字時代的法律博弈

虛擬主播肖像權保護，數字時代的法律博弈

首席數據官高鵬律師團隊 在虛擬主播行業蓬勃發展的表象之下&#xff0c;潛藏著一場關乎法律邊界的隱形戰爭。當一位虛擬偶像的3D模型被非法拆解、面部數據被批量復制&#xff0c;運營方驚訝地發現——傳統的肖像權保護體系&#xff0c;竟難以完全覆蓋這具由代碼與數據構成的“…
閱讀更多...
ArrayList-集合使用

ArrayList-集合使用

自動擴容&#xff0c;集合的長度可以變化&#xff0c;而數組長度不變&#xff0c;集合更加靈活。 集合只能存引用數據類型&#xff0c;不能直接存基本數據類型&#xff0c;除非包裝 ArrayList會拿[]展示數據
閱讀更多...
鴻蒙ArkUI體驗：Hexo博客客戶端開發心得

鴻蒙ArkUI體驗：Hexo博客客戶端開發心得

最近部門也在跟進鴻蒙平臺的業務開發&#xff0c;自己主要是做 Android 開發&#xff0c;主要使用 Kotlin/Java 語言。&#xff0c;需要對新的開發平臺和開發模式進行學習&#xff0c;在業余時間開了個項目練手&#xff0c;做了個基于 Hexo 博客內容開發的App。鴻蒙主要使用Ark…
閱讀更多...
【和春筍一起學C++】（十四）指針與const

【和春筍一起學C++】（十四）指針與const

將const用于指針&#xff0c;有兩種情況&#xff1a; const int *pt; int * const pt; 目錄 1. const int *pt 2. int * const pt 3. 擴展 1. const int *pt 首先看第一種情況&#xff0c;const在int的前面&#xff0c;有如下語句&#xff1a; int peoples12&#xff1…
閱讀更多...
本地緩存更新方案探索

本地緩存更新方案探索

文章目錄 本地緩存更新方案探索1 背景2 方案探索2.1 初始化2.2 實時更新2.2.1 長輪詢2.2.1.1 client2.2.2.2 server 本地緩存更新方案探索 1 背景 大家在工作中是否遇到過某些業務數據需要頻繁使用&#xff0c;但是數據量不大的情況&#xff0c;一般就是幾十條甚至幾百條這種…
閱讀更多...
深入理解 requestIdleCallback：瀏覽器空閑時段的性能優化利器

深入理解 requestIdleCallback：瀏覽器空閑時段的性能優化利器

requestIdleCallback 核心作用 requestIdleCallback 是瀏覽器提供的 API&#xff0c;用于將非關鍵任務延遲到瀏覽器空閑時段執行&#xff0c;避免阻塞用戶交互、動畫等關鍵任務&#xff0c;從而提升頁面性能體驗。 基本語法 const handle window.requestIdleCallback(callb…
閱讀更多...
51單片機——交通指示燈控制器設計

51單片機——交通指示燈控制器設計

設計目標 1、設計一交通燈控制&#xff0c;控制東西方向的紅、黃、綠燈和南北方向的紅、黃、綠燈。 2、可手動控制和自動控制&#xff0c;設置兩個輸入控制開關。 手動/自動開關&#xff0c;通過P11的按鍵輸入控制 3、手動&#xff1a;設置開關P11&#xff0c;兩種情況&#x…
閱讀更多...
神經網絡語言模型（前饋神經網絡語言模型）

神經網絡語言模型（前饋神經網絡語言模型）

神經網絡語言模型 什么是神經網絡&#xff1f;神經網絡的基本結構是什么&#xff1f;輸入層隱藏層輸出層 神經網絡為什么能解決問題&#xff1f;通用近似定理為什么需要權重和偏置&#xff1f;為什么需要激活函數&#xff1f;權重是如何確定的&#xff1f;1. 窮舉2. 反向傳播主…
閱讀更多...
信息系統項目管理師高級-軟考高項案例分析備考指南（2023年案例分析）

信息系統項目管理師高級-軟考高項案例分析備考指南（2023年案例分析）

個人筆記整理---僅供參考 計算題 案例分析里的計算題就是進度、掙值分析、預測技術。主要考査的知識點有:找關鍵路徑、求總工期、自由時差、總時差、進度壓縮資源平滑、掙值計算、預測計算。計算題是一定要拿下的&#xff0c;做計算題要保持頭腦清晰&#xff0c;認真讀題把PV、…
閱讀更多...
最新文章

Copyright @ 2022~2023