網(wǎng)站首頁 編程語言 正文
前言
棧的概念
- 棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數(shù)據(jù)插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數(shù)據(jù)元素遵守后進先出LIFO（Last In First Out）的原則。有點類似于手槍彈夾，后壓進去的子彈總是最先打出，除非槍壞了。
- 壓棧：棧的插入操作叫做進棧/壓棧/入棧。（入數(shù)據(jù)在棧頂）
- 出棧：棧的刪除操作叫做出棧。（出數(shù)據(jù)也在棧頂）
注意：
1、函數(shù)調(diào)用也有棧，這兩個棧有區(qū)別嗎？
當(dāng)然有區(qū)別。函數(shù)調(diào)用會調(diào)用棧幀，內(nèi)存里頭也有一個棧，程序運行起來時要執(zhí)行函數(shù)，函數(shù)里頭的局部變量、參數(shù)、返回值等等都要存在函數(shù)棧幀里頭。
這兩個棧沒有任何關(guān)聯(lián)，一個是數(shù)據(jù)結(jié)構(gòu)中的棧。另一個是操作系統(tǒng)中內(nèi)存劃分的一個區(qū)域，叫做棧，用來函數(shù)調(diào)用時，建立棧幀。雖然本質(zhì)上沒有任何關(guān)聯(lián)，但都符合后進先出的規(guī)則。
2、假設(shè)入棧順序為：1 2 3 4，那么出棧順序一定為：4 3 2 1 嗎？
當(dāng)然不是。雖說規(guī)則上明確后進先出，可這是相對而言的，如果說它每進一個再出一個，然后再繼續(xù)壓棧，那不同樣符合后進先出的規(guī)則嗎。就如同上例，你說它出棧順序為1 2 3 4 都不足為奇，每進一個出一個再進，同樣符合規(guī)則。類似的入棧兩個再出再進再出也是可以的，好比如2 1 4 3。
棧的結(jié)構(gòu)
棧的實現(xiàn)
創(chuàng)建棧結(jié)構(gòu)
Stack.h 文件：
//創(chuàng)建棧結(jié)構(gòu)
typedef int STDataType;
typedef struct Stack
{
STDataType* a; //存儲數(shù)據(jù)
int top; //棧頂?shù)奈恢?
int capacity; //容量
}ST;初始化棧
思想：
初始化還是相對比較簡單的，學(xué)了之前的順序表，初始化棧就很輕松了
Stack.h 文件：
//初始化棧 void StackInit(ST* ps);
Stack.c 文件：
//初始化棧
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}注意：
???這里初始化的時候?qū)op置為0是有意圖的。首先，由上文創(chuàng)建棧結(jié)構(gòu)時已經(jīng)標注了，top是用來記錄棧頂?shù)奈恢茫热皇菞ｍ數(shù)奈恢茫钱?dāng)top初始化為0時，我們可以直接將數(shù)據(jù)放入棧中，隨后top++，但是當(dāng)top初始化為-1時，top首先要++才能放入數(shù)據(jù)，因為數(shù)據(jù)不可能在負數(shù)不屬于棧的位置上放入。下圖演示過程：
?本文以 top = 0 示例
銷毀棧
思想：
動態(tài)開辟的內(nèi)存空間一定要釋放，free置空即可，并把其余數(shù)據(jù)置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;
}入棧
思路：
前文已經(jīng)強調(diào)了top初始化為0，那么理應(yīng)直接壓入數(shù)據(jù)，并把top++，不過在這之前，得判斷空間是否夠，當(dāng)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;//將數(shù)據(jù)壓進去
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的位置才是棧頂元素，因為在前文初始化的時候已經(jīng)明確指出top為0，當(dāng)時壓棧時直接放入數(shù)據(jù)的，此時第一個數(shù)據(jù)下標為0，隨后++top再壓入其它數(shù)據(jù)，由此可見，棧頂元素即下標top-1的位置。
Stack.h 文件：
//訪問棧頂數(shù)據(jù) STDataType StackTop(ST* ps);
Stack.c 文件：
//訪問棧頂數(shù)據(jù)
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1]; //top-1的位置才為棧頂?shù)脑?
}獲取棧中有效元素個數(shù)
思想：
上文講到下標top-1才是棧頂元素，那么是不是說總共就是top-1個元素呢？當(dāng)然不是，這里跟數(shù)組下標一樣的思想，元素個數(shù)應(yīng)該就是top個，直接返回即可。
Stack.h 文件：
//有效元素個數(shù) int StackSize(ST* ps);
Stack.c 文件：
//有效元素個數(shù)
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}檢測棧是否為空
思路：
當(dāng)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 //創(chuàng)建棧結(jié)構(gòu) typedef int STDataType; typedef struct Stack { STDataType* a; //存儲數(shù)據(jù) int top; //棧頂?shù)奈恢? 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); //訪問棧頂數(shù)據(jù) STDataType StackTop(ST* ps); //有效元素個數(shù) 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;//將數(shù)據(jù)壓進去
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，那么就為真，即返回
}
//訪問棧頂數(shù)據(jù)
STDataType StackTop(ST* ps)
{
assert(ps);
return ps->a[ps->top - 1]; //top-1的位置才為棧頂?shù)脑?
}
//有效元素個數(shù)
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
相關(guān)推薦
- 2022-07-04 python如何使用replace做多字符替換_python
- 2023-03-15 pandas將Series轉(zhuǎn)成DataFrame的實現(xiàn)_python
- 2022-07-01 Python錯誤+異常+模塊總結(jié)_python
- 2022-04-11 C++?std::initializer_list?實現(xiàn)原理解析及遇到問題_C 語言
- 2021-12-09 數(shù)據(jù)庫建表設(shè)計六范式介紹_數(shù)據(jù)庫其它
- 2022-06-20 C語言三種方法解決輪轉(zhuǎn)數(shù)組問題_C 語言
- 2022-07-02 使用Element Plus ＜script lang=“ts“ setup＞ 加上lang=“ts
- 2022-12-03 C++網(wǎng)絡(luò)編程詳細講解_C 語言
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡單動態(tài)字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速