數據結構----棧和隊列認識

目錄

棧（后進先出）

棧的實現

頭文件

初始化

入棧

注意：

bool 判空

出棧----棧頂

注意

出棧頂元素，元素不會刪除

注意：

獲取棧中有效個數

銷毀棧

源文件操作

用棧實現遞歸*

隊列（先進先出）

隊列實現

頭文件（基本操作）：

結構

初始化

判空

入隊----隊尾

出隊----隊頭

優勢：

取隊頭隊尾數據

優勢：

銷毀

棧（后進先出）

是?種特殊的線性表，其只允許在固定的?端進?插?和刪除元素操作。進?數據插?和刪除操作
的?端稱為棧頂，另?端稱為棧底。
壓棧：棧的插?操作叫做進棧/壓棧/?棧，入數據在棧頂。
出棧：棧的刪除操作叫做出棧。出數據也在棧頂。

底層結構是由數組實現的，相對來說數組在尾結點插入快

邏輯結構和物理結構都是線性的

棧的實現

頭文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定義棧的結構
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;//有效數據個數int capacity;//容量
}ST;//初始化
void StackInit(ST* ps);//棧是否為空
bool STEmpty(ST* ps);//入棧----棧頂
void StackPush(ST* ps, STDataType x);//出棧----棧頂
void StackPop(ST* ps);//出棧頂數據
STDataType StackTop(ST* ps);
\ No newline at end of file
STDataType StackTop(ST* ps);//獲取棧中有效元素個數
int StackSize(ST* ps);//棧是否為空
bool STEmpty(ST* ps);

初始化

//初始化
void StackInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->top = ps->capacity = 0;
}

使用前先調用StackInit初始化棧，然后才能進行入棧等其他操作，否則可能會導致未定義行為。

入棧

//入棧----棧頂
void StackPush(ST* ps, STDataType x)
{if (ps->top == ps->capacity){//增容int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc");exit(1);}//空間申請成功ps->arr = tmp;ps->capacity = newCapacity;}ps->arr[ps->top++] = x;
}
  1. 首先檢查棧是否已滿（ps->top == ps->capacity）
  2. 如果棧滿，則進行擴容操作：
    • 初始容量為 0 時，擴容到 4 個元素
    • 否則，按照 2 倍容量進行擴容
    • 使用realloc重新分配內存空間
    • 處理內存分配失敗的情況（打印錯誤并退出程序）
  3. 將新元素x放入棧頂位置（ps->arr[ps->top]）
  4. 棧頂指針top自增，指向新的棧頂位置

注意：

  • ps指針不為空,一般斷言一下。
  • 棧結構ST已經正確初始化
  • STDataType已經定義（通常是某種基本數據類型）

bool 判空

//棧是否為空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

為空則返回true,非空則是false

出棧----棧頂

//出棧----棧頂
void StackPop(ST* ps)
{assert(!STEmpty(ps));--ps->top;
}
  • 效率高，時間復雜度為 O (1)
  • 實現簡潔，通過移動棧頂指針而非真正釋放內存來 "刪除" 元素

注意

  • 該函數依賴STEmpty函數來判斷棧是否為空，需要確保STEmpty已正確實現
  • 出棧操作只是邏輯上移除元素（移動棧頂指針），并未真正釋放內存，這是棧實現的常見做法
  • 調用前應確保棧不為空，否則assert會觸發程序中斷

出棧頂元素，元素不會刪除


//出棧頂數據,元素不會刪除
STDataType StackTop(ST* ps)
{assert(!STEmpty(ps));return ps->arr[ps->top - 1];}

注意：

  • 棧頂指針top指向的是下一個可以插入元素的位置，所以當前棧頂元素的索引是top - 1
  • 僅僅返回元素值，不修改top指針，因此元素不會被 "刪除"
  • 依賴STEmpty函數判斷棧是否為空，需要確保該函數已正確實現

獲取棧中有效個數

//獲取棧中有效元素個數
int StackSize(ST* ps)
{return ps->top;
}
  1. 直接返回棧頂指針top的值作為棧中有效元素的個數
  2. 這是因為棧的實現中top指針恰好表示了下一個可以插入元素的位置，同時也等于當前棧中元素的數量
  3. 時間復雜度為 O (1)，效率極高

銷毀棧

void StackDestroy(ST* ps)
{assert(ps);free(ps->arr);  // 釋放底層數組內存ps->arr = NULL; // 避免野指針ps->top = ps->capacity = 0; // 重置狀態
}

源文件操作

#include"Stack.h"
void test1()
{ST st;StackInit(&st);StackPush(&st,1);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st,4);StackPush(&st, 4);StackPush(&st, 5);/*StackPop(&st);StackPop(&st);StackPop(&st);StackPop(&st);StackPop(&st);StackPop(&st);StackPop(&st);*//*while (!STEmpty(&st)){int top = StackTop(&st);printf("%d ", top);StackPop(&st);}*/int size = StackSize(&st);printf("%d\n", size);
}
int main()
{test1();return 0;
}

