網站首頁 編程語言 正文
前言
前一段時間，我們試著用C語言實現了數據結構中的順序表，單鏈表，雙向循環鏈表。今天我們再用C語言來實現另一種特殊的線性結構：棧
一. 什么是棧
棧（stack）又名堆棧，它是一種運算受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。
類似于步槍的子彈夾，后進去的子彈先發射出來以后，前面的子彈才可以發射。
二. 使用什么來實現棧
前一段時間，我們學習了兩種線性表，一種是順序表，一種是鏈表，那么對于棧我們該用哪一個來實現比較好呢
首先我們來對比一下線性表和鏈表
| 不同點 | 順序表 | 鏈表 |
|---|---|---|
| 存儲空間上 | 物理上一定連續 | 邏輯上連續，但物理上不一定連續 |
| 隨機訪問 | 可以直接訪問任何元素 | 必須從頭節點開始往后尋找 |
| 任意位置插入或刪除元素 | 要搬移其他的元素，效率低。 | 只需要修改節點的指針指向，效率高 |
| 插入 | 動態順序表，當空間不夠時需要擴容 | 無容量概念，需要就申請，不用就釋放 |
| 應用場景 | 元素高效存儲，并且需要頻繁訪問 | 需要在任意位置插入或者刪除頻繁 |
綜合以上來看，我認為實現一個棧，使用順序表比較好。
1.棧是先進后出，使用順序表，在元素出棧后更容易找到新的棧頂。
2.順序表CPU高速緩存命中率高，可以減少CPU去內存拿數據的次數，速度快，效率高。
三. 棧的實現
3.1 頭文件
1.包含的標準庫
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> //C語言中的bool類型需要這個頭文件
#include <assert.h>
2.定義結構體
typedef int STDateType;//棧中元素的數據類型
typedef struct Stack
{
STDateType* a; //順序表
int top; //棧頂
int capacity; //棧的容量
}Stack;
3.函數的聲明
void StackInti(Stack* ps);
// 棧的初始化
void StackDestory(Stack* ps);
// 棧的銷毀
void StackPush(Stack* ps, STDateType x);
// 入棧
void StackPop(Stack* ps);
// 出棧
bool StackEmpty(Stack* ps);
// 判斷棧是否為空
STDateType StackTop(Stack* ps);
// 取棧頂元素
3.2 函數實現
1. 棧的初始化
我們用assert（斷言），防止ps為空指針。
void StackInti(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
2. 棧的銷毀
釋放順序表。
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->a);
ps->capacity = 0;
ps->top = 0;
}
3.入棧
void StackPush(Stack* ps, STDateType x)
{
assert(ps);
if (ps->top == ps->capacity) //判斷容量是否足夠
{
int newCapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
ps->a = (int*)realloc(ps->a, sizeof(int) * newCapcity);
if (ps->a == NULL)
{
printf("ralloc error");
exit(-1);
}
ps->capacity = newCapcity;
}
ps->a[ps->top] = x;
ps->top++;
}
4. 出棧
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0); //空棧不能被刪除
ps->top--;
}
5. 判斷棧是否為空
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0; // 如果為空則返回true，否則返回false
}
6. 取棧頂元素
STDateType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);//空棧不能被刪除
return ps->a[ps->top - 1];
}
這樣我們就實現了一個簡單的棧
3.3 完整代碼
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int STDateType;
typedef struct Stack
{
STDateType* a;
int top;
int capacity;
}Stack;
void StackInti(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->a);
ps->capacity = 0;
ps->top = 0;
}
void StackPush(Stack* ps, STDateType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newCapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
ps->a = (int*)realloc(ps->a, sizeof(int) * newCapcity);
if (ps->a == NULL)
{
printf("ralloc error");
exit(-1);
}
ps->capacity = newCapcity;
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
STDateType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
四. 棧的用處
我們好不容易實現了一個棧，接下來我們來做個題看看棧有什么用吧。
題目描述
給定一個只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判斷字符串是否有效。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
基礎框架
C語言的基礎框架如下
bool isValid(char * s){
???????}
解題思路
左括號一定要和右括號對齊，非常滿足棧的特性
我們可以將所有的左括號存入一個棧中。
然后遇到右括號，就出棧，判斷是否匹配。
直到棧為空且字符串中的括號也遍歷完了，那么所有括號就正確的匹配了。
代碼詳解
// 1.因為C語言并沒有現成的棧，所以我們需要自己造輪子，先寫個棧再說
typedef char STDateType; // 更改數據類型為char
typedef struct Stack
{
STDateType* a;
int top;
int capacity;
}Stack;
void StackInti(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->a);
ps->capacity = 0;
ps->top = 0;
}
void StackPush(Stack* ps, STDateType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newCapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
ps->a = (int*)realloc(ps->a, sizeof(int) * newCapcity);
if (ps->a == NULL)
{
printf("ralloc error");
exit(-1);
}
ps->capacity = newCapcity;
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
STDateType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
bool isValid(char * s){
Stack a;
StackInti(&a);
while(*s)
{
if (*s == '(' || *s == '[' || *s == '{') //入棧
{
StackPush(&a, *s);
}
else //出棧
{
if(StackEmpty(&a)) //右括號多一個的情況
{
return false;
}
char tmp = StackTop(&a);
StackPop(&a);
if ((*s == ')' && tmp != '(')
||(*s == ']' && tmp != '[')
||(*s == '}' && tmp != '{') )
{
return false;
}
}
s++;
}
return StackEmpty(&a); //防止出現多一個左括號的情況
}
原文鏈接：https://blog.csdn.net/m0_60447315/article/details/123726501
- 上一篇：在WPF中實現全局快捷鍵功能_C#教程
- 下一篇：C語言實現隊列的示例詳解_C 語言
相關推薦
- 2023-07-25 SpringBoot整合Mybatis詳解
- 2023-04-18 spark?dataframe全局排序id與分組后保留最大值行_python
- 2022-04-03 Python?Flask?+?Redis?程序練習_python
- 2022-05-11 C++程序代碼優化的方法實例大全_C 語言
- 2022-04-22 element的el-drawer預留操作欄問題
- 2022-09-24 ASP.NET?MVC實現路由功能_實用技巧
- 2022-08-26 一篇文章學會GO語言中的變量_Golang
- 2022-06-16 Python數據結構之遞歸可視化詳解_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加速