前言
嗨，我们又见面了(✪ω✪)，相信大家已经学完顺序表和链表的相关知识，接下来我们又要迎接新的朋友——栈和队列，它和顺序表、链表、数组一样都属于线性表结构。今天我们主要介绍栈，让我们去了解它吧！
一、栈的概念栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。相关操作压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。出栈：栈的删除操作叫做出栈。出数据也在栈顶。
以下是相关操作图片展示，方便大家理解。
栈操作过程 简单类比：栈就像叠盘子，先放的在最底下，最后放的在最上面，拿的时候也得从最上面先拿，完美契合“后进先出”。
二、 栈的实现方式栈的实现一般可以使用数组或者链表实现
栈的逻辑结构为线性的，而栈的物理结构由二选择的方式所决定
对比项
数组实现的栈（顺序栈）
链表实现的栈（链栈）
存储方式
用连续的数组空间存储元素，通过栈顶指针标记栈顶位置
用链表节点（每个节点含数据域和指针域）存储元素，栈顶对应链表头节点
空间效率
若数组预分配空间过大，会造成空间浪费；若空间不足，会触发“栈溢出”
空间动态分配，无预分配浪费，但每个节点有指针域开销
时间效率
入栈（Push）、出栈（Pop）、查看栈顶（Peek）均为O(1)；支持数组的随机访问（但栈逻辑不常用）
入栈、出栈、查看栈顶均为O(1)；不支持随机访问
扩容/溢出
数组容量固定，满栈后无法再入栈（栈溢出），需手动扩容（如重新申请更大数组并拷贝元素）
无栈溢出风险，元素数量可动态增长，只需不断创建新节点即可
适用场景
适合元素数量已知或范围可控、追求存取效率的场景（如括号匹配、表达式求值）
适合元素数量不确定、需要灵活扩容的场景（如函数调用栈的动态管理）
实现复杂度
实现较简单，只需维护数组和栈顶指针
需处理链表节点的指针操作，实现稍复杂（但逻辑清晰）
通过这个表格相信大家一定有自己的判断了，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。所以下面我们通过数组来实现栈。
三、 栈的实现 下面通过Stack.h通过声明，Stack.c来实现功能，test.c来进行测试
开始前的操作（头文件）栈的实现主要通过初始化、销毁、入栈、出栈、取栈顶数据、判空、获取数据个数等方式来实现，这里先通过写头文件来先确定实现框架，后面就不进行重复展示了
头文件Stack.h
代码语言：javascript复制#pragma once
#include
#include
#include
#include
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;//栈顶
int capacity;//栈的空间大小
}ST;
// 初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);
// 入栈 出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
// 取栈顶数据
STDataType STTop(ST* pst);
// 判空
bool STEmpty(ST* pst);
// 获取数据个数
int STSize(ST* pst);1、初始化Stack.c
代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
// 初始化
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
// top指向栈顶数据的下一个位置
pst->top = 0;
// top指向栈顶数据
//pst->top = -1;
pst->capacity = 0;
}注意这里top如果初始化为0，代表指向栈顶的下一个元素=元素个数，如果初始化为-1，就代表指向栈顶元素=元素个数-1,以下是两种方式的图示，更方便大家理解
两种都可以，这里我用top=0来进行操作
test.c
代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void cm()
{
ST oj;
STInit(&oj);//初始化
}
int main()
{
cm();
return 0;
}2、栈的销毁在一系列操作之后，一定是要销毁的，以下是栈的销毁，和初始化相似
Stack.c
代码语言：javascript复制// 销毁栈（释放栈占用的内存，重置栈状态）
void STDestroy(ST* pst)
{
assert(pst); // 确保栈指针pst不为空（防止传入空指针导致的非法访问）
free(pst->a); // 释放栈的底层数组空间（数组是栈存储元素的实际载体）
pst->a = NULL;// 将数组指针置空，避免野指针（防止后续误访问已释放的内存）
pst->top = pst->capacity = 0; // 重置栈顶指针和容量为0，标记栈已销毁（逻辑上清空栈）
}test.c
代码语言：javascript复制#include"Stack.h"
void cm()
{
ST oj;
STInit(&oj);//初始化
STDestroy(&oj);//栈的销毁
}
int main()
{
cm();
return 0;
}3、入栈由于只能从栈顶插入，由于我们通过数组实现，也就相当于在数组尾部插入数据，还需要判断是否空间满，扩容操作，因为top初始化为0，执行判断top与capacity是否相等就可以了，如下
Stack.c
代码语言：javascript复制// 向栈中插入元素（入栈操作）
// pst：指向栈结构的指针，x：要插入的元素值
void STPush(ST* pst, STDataType x)
{
assert(pst); // 确保栈指针pst不为空（防止对空指针解引用，避免程序崩溃）
// 检查栈是否已满（栈顶指针等于容量时，无法直接插入，需先扩容）
if (pst->top == pst->capacity)
{
// 计算新容量：若初始容量为0（栈为空），则初始化为4；否则容量翻倍（高效扩容策略，减少频繁扩容开销）
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
// 重新分配内存：用realloc扩容底层数组，新大小为newcapacity个STDataType类型元素
STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
if (tmp == NULL) // 检查内存分配是否失败（如内存不足）
{
perror("realloc fail"); // 打印错误信息（如"realloc fail: Out of memory"）
return; // 分配失败则无法入栈，直接返回
}
pst->a = tmp; // 更新栈的底层数组指针为新分配的内存
pst->capacity = newcapacity; // 更新栈的容量为新容量
}
// 将元素x放入栈顶位置（当前top指向的索引是下一个可插入位置）
pst->a[pst->top] = x;
pst->top++; // 栈顶指针上移一位，指向新的可插入位置（栈大小+1）
}4、出栈出栈比较简单，只需要把指向栈顶下一个元素的top(也就是元素个数）-1就行了
如下
Stack.c
代码语言：javascript复制// 从栈中移除栈顶元素（出栈操作）
// pst：指向栈结构的指针
void STPop(ST* pst)
{
assert(pst); // 确保栈指针pst不为空（防止对空指针解引用，避免程序崩溃）
assert(pst->top > 0); // 确保栈不为空（top > 0表示栈中有元素），避免对空栈执行出栈操作
pst->top--; // 栈顶指针减一：通过移动栈顶指针，使原栈顶元素不再被栈包含，实现出栈（无需实际删除元素内存，后续入栈会覆盖）
}5、取栈顶元素因为我们top初始化为0指向栈顶的下一个元素，所以取的是top-1
Stack.c
代码语言：javascript复制// 获取栈顶元素的值（仅查看，不删除栈顶元素）
// pst：指向栈结构的指针，返回值为栈顶元素的数据（类型为STDataType）
STDataType STTop(ST* pst)
{
assert(pst); // 确保栈指针pst不为空（防止对空指针解引用，避免程序崩溃）
assert(pst->top > 0); // 确保栈不为空（top > 0表示栈中有元素），避免访问空栈的"栈顶"（会导致数组越界）
// 返回栈顶元素：栈顶指针top指向"下一个可插入位置"，因此当前栈顶元素的索引为top - 1
return pst->a[pst->top - 1];
}测试结合上面我们来测试一下，避免错误
先初始化，再入栈，取栈顶元素打印，再出栈，再打印，最后销毁
test.c
代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h" // 包含栈的头文件，其中定义了栈的结构体(ST)及相关操作函数（初始化、入栈、出栈等）
// 测试栈的各种操作的函数
void cm()
{
ST oj; // 定义栈实例（ST为栈结构体类型，oj为具体的栈变量）
STInit(&oj); // 初始化栈：为栈分配初始空间，设置栈顶指针和容量初始值（如top=0，capacity=0或初始大小）
// 入栈操作：向栈中压入元素2和1（栈遵循LIFO，此时栈中元素从底到顶为[2,1]，栈顶是1）
STPush(&oj, 2);
STPush(&oj, 1);
// 取栈顶元素并打印：此时栈顶是1，输出"1 "
printf("%d ", STTop(&oj));
// 出栈操作：移除栈顶元素1（栈中剩余元素[2]，栈顶变为2）
STPop(&oj);
// 取栈顶元素并打印：此时栈顶是2，输出"2 "
printf("%d ", STTop(&oj));
// 继续入栈：压入3和5（栈中元素从底到顶为[2,3,5]，栈顶是5）
STPush(&oj, 3);
STPush(&oj, 5);
// 取栈顶元素并打印：此时栈顶是5，输出"5 "
printf("%d ", STTop(&oj));
// 销毁栈：释放栈底层数组占用的内存，重置栈顶指针和容量为0，避免内存泄漏
STDestroy(&oj);
}
int main()
{
cm(); // 调用测试函数，执行栈的各项操作
return 0;
}结果为，正确
在这里插入图片描述6、判空这里只需要判断top是否为0就行啦，代码如下
Stack.c
代码语言：javascript复制// 判空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}7、获取元素个数因为top指的也是元素个数，所以返回top的值就行啦
Stack.c
代码语言：javascript复制// 获取数据个数
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}8、最后测试代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void cm()
{
ST oj;
STInit(&oj);
STPush(&oj, 2);
STPush(&oj, 1);
printf("%d ", STTop(&oj));
STPop(&oj);
printf("%d ", STTop(&oj));
STPush(&oj, 3);
STPush(&oj, 5);
printf("%d ", STTop(&oj));
STPop(&oj);
STPop(&oj);
int a=STEmpty(&oj);
if (a == 0)
{
printf("空\n");
}
else
{
printf("非空\n");
}
STPop(&oj);
a = STEmpty(&oj);
if (a == 0)
{
printf("空\n");
}
else
{
printf("非空\n");
}
STDestroy(&oj);
}
int main()
{
cm();
return 0;
}结果为，证明正确
在这里插入图片描述9、总代码Stack.h
代码语言：javascript复制#pragma once
#include
#include
#include
#include
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
// 初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);
// 入栈 出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
// 取栈顶数据
STDataType STTop(ST* pst);
// 判空
bool STEmpty(ST* pst);
// 获取数据个数
int STSize(ST* pst);Stack.c
代码语言：javascript复制#include"Stack.h"
// 初始化和销毁
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
// top指向栈顶数据的下一个位置
pst->top = 0;
// top指向栈顶数据
//pst->top = -1;
pst->capacity = 0;
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
// 入栈 出栈
void STPush(ST* pst, STDataType x)
{
assert(pst);
// 扩容
if (pst->top == pst->capacity)
{
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;
pst->top++;
}
void STPop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
// 取栈顶数据
STDataType STTop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
return pst->a[pst->top - 1];
}
// 判空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
// 获取数据个数
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}test.c
代码语言：javascript复制#include"Stack.h"
void cm()
{
ST oj;
STInit(&oj);
STPush(&oj, 2);
STPush(&oj, 1);
printf("%d ", STTop(&oj));
STPop(&oj);
printf("%d ", STTop(&oj));
STPush(&oj, 3);
STPush(&oj, 5);
printf("%d ", STTop(&oj));
STPop(&oj);
STPop(&oj);
int a=STEmpty(&oj);
if (a == 0)
{
printf("空\n");
}
else
{
printf("非空\n");
}
STPop(&oj);
a = STEmpty(&oj);
if (a == 0)
{
printf("空\n");
}
else
{
printf("非空\n");
}
STDestroy(&oj);
}
int main()
{
cm();
return 0;
}四、栈的应用（相关算法题）题目链接有效的括号
思路这题可以通过栈来实现左括号入栈，判断右括号与前一个左括号（利用取栈顶元素）是否匹配
方法1：我们已经写出来栈的实现，就可以以它作为模板，复制粘贴利用，我们再定义bool类型的函数，利用上面思路，匹配出栈，不匹配直接错误，最后判断是否为空，为空正确，非空错误
参考代码：
代码语言：javascript复制#include
#include
#include
#include
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->top = 0;
pst->capacity = 0;
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
void STPush(ST* pst, STDataType x)
{
assert(pst);
if (pst->top == pst->capacity)
{
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;
pst->top++;
}
void STPop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
STDataType STTop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
return pst->a[pst->top - 1];
}
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
bool isValid(char* s)
{
ST st1;
STInit(&st1);
while (*s)
{
if (*s == '(' || *s == '[' || *s == '{')
{
STPush(&st1, *s);
}
else
{
if (STEmpty(&st1))
{
STDestroy(&st1);
return false;
}
char ret = STTop(&st1);
if ((ret == '(' && *s != ')')
|| (ret == '[' && *s != ']')
|| (ret == '{' && *s != '}'))
{
STDestroy(&st1);
return false;
}
STPop(&st1);
}
s++;
}
if (STEmpty(&st1))
{
STDestroy(&st1);
return true;
}
STDestroy(&st1);
return false;
}方法2：与前面思路一样，只是利用栈的思想来实现,直接利用数组遍历字符串，遇到左括号（( [ {）就将其压入栈中暂存；遇到右括号时，检查栈顶是否有对应的左括号 —— 若栈为空（无左括号可匹配）或类型不匹配，直接判定为无效；若匹配，则弹出栈顶左括号（完成一对匹配）。遍历结束后，若栈为空，说明所有左括号都被对应右括号匹配，字符串有效；反之，存在未匹配的左括号，字符串无效。
代码如下
代码语言：javascript复制bool isValid(char* s)
{
char st[1000005]; // 栈数组，存储左括号
int t = 0; // 栈顶指针（t=0 表示栈空，t的值即栈中元素数量）
for (int i = 0; s[i]; i++) { // 遍历字符串中的每个字符
if (s[i] == '(' || s[i] == '[' || s[i] == '{')
{
st[t++] = s[i]; // 左括号入栈，栈顶指针上移
} else
{
if (t == 0)
{ // 栈空却遇到右括号，无匹配左括号 → 无效
return false;
}
// 检查右括号与栈顶左括号是否匹配
if ((s[i] == ')' && st[t-1] == '(') ||
(s[i] == ']' && st[t-1] == '[') ||
(s[i] == '}' && st[t-1] == '{')) {
t--; // 匹配成功，栈顶左括号出栈
} else {
return false; // 类型不匹配 → 无效
}
}
}
return t == 0; // 遍历结束后栈为空 → 所有括号匹配，否则存在未匹配左括号
}相似题目牛客上的相似题目，几乎一样，大家可以尝试
链接括号序列
其中一种如下
代码语言：javascript复制上面是对方法1的调用，这里忽略不写了
int main()
{
char arr[1000001];
scanf("%s", arr);
int a = isValid(arr);
if (a != 0)
{
printf("Yes\n");
}
else
printf("No\n");
return 0;
}另一种和方法2一样，只是稍作修改，这里就不展示了
总结本章到这里就结束啦(▽)，介绍了栈的实现方式和应用题目，希望大家有所收获，下一节我们就要介绍队列啦，敬请期待，本文有写的不好的地方希望大家提出，我会积极改正，感谢大家的支持！