[數據結構——lesson6.棧]

目錄

引言

1.棧的概念和結構

棧的核心概念

棧的結構

2.棧的實現

2.1棧的實現方式

2.2棧的功能

2.3棧的聲明

1.順序棧

2。鏈式棧

2.4棧的功能實現

1.棧的初始化

2.判斷棧是否為空

3.返回棧頂元素

4.返回棧的大小

5.元素入棧

6.元素出棧

7.打印棧的元素

8.銷毀棧

3.順序棧和鏈式棧的對比

?適用場景

總結

4.完整代碼

1.順序表

2.鏈式表

結束語


引言

在學習完鏈表之后,我們接下來學習數據結構——棧。

學習目標:

  • 1.棧的概念和結構
  • 2.棧的實現
  • 3.順序棧和鏈式棧的對比

1.棧的概念和結構

棧(Stack)是一種線性數據結構,其核心特點是 “后進先出”(Last In, First Out,LIFO)—— 即最后入棧的元素會最先被彈出。這種特性類似于日常生活中的 “疊盤子”:最后疊上去的盤子,會被最先拿走。

棧的核心概念

  1. 入棧(Push):向棧頂添加元素。
  2. 出棧(Pop):從棧頂移除并返回元素(棧為空時無法出棧)。
  3. 棧頂(Top):棧中最上方的元素(最后入棧的元素)。
  4. 棧底(Bottom):棧中最下方的元素(最先入棧的元素)。
  5. 棧空(Empty):棧中沒有任何元素的狀態。
  6. 棧的大小(Size):棧中元素的數量。

棧的結構

棧的結構可以抽象為一個 “容器”,元素只能從一端(棧頂)進行插入和刪除操作,另一端(棧底)是固定的。

“后進先出”(Last In, First Out,LIFO):

棧頂(Top):棧頂是棧中最后添加(push)元素的位置,也是最先被移除(pop)或查看(peek/top)的元素所在的位置。在棧的所有操作中,無論是添加、刪除還是查看元素,都是針對棧頂進行的。因此,棧頂是棧中最活躍、最頻繁被訪問的位置。

棧底(Bottom):棧底是棧中最早被添加進去的元素所在的位置,也是棧中唯一一個固定不變的位置(除非整個棧被清空)。在棧的常規操作中,棧底元素不會被直接訪問,除非是將整個棧的內容倒序輸出或者棧被完全清空。因此,棧底在棧的操作中扮演的是一個相對靜態的角色。

壓棧:棧的插入操作叫做進棧/入棧,入數據在棧頂。

出棧:棧的刪除操作叫做出棧,出數據也在棧頂。

  • 在計算機領域,棧有著廣泛應用。例如,在編程語言中,函數調用時會使用棧來管理局部變量和返回地址。當一個函數被調用時,其相關的信息(如參數、局部變量等)會被壓入棧中,函數執行完畢后,這些信息會從棧中彈出。此外,表達式求值、括號匹配等問題也常借助棧來解決。

2.棧的實現

2.1棧的實現方式

棧可以通過兩種常見的數據結構實現:

  1. 數組實現(順序棧)

    • 用數組存儲元素,棧頂對應數組的最后一個索引。
    • 入棧:在數組尾部添加元素(時間復雜度 O (1))。
    • 出棧:刪除數組尾部元素(時間復雜度 O (1))。
    • 缺點:數組大小固定,可能出現溢出(需動態擴容)。
  2. 鏈表實現(鏈式棧)

    • 用鏈表的頭節點作為棧頂,每次操作頭節點。
    • 入棧:在鏈表頭部插入新節點(時間復雜度 O (1))。
    • 出棧:刪除鏈表頭部節點(時間復雜度 O (1))。
    • 優點:大小靈活,無需考慮擴容。

相對而言數組的結構實現更優,因為數組在尾上插入數據的代價比較小。

2.2棧的功能

棧的數據結構要實現如下功能:

