栈的深度解析与C++实现-程序员充电站

栈的深度解析与C++实现

一、什么是栈？

栈（Stack）是一种遵循**后进先出（LIFO, Last In First Out）**原则的线性数据结构。想象一下往木桶里放苹果，最后放进去的苹果，会最先被取出来——栈的操作逻辑就和这个场景完全一致。

栈有两个核心操作：

入栈（Push）：将元素添加到栈的顶端（栈顶）；
出栈（Pop）：将栈顶的元素移除；

此外，栈通常还会提供top()操作（获取栈顶元素，不删除）、empty()操作（判断栈是否为空）、size()操作（获取栈中元素个数）等辅助接口。

栈的应用场景非常广泛，比如：

函数调用栈：保存函数调用时的上下文信息；
表达式求值：处理四则运算、括号匹配等；
回溯算法：比如迷宫求解、子集问题等；

二、栈的C++实现方案

在C++中，实现栈主要有两种方式：

基于数组（静态数组/动态数组）实现；
基于链表实现；

其中，基于动态数组（vector）的实现方式最为高效且易用，因为vector的尾插（push_back）和尾删（pop_back）操作都是O(1)时间复杂度，完美匹配栈的入栈和出栈需求。下面我们将重点实现这种方式，同时也会简单介绍链表实现的思路。

2.1 基于vector的栈实现

我们将封装一个模板类Stack，支持任意数据类型的存储，核心接口包括：push、pop、top、empty、size。

完整代码实现

#include<iostream>#include<vector>#include<stdexcept>// 用于抛出异常// 栈的模板类实现（基于vector）template<typenameT>classStack{private:std::vector<T>data;// 用vector存储栈元素public:// 入栈：将元素添加到栈顶voidpush(constT&val){data.push_back(val);}// 出栈：移除栈顶元素（注意：空栈出栈需处理）voidpop(){if(empty()){throwstd::runtime_error("Stack is empty, cannot pop!");}data.pop_back();}// 获取栈顶元素（空栈访问需处理）T&top(){if(empty()){throwstd::runtime_error("Stack is empty, no top element!");}returndata.back();}// 常量版本top，适配常量对象constT&top()const{if(empty()){throwstd::runtime_error("Stack is empty, no top element!");}returndata.back();}// 判断栈是否为空boolempty()const{returndata.empty();}// 获取栈中元素个数size_tsize()const{returndata.size();}// 清空栈voidclear(){data.clear();}};// 测试代码intmain(){try{Stack<int>intStack;// 测试入栈intStack.push(10);intStack.push(20);intStack.push(30);std::cout<<"栈的大小："<<intStack.size()<<std::endl;// 输出3std::cout<<"栈顶元素："<<intStack.top()<<std::endl;// 输出30// 测试出栈intStack.pop();std::cout<<"出栈后栈顶元素："<<intStack.top()<<std::endl;// 输出20std::cout<<"出栈后栈的大小："<<intStack.size()<<std::endl;// 输出2// 测试清空栈intStack.clear();std::cout<<"清空后栈是否为空："<<(intStack.empty()?"是":"否")<<std::endl;// 输出是// 测试空栈出栈（会抛出异常）intStack.pop();}catch(conststd::exception&e){std::cerr<<"异常信息："<<e.what()<<std::endl;// 输出"Stack is empty, cannot pop!"}// 测试字符串类型的栈Stack<std::string>strStack;strStack.push("Hello");strStack.push("Stack");std::cout<<"字符串栈顶元素："<<strStack.top()<<std::endl;// 输出"Stack"return0;}

代码说明

模板类设计：使用模板template <typename T>让栈支持任意数据类型（int、string、自定义对象等）；
底层存储：采用std::vector作为底层容器，利用其动态扩容特性，无需手动管理内存；
异常处理：为空栈调用pop()或top()时，抛出std::runtime_error异常，避免程序崩溃；
常量安全：提供常量版本的top()方法，确保常量对象也能访问栈顶元素；

2.2 基于链表的栈实现（简单思路）

基于链表实现栈时，通常选择头插法实现入栈，头删法实现出栈（因为链表头部操作的时间复杂度是O(1)）。核心思路：

定义链表节点结构，包含数据域和指针域；
栈类中维护一个指向链表头部的指针（栈顶指针）；
入栈：创建新节点，将新节点的指针指向当前栈顶，再更新栈顶指针为新节点；
出栈：保存栈顶节点的指针，更新栈顶指针为下一个节点，删除保存的节点；

链表实现的优点是无需预先分配内存，缺点是需要额外存储指针域，且实现稍显繁琐。如果对内存灵活性要求不高，优先选择基于vector的实现。

三、C++标准库中的栈（std::stack）

C++标准库已经为我们提供了栈的实现——std::stack，它定义在<stack>头文件中。std::stack是一个容器适配器，默认基于std::deque实现（也可以指定为vector或list）。

3.1 std::stack的基本使用

#include<iostream>#include<stack>#include<vector>intmain(){// 默认基于deque的栈std::stack<int>s1;s1.push(1);s1.push(2);std::cout<<"s1栈顶："<<s1.top()<<std::endl;// 2s1.pop();std::cout<<"s1栈顶："<<s1.top()<<std::endl;// 1// 指定基于vector的栈std::stack<int,std::vector<int>>s2;s2.push(10);s2.push(20);std::cout<<"s2栈大小："<<s2.size()<<std::endl;// 2return0;}

3.2 std::stack的接口说明

push(const T& val)：入栈；
pop()：出栈（无返回值，若需获取栈顶元素，需先调用top()）；
top()：获取栈顶元素；
empty()：判断栈是否为空；
size()：获取栈的大小；

注意：std::stack不支持直接遍历，这是因为栈的设计初衷就是限制访问方式，只允许操作栈顶元素，符合LIFO原则。

四、栈的常见问题实战

问题1：括号匹配问题

题目：给定一个只包含 ‘(’、‘)’、‘{’、‘}’、‘[’、‘]’ 的字符串，判断字符串是否有效（有效括号需满足：左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合）。

思路：利用栈的LIFO特性，遍历字符串时，遇到左括号则入栈；遇到右括号时，判断栈顶元素是否为对应的左括号，若是则出栈，否则无效。遍历结束后，栈必须为空（所有左括号都被匹配）。

基于std::stack的实现代码：

#include<iostream>#include<stack>#include<unordered_map>#include<string>boolisValid(std::string s){std::stack<char>st;// 存储右括号对应的左括号std::unordered_map<char,char>map={{')','('},{'}','{'},{']','['}};for(charc:s){if(map.count(c)){// 遇到右括号if(st.empty()||st.top()!=map[c]){// 栈空或不匹配returnfalse;}st.pop();// 匹配成功，出栈}else{// 遇到左括号，入栈st.push(c);}}returnst.empty();// 所有左括号必须被匹配}intmain(){std::cout<<isValid("()")<<std::endl;// 1（有效）std::cout<<isValid("()[]{}")<<std::endl;// 1（有效）std::cout<<isValid("(]")<<std::endl;// 0（无效）std::cout<<isValid("([)]")<<std::endl;// 0（无效）std::cout<<isValid("{[]}")<<std::endl;// 1（有效）return0;}