用棧實現遞歸*

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>// 定義棧結構
typedef int STDataType;
typedef struct Stack {STDataType* arr;int top;        // 棧頂指針，指向棧頂元素的下一個位置int capacity;   // 容量
} ST;// 棧的基本操作
void StackInit(ST* ps) {assert(ps);ps->arr = NULL;ps->top = ps->capacity = 0;
}void StackPush(ST* ps, STDataType x) {assert(ps);if (ps->top == ps->capacity) {int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL) {perror("realloc");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}ps->arr[ps->top++] = x;
}void StackPop(ST* ps) {assert(ps);assert(ps->top > 0);ps->top--;
}STDataType StackTop(ST* ps) {assert(ps);assert(ps->top > 0);return ps->arr[ps->top - 1];
}int StackSize(ST* ps) {assert(ps);return ps->top;
}void StackDestroy(ST* ps) {assert(ps);free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}// 用棧模擬遞歸計算n的階乘
int Factorial(int n) {if (n < 0) return -1; // 處理異常情況ST stack;StackInit(&stack);// 1. 模擬遞歸調用過程：將所有需要計算的數值入棧while (n > 1) {StackPush(&stack, n);n--;}// 2. 模擬遞歸返回過程：從棧頂開始計算int result = 1;while (StackSize(&stack) > 0) {result *= StackTop(&stack);StackPop(&stack);}StackDestroy(&stack);return result;
}int main() {int num = 5;int result = Factorial(num);printf("%d的階乘是: %d\n", num, result); // 輸出：5的階乘是: 120return 0;
}

隊列（先進先出）

只允許在?端進?插?數據操作，在另?端進?刪除數據操作的特殊線性表
?隊列：進?插?操作的?端稱為隊尾
出隊列：進?刪除操作的?端稱為隊頭

隊列實現

頭文件（基本操作）：

#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;
}QueueNode;
//隊列的結構
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;//int size; //隊列中有效數據個數
}Queue;//初始化
void QueueInit(Queue* pq);
//銷毀隊列
void QueueDestroy(Queue* pq);//入隊——隊尾
void QueuePush(Queue* pq, QDataType x);//出隊——隊頭
void QueuePop(Queue* pq);
//隊列判空
bool QueueEmpty(Queue* pq);
//隊列有效元素個數
int QueueSize(Queue* pq);//取隊頭數據
QDataType QueueFront(Queue* pq);
//取隊尾數據
QDataType QueueBack(Queue* pq);

結構

//隊列結點的結構
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;
//隊列的結構
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;//int size; //隊列中有效數據個數
}Queue;
  • 插入和刪除操作效率高（隊尾插入、隊首刪除均可在 O (1) 時間完成）
  • 不需要預先分配固定大小的內存，動態性好

初始化

//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;//pq->size = 0;
}
  1. 使用assert(pq)確保傳入的隊列指針pq不為空，避免空指針操作
  2. 將隊頭指針phead和隊尾指針ptail都初始化為NULL，表示初始狀態下隊列為空
  3. 注釋掉的pq->size = 0用于初始化隊列元素個數（如果保留size成員的話）

判空

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

入隊----隊尾

//入隊——隊尾
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;if (pq ->phead!= NULL)//隊列非空{pq->ptail->next = newnode;pq->ptail = newnode;}else//隊列為空{pq->phead = pq->ptail = newnode;}//size++;
}
  1. 當隊列為空時（phead為NULL），新節點既是隊頭也是隊尾
  2. 當隊列非空時，將新節點鏈接到當前隊尾節點（ptail）的next，然后更新ptail指向新節點

