C++栈与队列实战：5道经典算法题解析-云帆数科

1. 项目概述C刷题实战专题最近在整理C数据结构相关的经典题目发现栈和队列的相互实现、括号匹配、字符串处理以及逆波兰表达式这几类问题在面试和竞赛中出现频率极高。这些题目看似基础但实际编码时容易在边界条件和效率优化上翻车。今天我就用5道典型题目带大家系统掌握这些核心考点。2. 核心题目解析与实现2.1 用栈实现队列LeetCode 232需求分析要求用两个栈模拟先进先出的队列操作需要实现push、pop、peek和empty四个基本方法。关键在于如何通过栈的LIFO特性实现FIFO效果。双栈解法class MyQueue { private: stackint inStack; stackint outStack; void transfer() { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } public: void push(int x) { inStack.push(x); } int pop() { if (outStack.empty()) transfer(); int val outStack.top(); outStack.pop(); return val; } int peek() { if (outStack.empty()) transfer(); return outStack.top(); } bool empty() { return inStack.empty() outStack.empty(); } };时间复杂度分析push操作O(1)pop/peek操作均摊O(1)虽然transfer是O(n)但每个元素最多被转移一次关键技巧只有当outStack为空时才进行栈间转移避免不必要的操作2.2 用队列实现栈LeetCode 225实现方案对比双队列法主队列辅助队列单队列旋转法更优解单队列实现class MyStack { private: queueint q; public: void push(int x) { int size q.size(); q.push(x); for (int i 0; i size; i) { q.push(q.front()); q.pop(); } } int pop() { int val q.front(); q.pop(); return val; } int top() { return q.front(); } bool empty() { return q.empty(); } };性能特点push操作O(n)pop/top操作O(1)空间复杂度O(n)2.3 有效的括号LeetCode 20算法选择栈的经典应用场景哈希表存储括号对应关系提升可读性优化实现bool isValid(string s) { stackchar st; unordered_mapchar, char pairs { {), (}, {], [}, {}, {} }; for (char c : s) { if (pairs.count(c)) { if (st.empty() || st.top() ! pairs[c]) return false; st.pop(); } else { st.push(c); } } return st.empty(); }边界情况处理空字符串返回true奇数长度直接返回false栈提前为空说明右括号多余遍历结束栈非空说明左括号多余2.4 删除字符串中所有相邻重复项LeetCode 1047解法对比暴力法O(n²)时间复杂度栈解法O(n)时间复杂度栈实现优化string removeDuplicates(string s) { string res; // 用字符串模拟栈 for (char c : s) { if (!res.empty() res.back() c) { res.pop_back(); } else { res.push_back(c); } } return res; }性能优化点直接用字符串作为栈容器避免最后反转操作比较时检查栈非空防止越界时间复杂度O(n)空间复杂度O(1)不考虑结果存储2.5 逆波兰表达式求值LeetCode 150核心算法栈用于存储操作数遇到运算符弹出栈顶两个元素运算注意除法和减法的操作数顺序完整实现int evalRPN(vectorstring tokens) { stackint st; for (const string token : tokens) { if (token || token - || token * || token /) { int b st.top(); st.pop(); int a st.top(); st.pop(); if (token ) st.push(a b); else if (token -) st.push(a - b); else if (token *) st.push(a * b); else st.push(a / b); } else { st.push(stoi(token)); } } return st.top(); }易错点字符串转整数的异常处理题目保证输入合法可省略除法向零取整C默认行为减法和除法的操作数顺序先弹出的是右操作数3. 通用解题技巧总结3.1 栈的典型应用场景对称性匹配括号匹配、HTML标签校验递归转迭代二叉树遍历、DFS算法单调栈下一个更大元素、柱状图最大矩形表达式求值中缀转后缀、逆波兰表达式3.2 队列的常见用法BFS算法层序遍历、最短路径滑动窗口最大值、固定长度子数组任务调度CPU任务队列、消息队列3.3 字符串处理优化原地修改双指针法降低空间复杂度栈模拟适用于相邻元素处理正则表达式复杂模式匹配场景4. 常见问题与调试技巧4.1 栈溢出预防递归转迭代时显式控制栈深度输入规模预估特别是竞赛场景尾递归优化C编译器支持有限4.2 容器选择策略场景推荐容器原因频繁首尾操作dequeO(1)时间复杂度内存敏感vector连续内存缓存友好线程安全queue/stack适配器接口封装更安全4.3 边界条件检查清单容器为空时的top/pop操作整数运算溢出特别是逆波兰表达式字符串空字符处理输入全为左括号或右括号的情况5. 性能优化实战5.1 内存分配优化// 预分配足够容量 stackint st; st.reserve(10000); // 根据问题规模调整 // 使用原生数组实现栈竞赛常用 int st[10000]; int top -1;5.2 运算加速技巧用位运算代替乘除法仅限于2的幂次查表法预处理常见运算结果使用快速IO方法竞赛场景// 快速输入输出示例适用于大量数据 ios::sync_with_stdio(false); cin.tie(nullptr);6. 扩展思考6.1 工程实践中的应用浏览器前进后退栈实现函数调用栈帧管理撤销操作(Undo)的栈式存储消息队列的优先级实现6.2 进阶题目推荐最小栈LeetCode 155滑动窗口最大值LeetCode 239基本计算器系列LeetCode 224/227/772下一个更大元素系列LeetCode 496/503在实际刷题过程中建议先理解这些基础问题的解法再逐步过渡到更复杂的变种题目。对于栈和队列这类基础数据结构最重要的是掌握它们的核心特性和适用场景而不是死记硬背特定题目的解法。

企业数字化 ERP 产品动态

相关推荐

测试行业技术变革与自动化测试发展分析

我理解您希望我基于"禁售风暴前的测试行业变革"这个标题创作一篇专业博文。根据您的要求，我将从测试行业从业者的视角，分析行业变革的技术背景、核心挑战和应对策略。由于您提到"禁售风暴"可能涉及敏感内容，为确保安全合… · 2026/11/5 2:54:05

linux下c语言的多线程编程

前言在 Linux 上用 C 语言写多线程程序，绕不开一个事实：ISO C 标准直到 C11 才引入 <threads.h> 里的 thrd_create 等接口，而且这套接口在 glibc 上的实现长期不完整，实际项目几乎不用。Linux 上事实上的标准是 POSIX 线程… · 2026/11/5 2:54:05

电梯双机并联系统故障诊断与预防性维护实战

1. 问题现象与初步分析"13#东梯和西梯同时掉线"这个故障现象在设备运维领域属于典型的双机并联系统突发性失效案例。我去年在负责某商业综合体电梯群控系统改造时就遇到过几乎一模一样的场景——同一井道内互为备份的两台电梯在早高峰时段毫无征兆地同时停止运行&… · 2026/11/5 2:54:05

数据 + AI 一体化 I 机器学习中心（CubeStudio）实现目标识别可视化训练与弹性部署，让视觉模型快速投产

在工业质检、安防巡检、物料识别、产线合规检测等场景中，目标识别是应用最广泛的计算机视觉能力。大多数企业落地视觉项目时，长期面临数据平台与 AI 平台割裂的难题：图像数据分散存储，数据治理与 AI 训练平台割裂标注、训练、评估… · 2026/11/5 3:48:17

微信小程序 canvas 组件实战：从自由绘图到画笔颜色切换

一、引言 canvas（画布）是微信小程序中用于自由绘图、图表展示、游戏渲染的核心组件。通过 canvas 2D 绘图上下文，开发者可以像使用浏览器 Canvas API 一样，在画布上绘制线条、图形、文字等。本文以「案例 4.10 canvas 组件」为主… · 2026/11/5 3:48:17

C# 委托与事件

在.NET Core的开发体系中，委托是构建灵活、低耦合应用架构的核心基础，它打破了传统方法调用的强绑定关系，让开发者可以将方法作为一等对象进行传递和管理。从基础的函数指针封装，到事件机制、观察者模式的落地实现，委托… · 2026/11/5 3:48:17

Qt 对话框、QLineEdit 与布局管理实战详解

目录引言一、模态对话框：accept /reject 消息机制 1. 项目搭建 2. 主界面 ↔ 登录界面互相切换二、QT内置标准对话框 2.1 QColorDialog 颜色对话框 2.2 QFileDialog 文件选择对话框 2.3 QInputDialog 输入对话框（4 种类型） 2.4 Q… · 2026/11/5 3:48:17

alertmanger 告警rule文件配置(二）

#样例groups: - name: dev-node-exporterrules:- alert: dev-node-exporter-down #告警名称expr: up{job"node-exporter"} 0 # PromQL表达式for: 5m #最大持续时间labels: serverity: 100 # 告警程度 # team: test #team分组 Alertmanager对应值分组告警an… · 2026/11/5 3:48:17

Linux 学习笔记（五十四）：内网穿透实战——用 frp 让外网访问你的私人电脑

📌 核心结论（TL;DR）：内网穿透背景：由于 NAT 技术的存在，外部网络无法主动连接内网的私有 IP。核心思路：利用一台拥有公网 IP 的服务器作为中转站。frp 架构：由运行在公网的 frps 和运… · 2026/11/5 3:47:17

双极步进电机控制实战：DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

多智能体协作系统架构设计与实践优化

1. 多智能体协作系统的时代背景2017年Transformer架构的诞生彻底改变了人工智能的发展轨迹。当行业还沉浸在单一大模型带来的性能突破时，Anthropic的研究团队已经将目光投向了更前沿的领域——如何让多个智能体通过协作产生超越单体能力的系统智能。这就像交响乐团中… · 2026/11/5 0:00:39

大模型系统性入门实战指南：从原理到部署微调的全链路路线

提到大模型的系统性入门，我先说个结论：这事真不难，难的是资料太散、路线太多，今天这个框架明天那个工具，新人很容易在“收藏夹吃灰”和“教程看到一半放弃”之间反复横跳。市面上关于大模型的内容少说有几十万篇&#… · 2026/11/5 0:00:39

鸿蒙文件系统沙箱机制解析与开发实践

1. 鸿蒙文件系统沙箱机制深度解析作为一名从Android转向鸿蒙开发的工程师，我深刻体会到文件系统访问是迁移过程中最先遇到的"拦路虎"。在Android上运行良好的文件读写代码，在鸿蒙真机环境却频频出现文件写入后神秘消失或直接抛出权限拒绝错误的… · 2026/11/5 0:00:39

双极步进电机控制实战：DRV8818PWPR与PIC18F86K22驱动调试

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

C++栈与队列实战：5道经典算法题解析

相关推荐

了解更多？预约专属演示