Stack栈数据管理-stack.cpp

栈（Stack）数据结构实现

项目概述

本项目使用C++语言，基于单向链表实现了一个完整的栈数据结构。栈是一种后进先出（LIFO，Last In First Out）的线性表，所有操作仅在栈顶一端进行。本项目将栈的底层实现细节完全封装，对外提供简洁、安全的操作接口。

功能模块与API说明

核心操作（O(1)时间复杂度）

· push(int value)：将元素压入栈顶。动态创建新节点，挂接到链表头部，栈顶指针上移，元素个数自增。
· pop()：弹出栈顶元素。保存栈顶节点，栈顶指针指向下一节点，释放原栈顶内存，元素个数自减。若栈为空，输出错误提示。
· top()：返回栈顶元素的值（不删除）。直接读取栈顶节点的数据域。若栈为空，返回-1并输出错误提示。

辅助操作

· isEmpty()：判断栈是否为空。检查栈顶指针是否为nullptr，时间复杂度O(1)。
· size()：返回栈中元素个数。直接返回count成员变量，时间复杂度O(1)。
· clear()：清空栈。循环pop所有节点，释放全部内存，重置栈顶指针和计数器。

资源管理

· 构造函数：初始化栈顶指针为nullptr，计数器归零。
· 析构函数：自动调用clear()释放所有动态分配的内存，确保无内存泄漏。

设计思路

1. 底层存储选择：采用单向链表而非数组实现。链式存储无需预分配空间，可动态扩展；push/pop操作在链表头部进行，时间复杂度稳定为O(1)；无数组扩容时的数据拷贝开销，性能更稳定。
2. 节点完全封装：struct Node定义在Stack类的private区域，对外完全隐藏。用户无法直接访问节点结构或修改next指针，数据安全性更高，且未来可将链表替换为数组或其他底层结构而不影响外部代码。
3. 接口设计原则：只暴露必要的操作接口，不提供遍历或索引访问。符合栈“先进后出”的语义约束，避免用户误用，接口精简、职责单一。

技术实现细节

内存管理

· push操作：使用new动态分配节点内存，无需担心容量上限。
· pop操作：使用delete释放节点内存，防止内存泄漏。
· clear操作：循环释放所有节点，确保析构时完全回收。
· 遵循RAII原则：资源获取即初始化，析构自动释放资源。

异常处理

· pop时栈为空：输出错误信息，不执行删除操作。
· top时栈为空：输出错误信息，返回-1（可选的错误值）。
· 参数合法性检查：push和pop无需检查索引（栈只操作栈顶）。

代码结构

· 头文件（.h）：类定义、接口声明、注释文档。
· 实现文件（.cpp）：成员函数实现、私有辅助方法。
· 测试文件（main.cpp）：功能测试用例，覆盖正常与边界场景。
· 构建脚本（Makefile）：支持make编译、make clean清理。

使用场景示例

· 函数调用栈的底层机制模拟
· 表达式求值（中缀转后缀、后缀表达式计算）
· 括号匹配检测（{[()]}合法性验证）
· 深度优先搜索（DFS）的回溯路径记录
· 浏览器的前进/后退功能
· 撤销/重做操作（Undo/Redo）