出隊----隊頭

//出隊——隊頭
void QueuePop(Queue* pq)
{assert(!QueueEmpty(pq));if (pq->phead == pq->ptail)//只有一個節點，頭尾都置為空{free(pq->phead);pq->phead=pq->ptail = NULL;}else{QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}
}
  1. 分兩種情況處理：
    • 當隊列中只有一個節點時（pq->phead == pq->ptail）：
      • 釋放該節點內存
      • 將phead和ptail都置為NULL，保持空隊列狀態
    • 當隊列中有多個節點時：
      • 先保存頭節點的下一個節點指針
      • 釋放頭節點內存
      • 更新phead指向保存的下一個節點

優勢：

  • 正確維護了隊列的頭指針和尾指針狀態
  • 避免了內存泄漏（釋放了被移除節點的內存）
  • 處理了隊列從有元素變為空的邊界情況

若包含size,size--保持數量一致

取隊頭隊尾數據

//取隊頭數據
QDataType QueueFront(Queue* pq)
{assert(!QueueEmpty(pq));return pq->phead->data;
}//取隊尾數據
QDataType QueueBack(Queue* pq)
{assert(!QueueEmpty(pq));return pq->ptail->data;}

優勢：

  • 時間復雜度都是 O (1)，效率很高
  • 僅獲取元素值，不會修改隊列的結構和狀態
  • 依賴QueueEmpty函數判斷隊列是否為空，保持了代碼的一致性
  • 符合隊列 "先進先出" 的特性，分別提供了訪問兩端元素的接口

銷毀

//銷毀隊列
void QueueDestroy(Queue* pq)
{assert（pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail =NULL;//pq->size =0;
}

銷毀隊列是一個通用操作，即使隊列為空（初始狀態或已清空），也應該允許調用QueueDestroy，這樣可以避免在調用銷毀函數前還需要手動判斷隊列是否為空。

允許對空隊列進行銷毀

  • 當隊列為空時，pcur初始為NULL，循環不會執行，直接重置phead和ptail
  • 當隊列非空時，循環釋放所有節點，最后重置指針

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

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

相關文章

【Kafka系列】第二篇｜ Kafka 的核心概念、架構設計、底層原理

【Kafka系列】第二篇｜ Kafka 的核心概念、架構設計、底層原理

在大數據和分布式系統飛速發展的今天&#xff0c;消息隊列作為高效的通信工具&#xff0c;在系統解耦、異步通信、流量削峰等方面作用顯著。 而 Kafka 這款高性能、高吞吐量的分布式消息隊列&#xff0c;在日志收集、數據傳輸、實時計算等場景中應用廣泛。 接下來&#xff0c;我…
閱讀更多...
Kafka-exporter采集參數調整方案

Kafka-exporter采集參數調整方案

#作者&#xff1a;張桐瑞 文章目錄1 問題概述2 修改方案2.1修改參數2.2配置示例3 消費者組均分腳本3.1使用說明3.2腳本內容3.3實現原理說明4 KAFKA-EXPORTER流程代碼4.1KAFKA-EXPORTER拉取數據流程1 問題概述 由于kafka-exporter獲取kafka指標時間過長&#xff0c;無法通過cur…
閱讀更多...
AT32的freertos下modbus TCP移植

AT32的freertos下modbus TCP移植

1.準備模板 打開雅特力官網&#xff0c;也就是帶有LwIP的示例。 下載官方源碼&#xff1a;modbus 2.移植 我這里是在這里新建兩個文件夾&#xff0c;分別是modbus與port&#xff0c;這個任意&#xff0c;只需要將必要的文件加入項目即可。 將源碼中的modbus這些都移植過來&a…
閱讀更多...
Redis面試精講 Day 16：Redis性能監控與分析工具

Redis面試精講 Day 16：Redis性能監控與分析工具

【Redis面試精講 Day 16】Redis性能監控與分析工具 開篇 歡迎來到"Redis面試精講"系列第16天&#xff0c;今天我們將深入探討Redis性能監控與分析工具。在大型分布式系統中&#xff0c;Redis作為關鍵的數據存儲和緩存組件&#xff0c;其性能指標直接影響整個系統的…
閱讀更多...
vue3+vue-flow制作簡單可拖拽可增刪改流程圖

