顺序栈（动态数组实现） 超详细解析（C++ 语言 + 可直接运行）

前言栈Stack是一种 ** 后进先出LIFO, Last In First Out的线性数据结构。它只允许在一端栈顶** 进行插入、删除操作另一端栈底封闭。栈的应用场景极广函数调用栈表达式求值计算器括号匹配浏览器前进后退操作系统中断现场保护一、顺序栈是什么顺序栈 用动态数组实现的栈特点底层是连续内存空间支持自动扩容避免溢出访问、插入、删除效率极高O(1)实现简单、稳定、不易出错二、顺序栈结构体设计及支持的操作#pragma once #includestdio.h typedef char ELEM_TYPE; // 数据类型可改为 int/double 等 #define INITSIZE 10 // 初始容量 // 顺序栈结构体 struct Seq_Stack { ELEM_TYPE* base; // 动态数组起始地址 int top; // 栈顶指针下标 int stacksize; // 当前总容量 }; typedef struct Seq_Stack Seq_Stack; typedef struct Seq_Stack* PSeq_Stack; // 1. 初始化 void Init_Stack(Seq_Stack* ps); // 2. 入栈 bool Push(Seq_Stack* ps, ELEM_TYPE val); // 3. 出栈 bool Pop(Seq_Stack* ps); // 4. 获取栈顶元素 ELEM_TYPE Top(Seq_Stack* ps); // 5. 判空 bool Is_Empty(Seq_Stack* ps); // 6. 判满 bool Is_Full(Seq_Stack* ps); // 7. 扩容 static void Inc(Seq_Stack* ps); // 8. 获取长度 int Get_Length(Seq_Stack* ps); // 9. 清空 void Clear(Seq_Stack* ps); // 10. 销毁释放内存 void Destroy(Seq_Stack* ps); // 11. 打印 void Show(Seq_Stack* ps);结构说明base指向动态分配的数组top始终指向下一个可入栈的位置top 0→ 空栈top stacksize→ 栈满stacksize当前数组总容量可扩容三、核心函数逐行精讲最关键1. 初始化//初始化 void Init_Stack(Seq_Stack* ps) { assert(ps ! NULL); // 分配初始容量 ps-base (ELEM_TYPE*)malloc(INITSIZE * sizeof(ELEM_TYPE)); if (ps-base NULL) exit(1); ps-top 0; ps-stacksize INITSIZE; }作用申请内存、设置栈空、容量初始化。2. 入栈Pushbool Push(Seq_Stack* ps, ELEM_TYPE val) { assert(ps ! NULL); // 满了就扩容 2 倍 if (Is_Full(ps)) Inc(ps); ps-base[ps-top] val; ps-top; return true; }时间复杂度O(1)自动扩容永不溢出3. 出栈Popbool Pop(Seq_Stack* ps) { assert(ps ! NULL); if (Is_Empty(ps)) return false; ps-top--; return true; }出栈不删除数据只移动栈顶指针高效4. 获取栈顶元素TopELEM_TYPE Top(Seq_Stack* ps) { assert(ps ! NULL); if (Is_Empty(ps)) exit(1); return ps-base[ps-top - 1]; }5. 扩容函数Incstatic void Inc(Seq_Stack* ps) { assert(ps ! NULL); ELEM_TYPE* tmp (ELEM_TYPE*)realloc(ps-base, 2 * ps-stacksize * sizeof(ELEM_TYPE)); if (tmp ! NULL) ps-base tmp; ps-stacksize * 2; }自动扩容为原来的 2 倍避免频繁申请内存。6. 清空栈void Clear(Seq_Stack* ps) { assert(ps ! NULL); ps-top 0; }不释放内存只置空。7. 销毁栈//销毁 需要free void Destroy(Seq_Stack* ps) { assert(ps ! NULL); free(ps-base); ps-base NULL; ps-top ps-stacksize 0; }必须销毁防止内存泄漏。8. 打印栈void Show(Seq_Stack* ps) { assert(ps ! NULL); for (int i 0; i ps-top ; i) { cout ps-base[i] ; } cout endl; }9. 判空、判满、获取有效长度值//判空 bool Is_Empty(Seq_Stack* ps) { return ps-top 0; } //判满 bool Is_Full(Seq_Stack* ps) { return ps-top ps-stacksize; } //获取有效长度值 int Get_Length(Seq_Stack* ps) { assert(ps ! NULL); return ps-top; }四、测试主函数可直接运行#define _CRT_SECURE_NO_WARNINGS #includeiostream #includeassert.h #includestdlib.h #include顺序栈.h using namespace std; int main() { Seq_Stack head; Init_Stack(head); Push(head, A); Push(head, B); Push(head, C); Show(head); cout 长度 Get_Length(head) endl; cout 栈顶元素 Top(head) endl; Pop(head); Show(head); return 0; }运行结果五、顺序栈特点总结连续内存访问速度快O (1) 入栈、出栈、取栈顶动态扩容不会溢出实现简单、稳定无野指针、无内存泄漏六、高频考点必背栈的特点是什么后进先出LIFO。顺序栈和链式栈区别顺序栈连续内存、速度快、需扩容链式栈离散内存、不用扩容、速度稍慢顺序栈扩容为什么是 2 倍减少扩容次数平衡时间与空间。top 指针的含义指向下一个可入栈的位置。清空和销毁的区别清空只置空不释放内存销毁释放所有内存时间复杂度入栈、出栈、取栈顶O(1)