1.棧的初始化。
2.判斷棧是否為空。
3.返回隊頭元素。
4.返回棧的大小。
5.元素入棧。

6.元素出棧。
7.打印棧的元素。
8.銷毀棧。

2.3棧的聲明

1.順序棧

順序棧的聲明需要一個指向一塊空間的指針a,指向棧頂元素的top,以及標志棧空間大小的capacity。

typedef int STDataType;typedef struct STDataType
{STDataType* a;int top;int capacity;
}ST;
2.鏈式棧

鏈式棧的聲明只需要一個top指針,以及棧的容量capacity。

當然這里需要鏈表的聲明。

typedef int STDataType;typedef struct SListNode
{STDataType data;struct SListNode* next;
}SLTNode;typedef struct Stack
{// 指向棧頂節點的指針SLTNode* top;int size;
}ST;

2.4棧的功能實現

1.棧的初始化

順序棧和鏈式棧都可以先初始為NULL。

(1)順序棧

順序棧可以將top設置為-1,capacity設置為0。

代碼如下:

//棧的初始化
void STInit(ST* st)
{assert(st);st->a = NULL;st->top = -1;st->capacity = 0;
}
(2)鏈式棧

鏈式棧將size設置為0,top設置為NULL。

//棧的初始化
void STInit(ST* st)
{assert(st);st->size = 0;st->top = NULL;
}
2.判斷棧是否為空

判斷棧是否為空只需要判斷top的指向。

(1)順序棧

當top=-1則為空。

代碼如下:

//判空
bool STEmpty(ST* st)
{assert(st);return st->top == -1;
}
(2)鏈式棧

判斷top是否指向NULL。

//判空
bool STEmpty(ST* st)
{return (st->top == NULL);
}
3.返回棧頂元素
(1)順序棧
//取出棧頂數據
STDataType STTop(ST* st)
{assert(st);// 斷言確保棧不為空(即棧頂索引不小于0)assert(st->top >= 0);return st->a[st->top];
}
(2)鏈式棧
//取出棧頂數據
STDataType STTop(ST* st)
{assert(st);assert(!STEmpty(st));return st->top->data;
}
4.返回棧的大小
(1)順序棧

由于在一開始將top設置為-1,需要top+1才能符合需要。

代碼如下:

//獲取數據個數
STDataType STSize(ST* st)
{assert(st);return st->top + 1;
}
(2)鏈式棧
//獲取數據個數
STDataType STSize(ST* st)
{return st->size;
}
5.元素入棧

注意:入棧需要檢查空間是否足夠。

(1)順序棧

由于top設置的是-1,因此需要先騰出空間然后再將新元素x放在棧頂。

代碼如下:

//入棧
void STPush(ST* st, STDataType x)
{assert(st);// 注意:由于top初始化為-1,所以滿的條件是top == capacity - 1if (st->top == st->capacity - 1){// 如果棧已滿,則擴展棧的容量int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;STDataType* tmp = (STDataType*)realloc(st->a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail:");return;}st->a = tmp;st->capacity = newcapacity;}// 增加棧頂索引,為新元素騰出空間st->top++;// 將新元素x存儲在棧頂位置st->a[st->top] = x;
}
(2)鏈式棧
//入棧
void STPush(ST* st, STDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail:");return;}// 新節點的next指向原來的棧頂newnode->next = st->top;// 設置新節點的數據newnode->data = x;// 更新棧頂為新節點st->top = newnode;st->size++;
}
6.元素出棧

(1)順序棧
//出棧
void STPop(ST* st)
{assert(st);assert(st->top >= 0);st->top--;
}

(2)鏈式棧