vue3+vue-flow制作簡單可拖拽可增刪改流程圖

實現效果實現代碼 準備工作 安裝依賴 npm install vue-flow/core npm install vue-flow/minimap //小地圖 npm install vue-flow/controls //自帶的縮放、居中、加鎖功能我這里只用到上述三個&#xff0c;還有其余的可根據實際情況配合官方文檔使用。 npm install vue-flow/bac…
閱讀更多...
itextPdf獲取pdf文件寬高不準確

itextPdf獲取pdf文件寬高不準確

正常情況下我們通過下面方式獲取寬高PdfReader reader new PdfReader(file.getPath()); float width reader.getPageSize(1).getWidth(); float height reader.getPageSize(1).getHeight();但是這樣獲取的寬高是不準確的&#xff0c;永遠都是 寬 > 高&#xff0c;也就是橫…
閱讀更多...
NodeJs學習日志（2）：windows安裝使用node.js 安裝express，suquelize，mysql，nodemon

NodeJs學習日志（2）：windows安裝使用node.js 安裝express，suquelize，mysql，nodemon

windows安裝使用node.js 安裝express&#xff0c;suquelize&#xff0c;mysql&#xff0c;nodemon 系統是win10&#xff0c;默認已經安裝好nodejs與npm包名作用expressWeb應用框架suquelize數據庫ORMmysql數據庫nodemon代碼熱重載安裝express 添加express生成器 npm add expres…
閱讀更多...
VueCropper 圖片裁剪組件在Vue項目中的實踐應用

VueCropper 圖片裁剪組件在Vue項目中的實踐應用

VueCropper 圖片裁剪組件在Vue項目中的實踐應用 1. 組件介紹 VueCropper 是一個基于 Vue.js 的圖片裁剪組件&#xff0c;它提供了豐富的圖片裁剪功能&#xff0c;包括&#xff1a; 圖片縮放、旋轉、移動固定比例裁剪高質量圖片輸出多種裁剪模式選擇 2. 安裝與引入 首先需要安裝…
閱讀更多...
給同一個wordpress網站綁定多個域名的實現方法

給同一個wordpress網站綁定多個域名的實現方法

在WordPress網站上綁定多個域名&#xff0c;可以通過以下幾種方法實現&#xff1a; 1. 修改wp-config.php文件 在wp-config.php文件中&#xff0c;找到define(‘WP_DEBUG’, false);&#xff0c;在其下方添加以下代碼&#xff1a; define(WP_SITEURL, http:// . $_SERVER[HT…
閱讀更多...
HarmonyOS分布式開發實戰：打造跨設備協同應用

HarmonyOS分布式開發實戰：打造跨設備協同應用

&#x1f4d6; 文章目錄 第一章&#xff1a;HarmonyOS分布式架構揭秘第二章&#xff1a;跨設備協同的核心技術第三章&#xff1a;開發環境搭建與配置第四章&#xff1a;實戰項目&#xff1a;智能家居控制系統第五章&#xff1a;數據同步與狀態管理第六章&#xff1a;性能優化與…
閱讀更多...
用 Enigma Virtual Box 把 Qt 程序壓成單文件 EXE——從編譯、收集依賴到一鍵封包

用 Enigma Virtual Box 把 Qt 程序壓成單文件 EXE——從編譯、收集依賴到一鍵封包

關鍵詞&#xff1a;Qt、windeployqt、Enigma Virtual Box、單文件、綠色軟件 為什么要打成單文件&#xff1f; 傳統做法&#xff1a;用 windeployqt 把依賴拷進 release 目錄&#xff0c;發給用戶一個文件夾&#xff0c;文件又多又亂。理想做法&#xff1a;把整個目錄壓成一個…
閱讀更多...
unity中實現選中人物腳下顯示圓形標識且完美貼合復雜地形（如彈坑） 的效果

unity中實現選中人物腳下顯示圓形標識且完美貼合復雜地形（如彈坑） 的效果

要實現人物腳下圓形 完美貼合復雜地形&#xff08;如彈坑&#xff09; 的效果&#xff0c;核心思路是 「動態生成貼合地面的 Mesh」 —— 即根據地面的高度場實時計算環形頂點的 Y 坐標&#xff0c;讓每個頂點都 “貼” 在地面上。核心邏輯&#xff1a;確定環形范圍&#xff1a…
閱讀更多...
引領GameFi 2.0新范式：D.Plan攜手頂級財經媒體啟動“龍珠創意秀”

