目錄
引言
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)—— 即最后入棧的元素會最先被彈出。這種特性類似于日常生活中的 “疊盤子”:最后疊上去的盤子,會被最先拿走。
棧的核心概念
- 入棧(Push):向棧頂添加元素。
- 出棧(Pop):從棧頂移除并返回元素(棧為空時無法出棧)。
- 棧頂(Top):棧中最上方的元素(最后入棧的元素)。
- 棧底(Bottom):棧中最下方的元素(最先入棧的元素)。
- 棧空(Empty):棧中沒有任何元素的狀態。
- 棧的大小(Size):棧中元素的數量。
棧的結構
棧的結構可以抽象為一個 “容器”,元素只能從一端(棧頂)進行插入和刪除操作,另一端(棧底)是固定的。
“后進先出”(Last In, First Out,LIFO):
棧頂(Top):棧頂是棧中最后添加(push)元素的位置,也是最先被移除(pop)或查看(peek/top)的元素所在的位置。在棧的所有操作中,無論是添加、刪除還是查看元素,都是針對棧頂進行的。因此,棧頂是棧中最活躍、最頻繁被訪問的位置。
棧底(Bottom):棧底是棧中最早被添加進去的元素所在的位置,也是棧中唯一一個固定不變的位置(除非整個棧被清空)。在棧的常規操作中,棧底元素不會被直接訪問,除非是將整個棧的內容倒序輸出或者棧被完全清空。因此,棧底在棧的操作中扮演的是一個相對靜態的角色。
壓棧:棧的插入操作叫做進棧/入棧,入數據在棧頂。
出棧:棧的刪除操作叫做出棧,出數據也在棧頂。
-
在計算機領域,棧有著廣泛應用。例如,在編程語言中,函數調用時會使用棧來管理局部變量和返回地址。當一個函數被調用時,其相關的信息(如參數、局部變量等)會被壓入棧中,函數執行完畢后,這些信息會從棧中彈出。此外,表達式求值、括號匹配等問題也常借助棧來解決。
2.棧的實現
2.1棧的實現方式
棧可以通過兩種常見的數據結構實現:
-
數組實現(順序棧)
- 用數組存儲元素,棧頂對應數組的最后一個索引。
- 入棧:在數組尾部添加元素(時間復雜度 O (1))。
- 出棧:刪除數組尾部元素(時間復雜度 O (1))。
- 缺點:數組大小固定,可能出現溢出(需動態擴容)。
-
鏈表實現(鏈式棧)
- 用鏈表的頭節點作為棧頂,每次操作頭節點。
- 入棧:在鏈表頭部插入新節點(時間復雜度 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);}
}
結束語
本篇我們主要介紹了一下棧,接下來我們將接著學習與棧類似的另一個數據結構——隊列。
感謝您的三連支持!!!