//出棧
void STPop(ST* st)
{assert(st);assert(!STEmpty(st));// 獲取棧頂節點的下一個節點SLTNode* next = st->top->next;free(st->top);// 更新棧頂指針,使其指向新的棧頂節點st->top = next;st->size--;
}
7.打印棧的元素
(1)順序棧
//棧的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));// 從棧頂開始打印,直到棧底(但不包括索引-1)for (int i = st->top; i >= 0; i--){printf("%d ", st->a[i]);}
}
(2)鏈式棧
//棧的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));for (SLTNode* top = st->top; top != NULL; top = top->next){printf("%d ", top->data);}
}
8.銷毀棧
(1)順序棧
//棧的銷毀
void STDestory(ST* st)
{assert(st);free(st->a);st->a = NULL;st->capacity = 0;st->top = -1;
}
(2)鏈式棧
//棧的銷毀
void STDestory(ST* st) 
{assert(st);SLTNode* top = st->top;while (top != NULL){SLTNode* next = top->next;free(top);top = next;}st->size = 0;
}

3.順序棧和鏈式棧的對比

順序棧鏈式棧
數據結構使用動態數組實現,元素在物理內存中連續存儲使用鏈表實現,元素通過節點和指針連接,內存空間不連續
內存管理棧空間不足時可動態擴容,釋放整個棧時一次性釋放內存節點內存單獨分配和釋放,需要遍歷鏈表以釋放所有節點內存
時間效率可以通過數組下標直接訪問棧內任意位置的元素,但是這不符合棧的定義由于每次都需要擴容操作,所以效率略比順序棧低
空間效率順序棧的擴容較大可能會造成空間的浪費內存使用相對靈活,但每個節點需要額外存儲指針

優缺點對比

順序棧鏈式棧
優點1. 內存連續,緩存利用率高(局部性原理);
2. 實現簡單,操作高效(無指針操作)。
1. 無需預分配空間,大小動態調整;
2. 不會出現棧溢出(除非內存耗盡)。
缺點1. 初始化時需確定容量,可能溢出或浪費空間;
2. 動態擴容時有性能開銷。
1. 每個節點需額外存儲指針,空間開銷略大;
2. 內存不連續,緩存利用率較低。

?適用場景

  • 順序棧
    適用于元素數量已知或變化不大的場景,例如:

    • 表達式求值(元素數量有限);
    • 函數調用棧(深度可控)。
  • 鏈式棧
    適用于元素數量不確定或變化劇烈的場景,例如:

    • 處理動態數據(如日志記錄,長度未知);
    • 需頻繁擴容的場景(避免順序棧的復制開銷)。

總結

  • 順序棧注重效率和空間連續性,適合場景固定、數據量可預測的情況;
  • 鏈式棧注重靈活性,適合數據量動態變化、難以預估的情況。

4.完整代碼

1.順序表

Stack.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;typedef struct STDataType
{STDataType* a;int top;int capacity;
}ST;//棧的初始化
void STInit(ST* st);//棧的銷毀
void STDestory(ST* st);//入棧
void STPush(ST* st, STDataType x);
//出棧
void STPop(ST* st);//取出棧頂數據
STDataType STTop(ST* st);//判空
bool STEmpty(ST* st);//獲取數據個數
STDataType STSize(ST* st);//棧的打印
void STPrint(ST* st);

Stack.c

#include"Stack.h"//棧的初始化
void STInit(ST* st)
{assert(st);st->a = NULL;st->top = -1;st->capacity = 0;
}//棧的銷毀
void STDestory(ST* st)
{assert(st);free(st->a);st->a = NULL;st->capacity = 0;st->top = -1;
}//入棧
void STPush(ST* st, STDataType x)
{assert(st);// 注意:由于top初始化為-1,所以滿的條件是top == capacity - 1if (st->top == st->capacity - 1){// 如果棧已滿,則擴展棧的容量int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;STDataType* tmp = (STDataType*)realloc(st->a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");return;}st->a = tmp;st->capacity = newcapacity;}// 增加棧頂索引,為新元素騰出空間st->top++;// 將新元素x存儲在棧頂位置st->a[st->top] = x;
}//出棧
void STPop(ST* st)
{assert(st);assert(st->top >= 0);st->top--;
}//取出棧頂數據
STDataType STTop(ST* st)
{assert(st);assert(st->top >= 0);return st->a[st->top];
}//判空
bool STEmpty(ST* st)
{assert(st);return st->top == -1;
}//獲取數據個數
STDataType STSize(ST* st)
{assert(st);return st->top + 1;
}//棧的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));// 從棧頂開始打印,直到棧底(但不包括索引-1)for (int i = st->top; i >= 0; i--){printf("%d ", st->a[i]);}
}
2.鏈式表

