栈数据结构详解：从入门到实战

一、栈是什么栈是后进先出 LIFO的线性数据结构。只允许在一端进出栈顶另一端封闭栈底先进去的后出来后进去的先出来生活例子叠盘子、快递纸箱堆叠。二、栈核心操作固定五个基础操作入栈 push栈顶加元素出栈 pop删除栈顶元素取栈顶 top只取值不删除判空 empty是否无元素获取大小 size当前元素个数三、C STL 栈快速使用头文件#include stack using namespace std;基础用法stackint st; st.push(1); st.push(2); st.push(3); // 取栈顶 cout st.top(); // 出栈 st.pop(); // 判空 if(st.empty()){} // 大小 st.size();四、手写数组模拟栈底层原理必会不用 STL纯数组自己实现栈理解底层#include iostream using namespace std; const int MAXN 1000; // 数组模拟栈 struct MyStack { int arr[MAXN]; int top; // 栈顶指针 // 初始化 MyStack() { top -1; } // 入栈 void push(int val) { if(top MAXN - 1) return; arr[top] val; } // 出栈 void pop() { if(!empty()) top--; } // 取栈顶 int getTop() { return arr[top]; } // 判空 bool empty() { return top -1; } // 元素个数 int size() { return top 1; } };五、栈经典算法题有效括号匹配题目描述给定只包含() [] {}的字符串判断括号是否合法左括号必须用相同类型右括号闭合左括号必须以正确顺序闭合解题思路遇到左括号直接入栈遇到右括号栈空 → 直接不合法栈顶不是对应左括号 → 不合法匹配成功 → 出栈遍历结束栈必须为空才合法完整代码#include iostream #include stack #include string using namespace std; bool isValid(string s) { stackchar st; for(char c : s) { // 左括号全部入栈 if(c ( || c [ || c {) { st.push(c); } else { // 右括号但栈空 if(st.empty()) return false; char top st.top(); // 匹配校验 if( (c ) top ! () || (c ] top ! [) || (c } top ! {) ) { return false; } st.pop(); } } // 全部匹配完栈必须为空 return st.empty(); } int main() { string s1 ()[]{}; string s2 ([)]; cout boolalpha isValid(s1) endl; cout boolalpha isValid(s2) endl; return 0; }六、栈常见算法应用场景括号匹配、表达式求值函数递归调用栈底层二叉树非递归遍历单调栈解题下一天精讲浏览器前进后退、撤销操作七、今日易错点搞反栈「后进先出」顺序括号匹配忘记最后判断栈是否为空取栈顶top()前不判空导致程序崩溃手写栈栈顶指针初始值设错八、今日总结栈核心特性后进先出 LIFO掌握 STL stack 快速用法 数组手写栈必会经典题有效括号匹配固定模板栈是单调栈、树非递归遍历的基础