【数据结构指南】栈
前言：
厨房里叠放的盘子想必大家都见过，新洗好的只能放在最顶层，使用时也必须从最上层开始取。羽毛球桶里的羽毛球也是如此，用过的球只能放回顶层，取用时也必须从最上层拿取。这些日常场景里，其实都藏着一种重要的数据结构：栈。
关于栈的一个笑话：从前有一家客栈，客栈有一条规矩：最早进来的人最晚上菜，最晚进来的人最早上菜。有一天，一个人早早来到客栈吃饭，发现一个比他来的还晚的人已经吃完饭走了，而店主还没上自己的菜。吃完饭后他问店主这是为什么，店主回答：“因为我们是客栈啊。
本文系统讲解栈这一数据结构，从基础概念到实际应用进行全面剖析。通过清晰的逻辑和丰富的实例，即使是数据结构初学者也能轻松掌握核心要点。
一、栈的基本概念
1.1栈的定义
栈 (stack) 是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作，其核心特性遵循后进先出原则，这种特性可以形象地类比为叠放盘子的过程：最晚放入的盘子 (后进) 会被最先取出 (先出) ，而最早放入的盘子 (先进) 则最后才能取出 (后出) 。
1.2栈的基础知识
为了方便理解，我们先明确栈的 3 个核心概念：
栈顶（Top）：位于栈的最上层，即最后入栈的元素。所有入栈（push）和出栈（pop）操作都只能在栈顶进行。
栈底（Bottom）：位于栈的最底层，即第一个入栈的元素。这个元素在栈中位置固定，不会轻易变动。
空栈（empty）：没有任何元素的栈状态。此时无法执行出栈操作。
1.3进栈出栈的示意图
进栈（Push）：将元素添加到栈顶
出栈（Pop）：移除并返回栈顶元素
二、栈的实现
2.1栈实现的相关接口
本文通过数组的方式实现栈 ，实现的相关接口如图所示：
2.2栈实现的相关文件
2.3Stack.h文件
Stack.h头文件实现：通过结构体定义栈，声明栈的相关接口函数。
#pragma once #include<stdlib.h> #include<stdio.h> #include<stdbool.h> #include<assert.h> typedef int STDatatype; typedef struct Stack { STDatatype* a; //top表示指向栈顶元素的下一个元素下标 int top; //栈的容量大小 int capacity; }Stack; //初始化和销毁栈 void StackInit(Stack* pst); void StackDestroy(Stack* pst); //元素的入栈和出栈 void Push(Stack* pst,STDatatype x); void Pop(Stack* pst); //获取栈顶元素 STDatatype top(Stack* pst); //获取栈中有效元素个数 int Size(Stack* pst); //判断栈是否为空 bool Empty(Stack* pst);
对于Stack.h头文件主要关注：
typedef int STDatatype; typedef struct Stack { STDatatype* a; //top表示指向栈顶元素的下一个元素下标 int top; //栈的容量大小 int capacity; }Stack;typedef int STDatatype;
把 int 重命名为 STDatatype，方便后续修改栈存储的元素类型（比如想存 char 或结构体，只需改这一行）。
struct Stack
结构体：定义栈的核心结构。
STDatatype* a;
动态数组指针，指向栈的内存空间（存储栈的元素）。
int top;
栈顶标记（注释说明 “指向栈顶元素的下一个元素下标”）。例如：栈空时 top=0；入栈一个元素后，top=1（此时栈顶元素是 a[0]）。
int capacity;
栈的容量（当前分配的内存能存多少个元素），用于判断是否需要扩容。
2.4Stack.c文件
①栈的初始化
void StackInit(Stack* pst) { //断言pst assert(pst); pst->a = NULL; pst->capacity = 0; //指向栈顶元素的下一个元素 pst->top = 0; }
②栈的销毁
//销毁栈 void StackDestroy(Stack* pst) { assert(pst); if (pst->a != NULL) { free(pst->a); pst->a = NULL; } pst->capacity = 0; pst->top = 0; }
③入栈
//元素的入栈 void Push(Stack* pst, STDatatype x) { assert(pst); //判断是否容量足够 if (pst->capacity == pst->top) { //需要进行扩容 int newcapacity =pst->capacity==0? 4 : pst->capacity * 2; STDatatype* tmp = (STDatatype *)realloc(pst->a, newcapacity*sizeof(STDatatype)); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } //进行入栈 pst->a[pst->top++] = x; }
④出栈
//元素的出栈 void Pop(Stack* pst) { assert(pst && pst->top > 0); pst->top--; }
⑤获取栈顶元素
//获取栈顶元素 STDatatype top(Stack* pst) { assert(pst && pst->top > 0); return pst->a[pst->top-1]; }
⑥获取栈中的有效个数
//获取栈中有效元素个数 int Size(Stack* pst) { assert(pst); return pst->top; }
⑦判断栈是否为空
//判断栈是否为空 bool Empty(Stack* pst) { assert(pst); return pst->top == 0; }
2.5Test.c文件
#include"Stack.h" void Test() { Stack st = { 0 }; StackInit(&st); Push(&st, 1); printf("%d\n", top(&st)); Push(&st, 2); printf("%d\n", top(&st)); Push(&st, 3); printf("%d\n", top(&st)); Push(&st, 4); printf("%d\n", top(&st)); printf("当前栈中元素的总个数为：%d\n", Size(&st)); Pop(&st); printf("%d\n", top(&st)); Pop(&st); printf("%d\n", top(&st)); Pop(&st); printf("%d\n", top(&st)); Pop(&st); if (Empty(&st)) printf("当前栈为空\n"); else printf("当前栈不为空\n"); printf("当前栈中元素的总个数为：%d\n", Size(&st)); StackDestroy(&st); } int main() { Test(); return 0; }
三、栈的简单应用
Leetcode链接:有效的括号
3.1题目简介：
3.2题目分析
当开始接触题目时，我们会不禁想到如果计算出左括号的数量，和右括号的数量，如果每种括号左右数量相同，会不会就是有效的括号了呢？
但是左括号和右括号是否匹配还和它的位置相关，例如 " ]][[ " 这样一组案例即使左右括号数量相同，但是位置不满足题目条件。
我们通过仔细分析这样一组测试样例：{ ( ) [ ( ) ] } ，对于有效的括号，它的部分子表达式仍然是有效的括号。
故而可以使用栈来解决，对于左括号压入栈中，通过匹配右括号的方式，删除最小的括号对。
3.3代码示例
class Solution { public: bool isValid(string s) { //创建一个栈结构 stack<char> st; for(int i=0;i<s.length();i++) { //如果是左括号( { [ 进入栈中 if(s[i]=='('|| s[i]=='{' || s[i]=='[') { st.push(s[i]); } else //右括号 { //取出左括号的前提是栈中至少有左括号 if(st.empty()) { return false; } //取出栈顶元素 char ch=st.top(); st.pop(); //栈顶元素的左括号 与 右括号进行匹配 if( (ch=='('&&s[i]!=')') || (ch=='{'&&s[i] !='}') || (ch=='['&&s[i] !=']') ) { return false; } } } //如果遍历完字符串，栈中还有元素，说明左右括号数量不匹配 if(!st.empty()) return false; return true; } };
既然看到这里了，不妨点赞+收藏，感谢大家，若有问题请指正。