Stack.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;typedef struct SListNode
{STDataType data;struct SListNode* next;
}SLTNode;typedef struct Stack
{// 指向棧頂節點的指針SLTNode* top;int size;
}ST;//棧的初始化
void STInit(ST* st);//棧的銷毀
void STDestory(ST* st);//入棧
void STPush(ST* st, STDataType x);//出棧
void STPop(ST* st);//取出棧頂數據
STDataType STTop(ST* st);//判空
bool STEmpty(ST* st);//獲取數據個數
STDataType STSize(ST* st);//棧的打印
void STPrint(ST* st);

Stack.c

#include"Stack.h"//棧的初始化
void STInit(ST* st)
{assert(st);st->size = 0;st->top = NULL;
}//棧的銷毀
void STDestory(ST* st) 
{assert(st);SLTNode* top = st->top;while (top != NULL){SLTNode* next = top->next;free(top);top = next;}st->size = 0;
}//入棧
void STPush(ST* st, STDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail:");return;}// 新節點的next指向原來的棧頂newnode->next = st->top;// 設置新節點的數據newnode->data = x;// 更新棧頂為新節點st->top = newnode;st->size++;
}//出棧
void STPop(ST* st)
{assert(st);assert(!STEmpty(st));// 獲取棧頂節點的下一個節點SLTNode* next = st->top->next;free(st->top);// 更新棧頂指針,使其指向新的棧頂節點st->top = next;st->size--;
}//取出棧頂數據
STDataType STTop(ST* st)
{assert(st);assert(!STEmpty(st));return st->top->data;
}//判空
bool STEmpty(ST* st)
{return (st->top == NULL);
}//獲取數據個數
STDataType STSize(ST* st)
{return st->size;
}//棧的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));for (SLTNode* top = st->top; top != NULL; top = top->next){printf("%d ", top->data);}
}

結束語

本篇我們主要介紹了一下棧,接下來我們將接著學習與棧類似的另一個數據結構——隊列。

感謝您的三連支持!!!

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

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

相關文章

華為HICE云計算的含金量高嗎?

在數字時代的今天&#xff0c;云計算技術證飛速的發展成為企業數字化轉型的重要支撐。而華為作為領先的通信和信息技術公司&#xff0c;推出的HCIE云計算認證備受關注。接下來就來說說華為HCIE云計算認證的含金量到底有多高。HCIE認證被認為是華為認證中的最高等級&#xff0c;…

OSPF協議原理講解和實際配置(華為/思科)

OSPF&#xff08;open shorest path first&#xff0c;開放最短路徑優先&#xff09;是一種動態的&#xff0c;基于鏈路狀態的動態路由協議&#xff0c;廣泛的應用在企業網絡中&#xff0c;通過維護網絡拓撲信息&#xff0c;利用 Dijkstra 算法實現最短路徑&#xff0c;實現高效…

【開題答辯全過程】以 《黃帝內經》問答系統為例,包含答辯的問題和答案

個人簡介一名14年經驗的資深畢設內行人&#xff0c;語言擅長Java、php、微信小程序、Python、Golang、安卓Android等開發項目包括大數據、深度學習、網站、小程序、安卓、算法。平常會做一些項目定制化開發、代碼講解、答辯教學、文檔編寫、也懂一些降重方面的技巧。感謝大家的…

npm : 無法加載文件 C:\Program Files\nodejs\npm.ps1,因為在此系統上禁止運行腳

