目錄

棧的概念

畫圖理解棧

棧的實現

fun.h

fun.c

main.c

---

棧的概念

棧（Stack）是一種基本的數據結構，其特點是只允許在同一端進行插入和刪除操作，這一端被稱為棧頂。遵循后進先出（Last In, First Out, LIFO）原則，即最后存入棧中的元素最先被取出。形象地講，棧就像是生活中堆放盤子的架子，我們總是把新的盤子放在最上面，而需要拿盤子時也是從最上面開始拿。

生活中就有棧的一些例子比如這些圖片：

棧的基本操作包括：

1. 壓棧（Push）：向棧頂添加一個元素。相當于在堆疊的頂部放入一個新的物品。
2. 出棧（Pop）：從棧頂移除一個元素，并可選擇返回這個元素。這類似于從堆疊頂部移走最上面的物品。
3. 查看棧頂元素（Peek/Top）：獲取棧頂的元素但不移除它，用于檢查或獲取棧頂的信息。
4. 判斷棧是否為空（IsEmpty）：檢查棧中是否有元素。
5. 獲取棧的大小（Size）：返回棧中元素的數量
6. 

---

畫圖理解棧

首先我們棧有一個原理:先進后出，后進先出，于是我們得得到這么個圖

---

開始壓棧,壓棧的同時我們的p指針也要同時往后面走

---

最總

---

出棧

---

依次出棧后

這里為什么會1 2 3 4壓棧出棧后變成了4321？

其實正確的壓棧出棧我們需要邊壓棧邊出棧就不會出現這種情況了，所以我main函數中是這樣寫的

int main1() {Stack p;STInit(&p);//初始化棧StackPush(&p, 1);//壓棧StackPop(&p);//出棧printf("%d\n", p.a[p.top]);StackPush(&p, 2);StackPop(&p);printf("%d\n", p.a[p.top]);StackPush(&p, 3);StackPop(&p);printf("%d\n", p.a[p.top]);	
}

棧的實現

接下來我們用代碼實現棧，這里我用了三個文件,解析都在注釋中

fun.h

這個文件里有我實現了棧的一些功能

#pragma once
//頭文件
#include<stdlib.h>
#include<stdbool.h>
#include<stdio.h>
#include<assert.h>typedef int STDataType;
//棧的結構
typedef struct Stack
{STDataType* a;//指針int top;//棧頂int capacity;//容量
}Stack;// 初始化棧 
void StackInit(Stack* ps);
// 入棧 
void StackPush(Stack* ps, STDataType data);
// 出棧 
void StackPop(Stack* ps);
// 獲取棧頂元素 
STDataType StackTop(Stack* ps);
// 獲取棧中有效元素個數 
int StackSize(Stack* ps);
// 檢測棧是否為空，如果為空返回非零結果，如果不為空返回0 
bool StackEmpty(Stack* ps);
// 銷毀棧 
void StackDestroy(Stack* ps);

fun.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"fun.h"//擴容函數
void Exp(Stack* p) {if (p->capacity == p->top){//利用三目運算來判斷是否int New_cap = p->capacity == 0 ? 4 : p->capacity * 2;STDataType* tmp = (STDataType*)realloc(p->a, New_cap * sizeof(STDataType));if (tmp == NULL){assert("realloc");return;}//將開辟空間給給原來的變量p->a = tmp;p->capacity = New_cap;}
}//初始化
void StackInit(Stack* p) {assert(p);p->a = NULL;p->capacity = p->top = 0;
}
// 入棧 
void StackPush(Stack* p, STDataType data){assert(p);//判斷空間Exp(p);//入棧p->a[p->top] = data;//入棧后棧頂向上移動p->top++;
}
//出棧
void StackPop(Stack* p) {assert(p);assert(p->top > 0);//確保不為空//判斷是否元素是否為0,避免越界 /*if (p->top == 0){return;}*/p->top--;
}
// 獲取棧頂元素 
STDataType StackTop(Stack* p) {//判斷是否為0if (p->top == 0){return (STDataType)0;//由于返回類型是 STDataType，所以需要強制轉換}return p->a[p->top - 1];
}
// 獲取棧中有效元素個數 
int StackSize(Stack* p) {return p->top;}
//判空
bool StackEmpty(Stack* p) {// 使用邏輯非操作符(!)來檢查棧頂指針(top)是否為0（即棧是否為空）// 如果top為0，說明棧中沒有任何元素，因此棧是空的// 在C語言中，邏輯非操作符會將0轉換為1（true），非0轉換為0（false）// 所以當棧頂指針top為0時，!p->top的結果為true（非零值），表示棧為空// 反之，如果棧中有元素（top非0），則!p->top的結果為false（0），表示棧非空return !p->top;
}
// 銷毀棧 
void StackDestroy(Stack* p) {if (p->a){free(p->a);p->a = NULL;p->capacity = p->top = 0;}
}

main.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"fun.h"
//
//int main1() {
//	Stack p;
//	STInit(&p);
//	StackPush(&p, 1);
//	StackPop(&p);
//	printf("%d\n", p.a[p.top]);
//	StackPush(&p, 2);
//	StackPop(&p);
//	printf("%d\n", p.a[p.top]);
//	StackPush(&p, 3);
//	StackPop(&p);
//	printf("%d\n", p.a[p.top]);
//	
//	
//}int main() { Stack s1;StackInit(&s1);StackPush(&s1, 1);StackPush(&s1, 2);printf("棧中元素個數：%d個\n", StackSize(&s1));while (!StackEmpty(&s1)){printf("%d\n", StackTop(&s1));StackPop(&s1);}printf("棧中元素個數：%d個", StackSize(&s1));StackDestroy(&s1);
}

這個數據結構比較簡單，里面的很多方法，都是和順序表差不多，不懂得鐵鐵可以去看一下我前面的博客

數據結構：順序表-CSDN博客文章瀏覽閱讀838次，點贊18次，收藏9次。數據是計算機科學中的基本概念，它代表了在計算機程序中處理的一切信息內容。https://blog.csdn.net/2302_78381559/article/details/137435691這邊可能你還是不是很理解棧，我們可以試著做一道Leetcode的題，來感受一下棧

題的鏈接

20. 有效的括號 - 力扣（LeetCode）https://leetcode.cn/problems/valid-parentheses/description/

我對這道題理解之后寫的一篇博客，供大家觀看

20. 有效的括號 - 力扣（LeetCode）https://leetcode.cn/problems/valid-parentheses/description/