企业官网建设流程全解析

个人网站 备案 广告,网页广告图片,网站快速收录技术,苏州广告公司十强C stack 全面解析与实战指南 在C标准模板库#xff08;STL#xff09;中#xff0c;stack#xff08;栈#xff09;是一种遵循“后进先出”#xff08;LIFO, Last In First Out#xff09;规则的容器适配器。它并非独立的容器#xff0c;而是基于其他基础容器#xff…C stack 全面解析与实战指南在C标准模板库STL中stack栈是一种遵循“后进先出”LIFO, Last In First Out规则的容器适配器。它并非独立的容器而是基于其他基础容器如deque、vector、list封装实现屏蔽了部分基础容器的接口仅暴露符合栈逻辑的操作。stack在日常开发中应用广泛例如表达式求值、函数调用栈模拟、括号匹配等场景。本文将从stack的底层实现出发详细讲解其核心特性、常用接口结合实战案例演示具体用法并梳理使用注意事项帮助大家彻底掌握这一基础容器适配器。一、stack 核心原理与特性要理解stack的行为逻辑首先需要明确其“容器适配器”的本质——它不直接管理内存而是复用基础容器的内存管理和核心操作仅对外提供统一的栈操作接口。1.1 底层实现基于基础容器的适配stack的底层默认依赖deque容器实现C标准推荐大部分编译器默认如此。这是因为deque支持高效的尾部插入/删除操作push_back、pop_back且内存分配灵活能很好地匹配栈的核心需求。同时C也支持指定其他符合要求的基础容器需支持push_back、pop_back、back、empty、size这5个核心接口例如vector、list等。stack的适配逻辑非常简单将栈的“压栈”对应基础容器的push_back尾部插入“出栈”对应基础容器的pop_back尾部删除“栈顶元素访问”对应基础容器的back访问尾部元素。通过这种适配屏蔽了基础容器的头部操作、随机访问等接口严格保证“后进先出”的规则。1.2 核心特性总结后进先出LIFO最后插入的元素最先被访问仅允许在栈顶进行插入和删除操作容器适配器不独立管理内存依赖基础容器默认deque实现核心功能接口受限仅暴露栈相关接口压栈、出栈、访问栈顶、判空、获取大小不支持迭代器遍历无法直接访问栈中间的元素高效操作压栈push、出栈pop、访问栈顶top的时间复杂度均为O(1)依赖基础容器的尾部操作效率无默认初始化元素创建空stack时无默认元素需手动压栈添加元素。1.3 支持的基础容器stack可指定的基础容器需满足“支持尾部插入/删除、访问尾部元素、判空、获取大小”这5个核心接口STL中符合要求的容器有3个基础容器适配优势适用场景deque默认尾部插入/删除效率高内存分配灵活无vector扩容时的大量数据拷贝开销大多数通用场景推荐默认使用vector内存连续缓存命中率高尾部操作效率稳定栈元素数量稳定无需频繁扩容的场景list尾部插入/删除效率高无扩容开销元素插入不会导致迭代器失效但stack不支持迭代器栈元素数量波动大需频繁插入/删除的场景指定基础容器的语法示例#includestack#includevector#includelist// 基于vector的stackstd::stackint,std::vectorintstack_vec;// 基于list的stackstd::stackint,std::listintstack_list;// 基于默认deque的stack最常用std::stackintstack_deque;}二、C stack 常用接口详解stack的接口设计简洁直观仅包含与栈逻辑相关的核心操作。使用stack前需包含头文件stack并使用std命名空间或显式指定std::stack。2.1 构造与析构接口原型功能说明示例stack();默认构造函数创建空stack基础容器也为空std::stack s;explicit stack(const Container cont);用已有的基础容器对象cont初始化stackstack的元素与cont一致std::deque d{1,2,3}; std::stack s(d);stack(const stack other);拷贝构造函数创建一个与other内容完全相同的stackstd::stack s1; s1.push(1); std::stack s2(s1);~stack();析构函数释放基础容器的资源-2.2 核心操作压栈、出栈、访问栈顶这是stack最常用的接口直接对应栈的核心逻辑接口功能说明注意事项时间复杂度push(const value_type val)将val压入栈顶调用基础容器的push_backval会被拷贝/移动到容器中O(1)emplace(Args… args)在栈顶直接构造元素调用基础容器的emplace_back避免拷贝效率高于pushO(1)pop()删除栈顶元素调用基础容器的pop_back不返回被删除的元素栈为空时调用会导致未定义行为O(1)top()返回栈顶元素的引用调用基础容器的back栈为空时调用会导致未定义行为可通过top()修改栈顶元素若元素非constO(1)2.3 容量相关接口功能说明示例empty()判断栈是否为空调用基础容器的empty空返回true否则返回falseif (s.empty()) { … }size()返回栈中元素的个数调用基础容器的sizecout “栈大小” s.size();2.4 赋值操作接口原型功能说明示例stack operator(const stack other);拷贝赋值将other的内容赋值给当前stack覆盖原有内容s1 s2; // s1的内容变为s2的内容stack operator(stack other) noexcept;移动赋值将other的内容移动到当前stackother变为空s1 std::move(s2); // 高效转移资源2.5 接口综合示例#includestack#includeiostreamusingnamespacestd;intmain(){// 1. 构造空stack默认deque为基础容器stackints;// 2. 压栈操作s.push(10);s.push(20);s.emplace(30);// 直接构造效率更高cout栈大小s.size()endl;// 输出3cout栈顶元素s.top()endl;// 输出30最后压入的元素// 3. 修改栈顶元素非const情况下s.top()35;cout修改后栈顶元素s.top()endl;// 输出35// 4. 出栈操作s.pop();cout出栈后栈顶元素s.top()endl;// 输出20cout出栈后栈大小s.size()endl;// 输出2// 5. 判空与清空stack无clear接口需通过pop循环清空while(!s.empty()){cout出栈元素s.top()endl;s.pop();}cout清空后栈是否为空(s.empty()?是:否)endl;// 输出是// 6. 拷贝构造与赋值stackints1;s1.push(1);s1.push(2);stackints2(s1);// 拷贝构造couts2栈顶元素s2.top()endl;// 输出2stackints3;s3s1;// 拷贝赋值couts3栈大小s3.size()endl;// 输出2return0;}输出结果栈大小3 栈顶元素30 修改后栈顶元素35 出栈后栈顶元素20 出栈后栈大小2 出栈元素20 出栈元素10 清空后栈是否为空是 s2栈顶元素2 s3栈大小2三、stack 实战案例stack的“后进先出”特性使其在多个经典场景中不可或缺以下通过3个实战案例演示其实际应用3.1 场景1括号匹配验证需求给定一个只包含括号‘(’、‘)’、‘{’、‘}’、‘[’、‘]’的字符串判断字符串中的括号是否完全匹配左右括号类型一致、顺序正确、无多余括号。思路遍历字符串遇到左括号‘(’、‘{’、‘[’时将其压入栈中遇到右括号时判断栈是否为空为空则无匹配的左括号返回false或栈顶左括号与当前右括号类型不匹配返回false若匹配则弹出栈顶左括号遍历结束后栈需为空否则存在未匹配的左括号返回false否则返回true。#includestack#includeiostream#includestring#includeunordered_mapusingnamespacestd;boolisValid(string s){// 定义右括号到左括号的映射unordered_mapchar,charbracketMap{{),(},{},{},{],[}};stackcharst;for(charc:s){// 遇到右括号if(bracketMap.count(c)){// 栈为空或栈顶左括号不匹配if(st.empty()||st.top()!bracketMap[c]){returnfalse;}// 匹配成功弹出栈顶左括号st.pop();}else{// 遇到左括号压入栈中st.push(c);}}// 遍历结束后栈需为空无未匹配的左括号returnst.empty();}intmain(){string s1()[]{};string s2(];string s3([)];string s4{[]};couts1 是否有效(isValid(s1)?是:否)endl;// 是couts2 是否有效(isValid(s2)?是:否)endl;// 否couts3 是否有效(isValid(s3)?是:否)endl;// 否couts4 是否有效(isValid(s4)?是:否)endl;// 是return0;}3.2 场景2逆波兰表达式求值需求逆波兰表达式后缀表达式是一种不含括号的表达式运算符位于两个操作数之后计算规则简单。给定一个逆波兰表达式的字符串数组求其结果假设表达式合法仅包含数字和、-、*、/四种运算符除法向下取整。思路遍历字符串数组遇到数字时将其转换为整数压入栈中遇到运算符时弹出栈顶两个元素注意先弹出的是右操作数后弹出的是左操作数计算两个操作数与运算符的结果将结果压入栈中遍历结束后栈中仅剩一个元素即为表达式的结果。#includestack#includeiostream#includevector#includestringusingnamespacestd;intevalRPN(vectorstringtokens){stackintst;for(conststringtoken:tokens){// 遇到运算符if(token||token-||token*||token/){// 弹出两个操作数注意顺序先弹右操作数后弹左操作数intrightst.top();st.pop();intleftst.top();st.pop();// 计算结果并压栈if(token){st.push(leftright);}elseif(token-){st.push(left-right);}elseif(token*){st.push(left*right);}elseif(token/){// 除法向下取整C中负数除法需注意此处按题目要求处理st.push(left/right);}}else{// 遇到数字转换为整数压栈st.push(stoi(token));}}// 栈中仅剩结果returnst.top();}intmain(){vectorstringtokens1{2,1,,3,*};// 等价于 (21)*3 9vectorstringtokens2{4,13,5,/,};// 等价于 4 (13/5) 6vectorstringtokens3{10,6,9,3,,-11,*,/,*,17,,5,};// 等价于 ((10*(6/(93*-11)))17)5 22cout表达式1结果evalRPN(tokens1)endl;// 9cout表达式2结果evalRPN(tokens2)endl;// 6cout表达式3结果evalRPN(tokens3)endl;// 22return0;}3.3 场景3模拟函数调用栈需求模拟程序的函数调用过程记录函数的调用顺序和返回顺序函数调用时压栈函数返回时出栈。#includestack#includeiostream#includestringusingnamespacestd;// 模拟函数调用压栈voidcallFunction(stackstringcallStack,conststringfuncName){callStack.push(funcName);cout调用函数funcNameendl;}// 模拟函数返回出栈voidreturnFunction(stackstringcallStack){if(callStack.empty()){cout无正在执行的函数无法返回endl;return;}string funcNamecallStack.top();callStack.pop();cout返回函数funcNameendl;}intmain(){stackstringcallStack;// 模拟函数调用流程callFunction(callStack,main());callFunction(callStack,funcA());callFunction(callStack,funcB());returnFunction(callStack);// funcB返回callFunction(callStack,funcC());returnFunction(callStack);// funcC返回returnFunction(callStack);// funcA返回returnFunction(callStack);// main返回returnFunction(callStack);// 无函数可返回return0;}输出结果调用函数main() 调用函数funcA() 调用函数funcB() 返回函数funcB() 调用函数funcC() 返回函数funcC() 返回函数funcA() 返回函数main() 无正在执行的函数无法返回四、stack 使用注意事项栈为空时禁止调用pop()和top()stack的pop()和top()接口在栈为空时调用会导致未定义行为程序崩溃或异常。因此在调用这两个接口前必须通过empty()判断栈是否为空。stack无迭代器无法遍历stack的设计初衷是严格遵循LIFO规则因此未暴露迭代器接口无法直接遍历栈中的所有元素。若需遍历需通过pop()将元素依次弹出并记录但会清空栈或自定义基于基础容器的栈结构。stack无clear()接口清空需手动循环pop()与vector、deque等容器不同stack未提供clear()接口。若需清空栈需通过while循环调用pop()直到栈为空。选择合适的基础容器默认的deque基础容器适用于大多数场景兼顾效率和灵活性若栈元素数量稳定无需频繁扩容可选择vector作为基础容器内存连续缓存命中率高若需频繁插入/删除且元素数量波动大可选择list作为基础容器无扩容开销。top()返回的是引用可修改栈顶元素stack的top()返回栈顶元素的非const引用因此可以通过top()修改栈顶元素的值。若需禁止修改可使用const stack。元素类型需支持拷贝/移动stack的push()接口会拷贝/移动元素到基础容器中因此元素类型必须支持拷贝构造或移动构造。若元素为自定义类型需确保正确实现拷贝/移动语义。线程安全性与所有STL容器一致stack不保证线程安全。多线程环境下并发读写栈时需手动加锁如使用std::mutex保护栈的操作。五、总结stack是C STL中基于基础容器封装的“后进先出”容器适配器核心优势是接口简洁、操作高效压栈、出栈、访问栈顶均为O(1)。它不独立管理内存而是复用deque、vector、list等基础容器的功能严格屏蔽了非LIFO相关的接口确保数据操作的规范性。stack的经典应用场景包括括号匹配、表达式求值、函数调用栈模拟等掌握其核心接口和使用注意事项能帮助我们快速解决这类“后进先出”相关的问题。使用时需注意调用pop()和top()前先判空、无迭代器无法遍历、清空需手动循环pop()等细节避免出现未定义行为。希望本文能帮助大家彻底理解并掌握stack的使用如果有疑问或补充欢迎在评论区留言