這個錯誤是由于 PowerShell 的執行策略限制&#xff0c;導致無法運行腳本。你可以通過以下步驟解決這個問題&#xff1a; 1. 查看當前的執行策略 打開 PowerShell&#xff0c;以管理員身份運行&#xff0c;輸入以下命令查看當前的執行策略&#xff1a; Get-ExecutionPolicy如果…

macOS蘋果電腦運行向日葵遠程控制軟件閃退

文章目錄問題原因分析修復附錄向日葵字太小按Ctrl鍵會彈出開始菜單的問題問題 向日葵是一款遠程控制的應用&#xff0c;在macOS下也能運行&#xff0c; 本來用的好好的&#xff0c;有一天升級后突然就運行不起來了&#xff0c;一點開能顯示幾秒首界面&#xff0c;立馬就自動退…

Linux dma-buf 框架原理、實現與應用詳解

1. 背景與意義 1.1 異構系統與緩沖區共享的挑戰 在現代 SoC、嵌入式、圖形和多媒體系統中&#xff0c;CPU、GPU、VPU、ISP、DMA 控制器等多個硬件單元需要高效地共享和傳遞大塊數據&#xff08;如圖像幀、視頻流、AI 張量等&#xff09;。如果每個設備都維護獨立的緩沖區&…

Scikit-learn Python機器學習 - 分類算法 - 樸素貝葉斯

鋒哥原創的Scikit-learn Python機器學習視頻教程&#xff1a; https://www.bilibili.com/video/BV11reUzEEPH 課程介紹 ? 本課程主要講解基于Scikit-learn的Python機器學習知識&#xff0c;包括機器學習概述&#xff0c;特征工程(數據集&#xff0c;特征抽取&#xff0c;特…

如何免費股票數據API(第13期):滬深A股《最新分時交易》數據獲取大全:附Python、Java等多語言實戰教程與接口文檔說明

在金融科技迅猛發展的今天&#xff0c;股票量化分析以其嚴謹的科學性和強大的系統性&#xff0c;正日益成為投資領域的主流方法論。任何卓越的量化模型的誕生&#xff0c;都離不開全面、精準、及時的數據支撐。無論是躍動著的實時交易數據、沉淀了歷史規律的K線走勢&#xff0c…

國標GB28181視頻EasyGBS視頻監控平臺:一網聯全城,交通道路可視化、視頻巡檢、應急指揮“三合一”。

一、方案背景?人車暴漲&#xff0c;路口告急&#xff1a;高峰堵、事故慢、取證難&#xff0c;老辦法已拖不動城市交通。破局之道&#xff0c;先看攝像頭——EasyGBS 嚴格遵循 GB28181 國標&#xff0c;一站式完成直播、存儲、檢索、轉碼&#xff0c;把萬千路口秒級搬上云端&am…

單元測試(白盒測試方法)

一、單元測試1.單元測試是對軟件的基本組成單元進行的測試&#xff0c;如函數、類或類的方法。單元測試是對軟件的最小可測試單元&#xff08;即可獨立編譯或匯編的程序模塊&#xff09;進行的測試活動&#xff0c;也稱為模塊測試二、白盒測試方法實例代碼public static int te…

2010-2022 同等學力申碩國考:軟件工程簡答題真題匯總

2010年簡答題 給出數據流圖的定義&#xff0c;并舉例說明數據流圖的四個基本構成成份。 數據流圖&#xff08;Data Flow Diagram, DFD&#xff09;是一種用于描述系統中數據流動和處理過程的圖形工具。它通過直觀的方式展示了系統的輸入數據如何經過一系列處理變換為輸出數據&a…

海外盲盒APP開發:如何用技術重構“驚喜經濟”

當盲盒的神秘感遇上技術的確定性&#xff0c;一場關于消費體驗的革命正在海外市場悄然發生。從概率算法的公平性到AR虛擬開箱的沉浸感&#xff0c;從跨境物流的實時追蹤到多語言支持的無縫切換&#xff0c;海外盲盒APP的開發是一場技術、設計與商業邏輯的深度融合。概率算法&am…