引領GameFi 2.0新范式：D.Plan攜手頂級財經媒體啟動“龍珠創意秀”

在GameFi賽道尋求新突破的今天&#xff0c;一個名為Dragonverse Plan&#xff08;D.Plan&#xff09;的項目正以其獨特的經濟模型和宏大愿景&#xff0c;吸引著整個Web3社區的目光。據悉&#xff0c;D.Plan即將聯合中文區頂級加密媒體金色財經與非小號&#xff08;Feixiaohao&a…
閱讀更多...
通信算法之307：fpga之時序圖繪制

通信算法之307：fpga之時序圖繪制

時序圖繪制軟件 一. 序言 在FPGA設計過程中&#xff0c;經常需要編寫設計文檔&#xff0c;其中&#xff0c;不可缺少的就是波形圖的繪制&#xff0c;可以直接截取Vivado或者Modelsim平臺實際仿真波形&#xff0c;但是往往由于信號雜亂無法凸顯重點。因此&#xff0c;通過相應軟…
閱讀更多...
計網學習筆記第3章 數據鏈路層（灰灰題庫）

計網學習筆記第3章 數據鏈路層（灰灰題庫）

題目 11 單選題 下列說法正確的是______。 A. 路由器具有路由選擇功能&#xff0c;交換機沒有路由選擇功能 B. 三層交換機具有路由選擇功能&#xff0c;二層交換機沒有路由選擇功能 C. 三層交換機適合異構網絡&#xff0c;二層交換機不適合異構網絡 D. 路由器適合異構網絡&…
閱讀更多...
SQL的LEFT JOIN優化

SQL的LEFT JOIN優化

原sql&#xff0c;一個base表a,LEFT JOIN三個表抽數 SELECT ccu.*, ctr.*, om.*, of.* FROM ods.a ccu LEFT JOIN ods.b ctr ON ccu.coupon_code ctr.coupon_code AND ctr.is_deleted 0 LEFT JOIN ods.c om ON ctr.bill_code om.order_id AND om.deleted 0 LEFT JOIN ods.…
閱讀更多...
Redis 核心概念、命令詳解與應用實踐：從基礎到分布式集成

Redis 核心概念、命令詳解與應用實踐：從基礎到分布式集成

目錄 1. 認識 Redis 2. Redis 特性 2.1 操作內存 2.2 速度快 2.3 豐富的功能 2.4 簡單穩定 2.5 客戶端語言多 2.6 持久化 2.7 主從復制 2.8 高可用 和 分布式 2.9 單線程架構 2.9.1 引出單線程模型 2.9.2 單線程快的原因 2.10 Redis 和 MySQL 的特性對比 2.11 R…
閱讀更多...
【Day 18】Linux-DNS解析

【Day 18】Linux-DNS解析

目錄 一、DNS概念 1、概念和作用 2、域名解析類型 3、 軟件與服務 4、DNS核心概念 區域 記錄 5、查詢類型 6、分層結構 二、DNS操作 配置本機為DNS內網解析服務器 &#xff08;1&#xff09;修改主配置文件 &#xff08;2&#xff09;添加區域 正向解析區域&#xff1a; …
閱讀更多...
Python 中 OpenCV (cv2) 安裝與使用介紹

Python 中 OpenCV (cv2) 安裝與使用介紹

Python 中 OpenCV (cv2) 安裝與使用詳細指南 OpenCV (Open Source Computer Vision Library) 是計算機視覺領域最流行的庫之一。Python 通過 cv2 模塊提供 OpenCV 的接口。 一、安裝 OpenCV 方法 1&#xff1a;基礎安裝&#xff08;推薦&#xff09; # 安裝核心包&#xff0…
閱讀更多...
微軟WSUS替代方案

微軟WSUS替代方案

微軟WSUS事件回顧2025年7月10日&#xff0c;微軟最新確認Windows Server Update Services&#xff08;WSUS&#xff09;出現了問題&#xff0c;導致IT管理員無法正常同步和部署Windows更新。WSUS是允許管理員根據策略配置&#xff0c;將更新推送到特定計算機&#xff0c;并優化…
閱讀更多...
最新文章

Copyright @ 2022~2023