色哟哟视频在线观看-色哟哟视频在线-色哟哟欧美15最新在线-色哟哟免费在线观看-国产l精品国产亚洲区在线观看-国产l精品国产亚洲区久久

0
  • 聊天消息
  • 系統消息
  • 評論與回復
登錄后你可以
  • 下載海量資料
  • 學習在線課程
  • 觀看技術視頻
  • 寫文章/發帖/加入社區
會員中心
創作中心

完善資料讓更多小伙伴認識你,還能領取20積分哦,立即完善>

3天內不再提示

什么是順序棧?什么又是鏈棧?

電子工程師 ? 來源:編程學習總站 ? 作者:寫代碼的牛頓 ? 2021-06-15 10:50 ? 次閱讀

1、順序棧

棧是一種后進先出的數據結構,棧的實現方式主要有2種,順序棧和鏈棧。順序棧則是棧的元素虛擬內存地址是連續的,鏈棧則是棧元素虛擬地址非連續的。在C語言里數組的元素虛擬地址是連續的但是數組大小必須在編譯的時候確定,用于實現棧不夠靈活。而在C語言里調用malloc申請到的一塊內存虛擬地址是連續的,而且大小在運行期間確定,比較符合我們靈活的實現順序棧的需求。先來看一下順序棧的定義和函數聲明。

#define NAN (0xFFFFFFFE) typedef struct stack{ int size; int cap; int front; int *arr; }_stack_t; extern void stack_init(_stack_t *s, int capacity); //初始化棧 extern void stack_push(_stack_t *s, int data); //入棧 extern int stack_pop(_stack_t *s); //出棧 extern int stack_size(_stack_t *s); //獲取棧大小 extern bool stack_is_empty(_stack_t *s); //判斷棧是否為空 extern bool stack_is_full(_stack_t *s); //判斷棧是否滿 extern void stack_destroy(_stack_t *s); //銷毀棧

這里我們自定義了一個_stack_t類型,size是棧大小,cap是棧容量,front是棧頂,arr指針指向一塊存儲數據的內存,我們還通過宏定義了一個NAN值表示非法值。

棧初始化

函數實現如下:

void stack_init(_stack_t *s, int capacity){ if(s == NULL || capacity 《= 0){ return; } s-》arr = (int *)malloc(capacity * sizeof(int)); s-》front = 0; s-》size = 0; s-》cap = capacity; }

這里我們申請了一塊內存用于存儲數據,并保存棧容量大小。

入棧

函數實現如下:

void stack_push(_stack_t *s, int data){ if(s == NULL){ return; } if(stack_is_full(s)){ return; } s-》size++; //棧使用大小增1 s-》arr[s-》front++] = data; //保存數據后棧頂指針往后移 }

由于棧容量有限,每次將數據壓入棧之前先判斷一下棧是否滿,棧未滿才能繼續往里壓入數據。

出棧

每次出棧是后面入棧的數據先出,前面入棧的數據后出。函數實現如下:

int stack_pop(_stack_t *s){ if(s == NULL){ return NAN; } //判斷棧是否空 if(stack_is_empty(s)){ return NAN; } s-》size--; //棧使用量減1 return s-》arr[--s-》front]; //先遞減棧頂指針,獲取棧頂數據 }

棧為空時說明棧里沒有數據則返回一個非法值,否則獲取棧頂數據并返回。

獲取棧大小

函數實現如下:

int stack_size(_stack_t *s){ if(s == NULL){ return 0; } return s-》size; }

判斷棧是否為空

函數實現如下:

bool stack_is_empty(_stack_t *s){ if(s == NULL){ return true; } return s-》size 》 0 ? false : true; }

判斷棧是否滿

函數實現如下:

bool stack_is_full(_stack_t *s){ if(s == NULL){ return false; } return s-》size == s-》cap ? true : false; }

銷毀棧

函數實現如下:

void stack_destroy(_stack_t *s){ if(s == NULL){ return; } if(s-》arr){ free(s-》arr); } s-》arr = NULL; s-》cap = 0; s-》size = 0; s-》front = 0; }

銷毀棧操作主要是釋放內存,并初始化成員變量。

2、鏈棧

在前面的文章中我們講解了單鏈表,在文中我們采用頭插法插入結點到鏈表,由于頭插法每次將最新的數據插入到鏈表頭,如果依次遍歷鏈表獲取鏈表結點的數據,就是標準的棧彈出數據的操作。現在我們用前面文章實現的單鏈表實現一個鏈棧,顧名思義鏈棧就是用鏈式數據結構實現棧。我們自定義一個棧數據類型并聲明一些操作函數。

typedef list_t stack_linked_t; //自定義棧數據類型 extern stack_linked_t *new_stack_linked_node(int data); //新建一個棧結點 extern void stack_linked_push(stack_linked_t **s, int data); //入棧 extern int stack_linked_pop(stack_linked_t **s); //出棧 extern int stack_linked_size(stack_linked_t *s); //獲取棧大小 extern bool stack_linked_is_empty(stack_linked_t *s); //判斷棧是否為空 extern void stack_linked_destroy(stack_linked_t **s); //銷毀棧

這里我們將list_t自定義成stack_linked_t,看似多此一舉,實際上更直觀了,我們雖然使用鏈表實現棧,但是如果將數據類型聲明為list_t反而更迷惑。由于鏈棧是鏈式結構不存在棧是否滿的情況,除非已經無法申請到內存。

新建棧結點

函數實現如下:

stack_linked_t *new_stack_linked_node(int data){ return new_list_node(data); }

這里我們直接對新建鏈表結點函數進行封裝,后面我們也會大量用到鏈表操作函數,差不多都是類似的封裝。

入棧

函數實現如下:

void stack_linked_push(stack_linked_t **s, int data){ //這里一定要注意分開兩個if,因為或運算符的特性 if(s == NULL){ return; } if(*s == NULL){ return; } //采用頭插法插入鏈表 *s = list_add(*s, data); }

這里重點注意由于我們傳入的是一個二級指針if(s == NULL)和if(*s == NULL)一定要分開處理,不能使用||運算進行處理,因為||運算符會執行第二個判斷,如果s == NULL成立那么在執行第二個判斷時由于使用了空指針程序會奔潰。

出棧

為了獲取鏈表頭結點,我們定義了一個獲取鏈表頭結點函數,函數實現如下:

list_t *get_list_head(list_t **list){ if(list == NULL){ return NULL; } if(*list == NULL){ return NULL; } list_t *head = *list; //鏈表只有一個結點 if((*list)-》next == NULL){ *list = NULL; return head; } //鏈表長度大于1則保存頭結點,新頭結點是原頭結點的下一個結點 *list = (*list)-》next; head-》next = NULL; //原頭結點一定要將next指針置為NULL return head; }

出棧函數實現如下:

int stack_linked_pop(stack_linked_t **s){ //這里一定要注意分開兩個if,因為或運算符的特性 if(s == NULL){ return NAN; } if(*s == NULL){ return NAN; } stack_linked_t *stack_node = get_list_head(s); int data = stack_node-》data; free(stack_node); return data; }

獲取鏈表頭結點數據并釋放內存。

獲取棧大小

獲取棧大小其實就是獲取鏈表長度,因此我們定義了一個獲取鏈表長度函數,函數實現如下:

//獲取鏈表長度 int list_length(list_t *list){ if(list == NULL){ return 0; } int length = 0; while(list != NULL){ length++; list = list-》next; } return length; }

獲取棧大小實現函數如下:

int stack_linked_size(stack_linked_t *s){ if(s == NULL){ return 0; } return list_length(s); }

判斷棧是否為空

函數實現如下:

bool stack_linked_is_empty(stack_linked_t *s){ if(s == NULL){ return true; } return list_length(s) 》 0 ? false : true; }

鏈表長度為0則鏈表為空,非0則有數據。

銷毀棧

函數實現如下:

void stack_linked_destroy(stack_linked_t **s){ if(s == NULL){ return; } if(*s == NULL){ return; } list_destroy(*s); *s = NULL; }

3、驗證測試

最后我們寫一個小程序驗證一下我們實現的棧是否正確,代碼如下:

#include 《stdio.h》 #include “stack.h” int main() { _stack_t my_stack; int i = 0; stack_init(&my_stack, 5); //初始化棧 printf(“進棧順序 ”); for(i = 0; i 《 5; i++){ printf(“%d, ”, i); stack_push(&my_stack, i); //將數據壓入棧 } printf(“ ”); if(stack_is_full(&my_stack)){ printf(“棧已滿 ”); }else{ printf(“棧未滿 ”); } printf(“棧的大小是:%d ”, stack_size(&my_stack)); printf(“出棧順序是 ”); for(i = 0; i 《 5; i++){ printf(“%d ,”, stack_pop(&my_stack)); } printf(“ ”); if(stack_is_empty(&my_stack)){ printf(“棧為空 ”); }else{ printf(“棧未空 ”); } stack_destroy(&my_stack); //銷毀棧 printf(“ ”); printf(“用鏈表實現棧 ”); printf(“入棧順序 ”); printf(“%d ,”, 0); stack_linked_t *my_stack2 = new_stack_linked_node(0); for(i = 0; i 《 5; i++){ printf(“%d ,”, i + 1); stack_linked_push(&my_stack2, i + 1); } printf(“ ”); printf(“棧大小是: %d ”, stack_linked_size(my_stack2)); printf(“出棧順序是 ”); for(i = 0; i 《 6; i++){ printf(“%d ,”, stack_linked_pop(&my_stack2)); } printf(“ ”); if(stack_linked_is_empty(my_stack2)){ printf(“鏈棧為空 ”); }else{ printf(“鏈棧非空 ”); } stack_linked_destroy(&my_stack2); return 0; }

編譯運行輸出:

進棧順序 0, 1, 2, 3, 4, 棧已滿 棧的大小是:5 出棧順序是 4 ,3 ,2 ,1 ,0 , 棧為空 用鏈表實現棧 入棧順序 0 ,1 ,2 ,3 ,4 ,5 , 棧大小是: 6 出棧順序是 5 ,4 ,3 ,2 ,1 ,0 , 鏈棧為空

輸出完全正確。

聲明:本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人,不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用,如有內容侵權或者其他違規問題,請聯系本站處理。 舉報投訴
  • C語言
    +關注

    關注

    180

    文章

    7608

    瀏覽量

    137150

原文標題:數據結構與算法篇-棧

文章出處:【微信號:AndroidPush,微信公眾號:Android編程精選】歡迎添加關注!文章轉載請注明出處。

收藏 人收藏

    評論

    相關推薦

    曙光云開啟全智能時代

    近日,“全可信 云中生智”曙光云戰略發布會召開。曙光云從首創“城市云”進化到實現“全智能云”,打造“云智、云安、云算、云數”四位一體能力體系,深度賦能千行百業數智化轉型升級。
    的頭像 發表于 12-19 15:11 ?279次閱讀

    λ-IO:存儲計算下的IO設計

    動機和背景? ? 存儲計算存儲資源的充分利用。IO是管理存儲器的的基本組件,包括設備驅動、塊接口層、文件系統,目前一些用戶空間IO庫(如SPDK)有效降低了延遲,但是io仍然不可或缺。這是因為1
    的頭像 發表于 12-02 10:35 ?223次閱讀
    λ-IO:存儲計算下的IO<b class='flag-5'>棧</b>設計

    CC256x TI藍牙協議基礎HFGAGDemo應用

    電子發燒友網站提供《CC256x TI藍牙協議基礎HFGAGDemo應用.pdf》資料免費下載
    發表于 11-11 15:18 ?2次下載
    CC256x TI藍牙協議<b class='flag-5'>棧</b>基礎HFGAGDemo應用

    RVBacktrace RISC-V極簡回溯組件

    RVBacktrace組件簡介一個極簡的RISC-V回溯組件。功能在需要的地方調用組件提供的唯一API,開始當前環境的回溯支持輸出addr2line需要的命令,使用addr2line進行棧回溯支持結合反匯編,回溯信息圖表化
    的頭像 發表于 09-15 08:12 ?414次閱讀
    RVBacktrace RISC-V極簡<b class='flag-5'>棧</b>回溯組件

    Linux網絡協議的實現

    網絡協議是操作系統核心的一個重要組成部分,負責管理網絡通信中的數據包處理。在 Linux 操作系統中,網絡協議(Network Stack)負責實現 TCP/IP 協議簇,處理應用程序發起的網絡
    的頭像 發表于 09-10 09:51 ?331次閱讀
    Linux網絡協議<b class='flag-5'>棧</b>的實現

    TCP/IP協議的設計與實現_中文

    電子發燒友網站提供《TCP/IP協議的設計與實現_中文.pdf》資料免費下載
    發表于 07-03 11:28 ?4次下載

    鴻蒙開發:【頁面及任務

    單個UIAbility組件可以實現多個頁面,并在多個頁面之間跳轉,這種UIAbility組件內部的頁面跳轉關系稱為“頁面”,由ArkUI框架統一管理,如下圖中的UIAbility1
    的頭像 發表于 06-14 10:10 ?441次閱讀
    鴻蒙開發:【頁面<b class='flag-5'>棧</b>及任務<b class='flag-5'>鏈</b>】

    TI Z-stack2007 協議入門實驗

    電子發燒友網站提供《TI Z-stack2007 協議入門實驗 .pdf》資料免費下載
    發表于 05-10 09:14 ?0次下載

    Microchip TCP/IP 協議應用筆記

    電子發燒友網站提供《Microchip TCP/IP 協議應用筆記.pdf》資料免費下載
    發表于 04-17 14:16 ?3次下載

    物聯數據網關是什么?

    物聯數據網關就是物聯網智能網關。 物聯數據網關是物聯網架構中的重要組件之一。它是連接物聯網設備和云平臺的中間設備,負責將物聯網設備采集到的數據傳輸到云平臺,并將云平臺下發的指令傳輸給物聯網設備
    的頭像 發表于 03-29 17:10 ?335次閱讀

    ethernetif_input和tcpip協議線程的作用

    tcpip協議線程是lwIP協議的核心線程,負責處理TCP/IP協議的各種功能,包括TCP連接管理、IP數據報的路由和轉發、以及UDP數據包的處理等。
    的頭像 發表于 03-20 10:01 ?1400次閱讀

    PROFINET協議通信技術介紹

    PROFINET協議是PROFINET通信協議的實現基礎,它由多個層次組成,每個層次都有特定的功能和作用。
    的頭像 發表于 02-03 16:22 ?2490次閱讀

    使用LwIP協議淺析實戰分析(i.MX RT)

    LWIP協議與網絡分層 LwIP(Light weight IP),是一種輕量化且開源的TCP/IP協議,它可以在有限的RAM和ROM條件下,實現一個完整的TCP/IP 協議。此外,LwIP
    的頭像 發表于 02-02 17:05 ?1824次閱讀
    使用LwIP協議<b class='flag-5'>棧</b>淺析實戰分析(i.MX RT)

    虛擬化軟件有哪些防御措施

    虛擬化軟件是一種在物理服務器上運行多個虛擬機的技術,可以提高服務器資源的利用率和靈活性。然而,虛擬化軟件也帶來了新的安全風險,因此需要采取一系列的防御措施來保護虛擬化環境的安全。下面介紹虛擬化
    的頭像 發表于 01-25 11:27 ?779次閱讀

    堆和的區別和使用注意事項

    堆和是在計算機科學中廣泛使用的兩種數據結構,它們具有不同的用途和特點。堆和的區別涉及到內存分配、訪問方式、數據存儲等方面。在使用堆和時,還需要注意一些細節,以確保程序的正確性和效率。本文將詳細
    的頭像 發表于 01-18 17:24 ?2258次閱讀
    主站蜘蛛池模板: 99精品99| 神马影院午夜伦理限级| 97精品一区二区视频在线观看| 日本xxxx19| 久久精品亚洲牛牛影视| 国产99精品在线观看| 6080yy亚洲久久无码| 亚洲精品久久无码AV片银杏| 日本高清在线一区二区三区| 久久这里只有是精品23| 国产人妻精品久久久久久很牛| chinese情侣自拍啪hd| 一本道dvd久久综合高清免费 | 无限资源在线观看8| 欧美成人中文字幕在线看| 久久嫩草影院网站| 国语自产二区高清国语自产拍| 观看免费做视频| nu77亚洲综合日韩精品| 19十主播福利视频| 在线 亚洲 日韩 欧洲视频| 亚洲精品无码一区二区三区四虎| 四虎永久在线精品免费A| 日本三区四区免费高清不卡| 男女床上黄色| 美艳人妻在厨房翘着屁股| 久久国产加勒比精品无码| 国产在线亚洲精品观| 国产高清视频a在线大全| 成人在线免费观看| ZZoo兽2皇| www.久久精品视频| bbbbbxxxxx肥胖| 99精品欧美一区二区三区美图| 2018久久视频在线视频观看| 张开腿我尝尝你的草莓| 在线观看国产亚洲| 18videosex性欧美黑色| 91se在线看片国产免费观看| 456亚洲人成在线播放网站| 最近中文字幕2019免费版|