Aosp13 手機sim卡信號格顯示修改

工作中&#xff0c;客戶要求對信號格顯示偏弱不夠友好為由&#xff0c;提出修改&#xff0c;要求使其顯示信號強一些。在此記錄 一問題&#xff1a;修改系統sim卡顯示的信號格&#xff0c;在設備其他配置不變的情況下&#xff0c;使其信號格顯示比原有的要優秀二 …

硬件開發2-匯編2(ARMv7-A)- 裸機開發

一、指令1、b&#xff08;Branch&#xff09;原型&#xff1a;B<c> <label>作用&#xff1a;實現無條件跳轉&#xff0c;常用于不返回的跳轉場景特點&#xff1a;僅跳轉到目標地址&#xff0c;不保存返回地址示例&#xff1a;b reset ;跳轉到reset標號處執…

清源 SCA 社區版更新(V4.2.0)|漏洞前置感知、精準修復、合規清晰,筑牢軟件供應鏈安全防線!

隨著數字化進程加速&#xff0c;軟件供應鏈安全威脅日益復雜&#xff0c;公開漏洞響應滯后、0day 攻擊防不勝防、組件升級編譯失敗、安全與合規風險混雜......這些痛點讓企業安全團隊、運維人員及研發團隊疲于應對。自 2025 年 7 月 1 日安勢清源 SCA 社區版首次正式發布以及在…

氚燃料增殖里程碑:MIT新型BABY包層技術實驗驗證

● 導語 5月20日&#xff0c;麻省理工學院&#xff08;MIT&#xff09;發文稱&#xff0c;BABY實驗首次獲取了氚在裝置內增殖的實測數據&#xff0c;驗證了核心模型&#xff0c;并為未來核聚變電廠的燃料自循環奠定了重要基礎。 原文&#x1f447;&#x1f3fb; https://m…

python+springboot+uniapp微信小程序題庫系統 在線答題 題目分類 錯題本管理 學習記錄查詢系統

目錄技術棧介紹具體實現截圖系統設計研究方法&#xff1a;設計步驟設計流程核心代碼部分展示研究方法詳細視頻演示試驗方案論文大綱源碼獲取/詳細視頻演示技術棧介紹 Django-SpringBoot-php-Node.js-flask 本課題的研究方法和研究步驟基本合理&#xff0c;難度適中&#xff0…

Office轉PDF轉換器v1.0.py

軟件介紹 這是批量將word、Excel、PPT轉換為PDF格式的軟件&#xff0c;不過PPT轉換為PDF需要電腦安裝了office&#xff0c;目前這個我還沒有解決沒有office也可以安裝的方法。 軟件使用 軟件使用是比較簡單的&#xff0c;導入文件/文件夾&#xff0c;在自定義輸出路徑 點擊這…

62_基于深度學習的海洋垃圾檢測識別系統(yolo11、yolov8、yolov5+UI界面+Python項目源碼+模型+標注好的數據集)

目錄 項目介紹&#x1f3af; 功能展示&#x1f31f; 一、環境安裝&#x1f386; 環境配置說明&#x1f4d8; 安裝指南說明&#x1f3a5; 環境安裝教學視頻 &#x1f31f; 二、數據集介紹&#x1f31f; 三、系統環境&#xff08;框架/依賴庫&#xff09;說明&#x1f9f1; 系統環…

深入淺出 全面剖析消息隊列(Kafka,RabbitMQ,RocketMQ 等)

消息隊列 一、概念 消息隊列&#xff08;MQ&#xff09;&#xff1a;一種異步通信機制&#xff0c;通過“消息”的形式讓不同系統或模塊解耦核心思想&#xff1a;發送方&#xff08;生產者Producer&#xff09;只負責發送消息&#xff0c;接收方&#xff08;消費者Consumer&…