每日一题·栈在括号匹配中的应用

C++（直接用 std::stack）

给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true

示例 5：

输入：s = "([)]"

输出：false

提示：

• 1 <= s.length <= 104
• s仅由括号'()[]{}'组成

1 不同语言实现栈的方式

例如：

用c语言手动实现一个顺序栈：

#include <stdio.h> #define MAX 100 // 手动定义栈结构 int stack[MAX]; int top = -1; // 手动实现压栈 void push(int val) { if(top < MAX-1) stack[++top] = val; } // 手动实现弹栈 int pop() { return top >=0 ? stack[top--] : -1; } // 手动实现查栈顶 int peek() { return top >=0 ? stack[top] : -1; } int main() { push(10); push(20); printf("%d\n", peek()); // 20 printf("%d\n", pop()); // 20 return 0; }

C++（直接用 std::stack）

#include <iostream> #include <stack> using namespace std; int main() { stack<int> st; // 直接定义栈 st.push(10); st.push(20); cout << st.top() << endl; // 20（查栈顶） st.pop(); // 弹栈（无返回值） return 0; }

简单说：std::stack=C++ 标准库提供的栈容器适配器。

std::stack本身不直接存储数据，而是套在其他基础容器（比如std::deque/std::vector）外面的一层 “壳”：

• 它屏蔽了基础容器的大部分功能（比如随机访问、遍历）；
• 只开放栈的核心操作：push()（压栈）、pop()（弹栈）、top()（取栈顶）、empty()（判空）；
• 强制遵循 “后进先出” 规则，保证栈的纯粹性。

那么C++，具体是如何实现这层“壳”的？

要理解std::stack这层 “壳” 的实现，核心是组合复用 + 接口封装—— 它内部持有一个基础容器对象，把栈的操作转发给这个容器的对应方法，同时屏蔽容器的其他无关接口。

std::stack的实现本质非常简单，C++ 标准库中的源码简化后长这样（去掉模板细节和兼容代码）：

// 底层容器默认用 std::deque template <typename T, typename Container = std::deque<T>> class stack { private: // 核心：内部持有一个基础容器对象（真正存数据的地方） Container c; // 屏蔽容器的其他接口：私有继承/只暴露栈相关方法 public: // 1. 压栈 → 转发给容器的 push_back（往容器尾部加元素） void push(const T& value) { c.push_back(value); } // 2. 弹栈 → 转发给容器的 pop_back（删除容器尾部元素） void pop() { c.pop_back(); } // 3. 取栈顶 → 转发给容器的 back（获取容器尾部元素） T& top() { return c.back(); } // 4. 判空 → 转发给容器的 empty bool empty() const { return c.empty(); } // 5. 获取大小 → 转发给容器的 size size_t size() const { return c.size(); } };

“壳” 的实现核心：3 个关键动作

1. 内部持有基础容器（数据交给别人存）

std::stack类里只定义了一个私有成员变量Container c（比如std::deque<int> c），所有数据都存在这个c里 ——stack自己不碰数据存储，只做 “中间商”。

2. 操作转发（只开放栈需要的接口）

栈的核心操作（push/pop/top），本质是调用基础容器的尾部操作：

表格

比如你写st.push(10)，实际执行的是st.c.push_back(10)（c是内部的deque对象）；你写st.top()，实际拿的是st.c.back()。

3. 屏蔽无关接口（保证栈的纯粹性）

std::stack把基础容器的其他方法（比如deque的front()/insert()/erase()、vector的[]下标访问）全部屏蔽：

• 要么把容器对象c设为私有成员（外部无法直接访问）；
• 要么用私有继承（继承容器但不暴露父类接口）；最终效果：你只能调用stack提供的push/pop/top等栈方法，无法直接操作底层容器，保证栈 “后进先出” 的规则不被破坏。

Java（用 Deque 替代 Stack）

import java.util.Deque; import java.util.ArrayDeque; public class Main { public static void main(String[] args) { Deque<Integer> stack = new ArrayDeque<>(); // 推荐写法 stack.push(10); stack.push(20); System.out.println(stack.peek()); // 20（查栈顶） System.out.println(stack.pop()); // 20（弹栈并返回） } }

• C：无任何封装，需自己处理边界（栈空 / 栈满），否则会数组越界崩溃；
• C++：pop()只弹栈不返回值，查栈顶必须用top()，栈空调用top()/pop()会崩溃；
• Java：
  • 千万别用java.util.Stack（继承 Vector，能破坏栈规则）；
  • ArrayDeque性能远高于LinkedList，优先用；
  • pop()会返回栈顶元素，栈空调用抛异常，peek()栈空返回 null

Java对栈的实现

ArrayDeque是Java 官方推荐的栈实现方式，核心是用双端队列（Deque）模拟栈（只操作队列头部）。

1. 两种主流实现类（底层不同）

2. 底层实现逻辑（以ArrayDeque为例）

ArrayDeque是栈的最优选择，底层是动态扩容的循环数组：

• 维护两个指针（head/tail），栈的push()本质是往head位置插入元素；
• pop()是删除head位置元素，peek()是获取head位置元素；
• 数组满了自动扩容（翻倍），时间复杂度都是 O (1)。

Java 和 C++ 的栈实现，底层逻辑可追溯到 C 语言的基础数据结构思想。

2 题解

class Solution { public boolean isValid(String s) { // Java 推荐用 Deque + ArrayDeque 实现栈（替代废弃的 Stack 类） Deque<Character> stack = new ArrayDeque<>(); // 遍历字符串，逻辑和 C++ 完全一致 for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); // C++ 的 s[i] 对应 Java 的 charAt(i) // 左括号压栈 if (c == '(' || c == '[' || c == '{') { stack.push(c); } else { // 右括号校验 // 栈空直接返回 false（无匹配的左括号） if (stack.isEmpty()) { return false; } // 校验括号是否匹配 if (c == ')' && stack.peek() != '(') { return false; } if (c == ']' && stack.peek() != '[') { return false; } if (c == '}' && stack.peek() != '{') { return false; } // 匹配成功，弹出栈顶 stack.pop(); } } // 遍历结束后栈空，说明所有括号都匹配 return stack.isEmpty(); } }

class Solution { public: bool isValid(string s) { stack<int> st; for(int i = 0; i < s.size(); i++){ if (s[i] == '(' || s[i] == '[' ||s[i] == '{') st.push(s[i]); else { if(st.empty()) return false; if(s[i] == ')' && st.top()!= '(') return false; if(s[i] == ']' && st.top()!= '[') return false; if(s[i] == '}' && st.top()!= '{') return false; st.pop(); } } return st.empty(); } };