網站首頁 編程語言 正文
前言
棧的概念
- 棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則。有點類似于手槍彈夾，后壓進去的子彈總是最先打出，除非槍壞了。
- 壓棧：棧的插入操作叫做進棧/壓棧/入棧。（入數據在棧頂）
- 出棧：棧的刪除操作叫做出棧。（出數據也在棧頂）
注意：
1、函數調用也有棧，這兩個棧有區別嗎？
當然有區別。函數調用會調用棧幀，內存里頭也有一個棧，程序運行起來時要執行函數，函數里頭的局部變量、參數、返回值等等都要存在函數棧幀里頭。
這兩個棧沒有任何關聯，一個是數據結構中的棧。另一個是操作系統中內存劃分的一個區域，叫做棧，用來函數調用時，建立棧幀。雖然本質上沒有任何關聯，但都符合后進先出的規則。
2、假設入棧順序為：1 2 3 4，那么出棧順序一定為：4 3 2 1 嗎？
當然不是。雖說規則上明確后進先出，可這是相對而言的，如果說它每進一個再出一個，然后再繼續壓棧，那不同樣符合后進先出的規則嗎。就如同上例，你說它出棧順序為1 2 3 4 都不足為奇，每進一個出一個再進，同樣符合規則。類似的入棧兩個再出再進再出也是可以的，好比如2 1 4 3。
棧的結構
棧的實現
創建棧結構
Stack.h 文件：
//創建棧結構
typedef int STDataType;
typedef struct Stack
{
STDataType* a; //存儲數據
int top; //棧頂的位置
int capacity; //容量
}ST;初始化棧
思想：
初始化還是相對比較簡單的，學了之前的順序表，初始化棧就很輕松了
Stack.h 文件：
//初始化棧 void StackInit(ST* ps);
Stack.c 文件：
//初始化棧
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}注意：
???這里初始化的時候將top置為0是有意圖的。首先，由上文創建棧結構時已經標注了，top是用來記錄棧頂的位置，既然是棧頂的位置，那當top初始化為0時，我們可以直接將數據放入棧中，隨后top++，但是當top初始化為-1時，top首先要++才能放入數據，因為數據不可能在負數不屬于棧的位置上放入。下圖演示過程：
?本文以 top = 0 示例
銷毀棧
思想：
動態開辟的內存空間一定要釋放，free置空即可，并把其余數據置0。
Stack.h 文件：
//銷毀棧 void StackDestory(ST* ps);
Stack.c 文件：
//銷毀棧
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}入棧
思路：
前文已經強調了top初始化為0，那么理應直接壓入數據，并把top++，不過在這之前，得判斷空間是否夠，當top=capacity的時候，棧就滿了，那么就需要realloc擴容。
Stack.h 文件：
//壓棧 void StackPush(ST* ps, STDataType x);
Stack.c 文件：
//壓棧
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//如果棧滿了，考慮擴容
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //檢測容量
ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (ps->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->capacity = newcapacity; //更新容量
}
ps->a[ps->top] = x;//將數據壓進去
ps->top++;//棧頂上移
}出棧
思路：
在你出棧之前，要確保top不為空，而top不為空的條件就是top>0，所以還要斷言top>0，隨后，直接將棧頂位置下移--即可。跟順序表的思想大同小異。
Stack.h 文件：
//出棧 void StackPop(ST* ps);
Stack.c 文件：
//出棧
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}獲取棧頂元素
思路：
首先要搞清楚誰才是棧頂元素，是top位置還是top-1位置？很顯然是top-1的位置才是棧頂元素，因為在前文初始化的時候已經明確指出top為0，當時壓棧時直接放入數據的，此時第一個數據下標為0，隨后++top再壓入其它數據，由此可見，棧頂元素即下標top-1的位置。
Stack.h 文件：
//訪問棧頂數據 STDataType StackTop(ST* ps);
Stack.c 文件：
//訪問棧頂數據
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1]; //top-1的位置才為棧頂的元素
}獲取棧中有效元素個數
思想：
上文講到下標top-1才是棧頂元素，那么是不是說總共就是top-1個元素呢？當然不是，這里跟數組下標一樣的思想，元素個數應該就是top個，直接返回即可。
Stack.h 文件：
//有效元素個數 int StackSize(ST* ps);
Stack.c 文件：
//有效元素個數
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}檢測棧是否為空
思路：
當top的值為0時即為空，return直接返回即可
Stack.h 文件：
//判空 bool StackEmpty(ST* ps);
Stack.c 文件：
//判空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0; //如果top為0，那么就為真，即返回
}Test.c 文件：
void TestStack()
{
ST st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
printf("\n");
StackDestory(&st);
}效果如下：
總代碼
Stack.h 文件
#pragma once #include#include #include #include //創建棧結構 typedef int STDataType; typedef struct Stack { STDataType* a; //存儲數據 int top; //棧頂的位置 int capacity; //容量 }ST; //初始化棧 void StackInit(ST* ps); //銷毀棧 void StackDestory(ST* ps); //壓棧 void StackPush(ST* ps, STDataType x); //出棧 void StackPop(ST* ps); //判空 bool StackEmpty(ST* ps); //訪問棧頂數據 STDataType StackTop(ST* ps); //有效元素個數 int StackSize(ST* ps);
Stack.c 文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化棧
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
//銷毀棧
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
//壓棧
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//如果棧滿了，考慮擴容
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //檢測容量
ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (ps->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->capacity = newcapacity; //更新容量
}
ps->a[ps->top] = x;//將數據壓進去
ps->top++;//棧頂上移
}
//出棧
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
//判空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0; //如果top為0，那么就為真，即返回
}
//訪問棧頂數據
STDataType StackTop(ST* ps)
{
assert(ps);
return ps->a[ps->top - 1]; //top-1的位置才為棧頂的元素
}
//有效元素個數
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}Test.c 文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void TestStack()
{
ST st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
printf("\n");
StackDestory(&st);
}
int main()
{
TestStack();
return 0;
}原文鏈接：https://blog.csdn.net/bit_zyx/article/details/123763458
相關推薦
- 2022-08-05 springBoot集成swagger啟動報錯：Failed to start bean ‘docu
- 2022-12-03 React使用ref方法與場景介紹_React
- 2023-05-29 python怎樣判斷一個數值(字符串)為整數_python
- 2022-06-20 Android?Flutter實現點贊效果的示例代碼_Android
- 2022-07-12 for循環中var和let的不為人知的秘密
- 2022-10-06 Python?Numpy中數組的集合操作詳解_python
- 2024-03-22 springboot報錯Error creating bean with name ‘dataSou
- 2022-07-04 PyG搭建GCN模型實現節點分類GCNConv參數詳解_python
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速