一、栈（Stack）
🌱 栈是一种特殊的线性表，只能在一端进行操作
🌱 往栈中添加元素的操作，一般叫做 push（入栈）
🌱 从栈中移除元素的操作，一般叫做 pop，出栈（只能移除栈顶元素），也叫做：弹出栈顶元素
🌱 后进先出的原则，Last In First Out，LIFO
注意：这里的栈与内存中的栈空间是两个不同的概念
二、利用 ArrayList 实现栈
🌾栈的内部实现可使用动态数组、链表等进行实现
🌾jdk 官方的栈是继承了 Vector 进行实现
🌾Vector 可以理解为是线程安全的动态数组
/** * 利用动态数组实现栈 */ public class Stack<E> { // 通过【组合】的方式使用 ArrayList private final List<E> list = new ArrayList<>(); /** * 获取栈中元素个数 */ public int size() { return list.size(); } /** * 判断栈中是否一个元素都没有（判断是否是一个空栈） */ public boolean isEmpty() { return list.isEmpty(); } /** * 往栈中添加元素（入栈） */ public void push(E element) { list.add(element); } /** * 取出栈顶元素, 并把栈顶元素删除（出栈） * * @return 栈顶元素 */ public E pop() { return list.remove(size() - 1); } /** * 获取栈顶元素内容 */ public E top() { return list.get(size() - 1); } /** * 清空栈 */ public void clear() { list.clear(); } }
测试代码：
public class QQMain { public static void main(String[] args) { Stack<String> stack = new Stack<>(); stack.push("心"); stack.push("顺"); stack.push("事"); stack.push("万"); stack.push("愿"); while (!stack.isEmpty()) { System.out.print(stack.pop()); } } }
三、LeetCode: 有效的括号
题目地址：https://leetcode.cn/problems/valid-parentheses/
❓ 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
① 左括号必须用相同类型的右括号闭合
② 左括号必须以正确的顺序闭合
③ 每个右括号都有一个对应的相同类型的左括号
☘️ {[]}: true
☘️ ([)]: false
(1) 思路
🍃① 遇见左字符，将左字符入栈
🍃② 遇见右字符
🌻如果栈是空的，说明不是有效的括号【)()】
🌻如果栈不为空，将栈顶字符出栈，与右字符进行比较
❄️如果左右字符不匹配，说明括号无效
❄️如果左右字符匹配，继续扫描下一个字符
🍃③ 所有字符扫描完毕后
🌻栈为空，说明是有效的括号
🌻栈不为空，说明不是有效的括号
(2) 代码
① 看完思路后自己实现的代码
代码是正确的，通过了 LeetCode 的检测
class Solution { /** * 判断是否是有效的括号 * * @param s 待判断的字符串 * @return true: 是有效的括号; false: 不是有效的括号 */ public boolean isValid(String s) { if (s == null || s.length() < 2) return false; String[] ss = s.split(""); Stack<String> stack = new Stack<>(); for (String item : ss) { if (isLeft(item)) { // 是左括号：入栈 stack.push(item); } else if (isRight(item)) { // 是右括号：拿出栈顶元素进行比较 // 拿出了右括号, 但栈为空 if (stack.isEmpty()) return false; String left = stack.pop(); if (!match(left, item)) return false; } } return stack.isEmpty(); } private boolean match(String left, String right) { if ("(".equals(left)) { return ")".equals(right); } else if ("{".equals(left)) { return "}".equals(right); } else if ("[".equals(left)) { return "]".equals(right); } return false; } /** * 判断是否是【左】括号 */ private boolean isLeft(String s) { return "(".equals(s) || "{".equals(s) || "[".equals(s); } /** * 判断是否是【右】括号 */ private boolean isRight(String s) { return ")".equals(s) || "}".equals(s) || "]".equals(s); } }
② 老师的代码
☘️ 字符串的长度要调用
length()方法☘️ 数组的长度是直接访问
length成员变量☘️ 取出字符串的每个字符：
charAt(int index)，返回值是 char 类型【 我是先把字符串转换为字符数组 】
class Solution { public boolean isValid(String s) { if (s == null) return false; int length = s.length(); // 如果只有一个字符（一个括号）或括号是单数, 肯定不是有效的括号 if (length < 2 || ((length % 2) != 0)) return false; Stack<Character> stack = new Stack<>(); for (int i = 0; i < length; i++) { char c = s.charAt(i); if (c == '(' || c == '[' || c == '{') { // 是左括号 stack.push(c); } else if (c == ')' || c == ']' || c == '}') { // 是右括号 // 检查栈是否为空 if (stack.isEmpty()) return false; // 取出栈顶元素进行比较 Character topElem = stack.pop(); if (c == ')' && topElem != '(') return false; if (c == ']' && topElem != '[') return false; if (c == '}' && topElem != '{') return false; } } return stack.isEmpty(); // 如果栈中还有元素，则不是有效的括号 } }
③ 利用 HashMap 简化代码
public class Solution { private static final Map<Character, Character> MAP = new HashMap<>(); static { // 初始化 MAP 的值 MAP.put('(', ')'); MAP.put('[', ']'); MAP.put('{', '}'); } /** * 判断是否是有效的括号 * * @param s 待判断的字符串 * @return true: 是有效的括号; false: 不是有效的括号 */ public boolean isValid(String s) { if (s == null) return false; int length = s.length(); // 如果只有一个字符（一个括号）或括号是单数, 肯定不是有效的括号 if (length < 2 || ((length % 2) != 0)) return false; Stack<Character> stack = new Stack<>(); for (int i = 0; i < length; i++) { char c = s.charAt(i); if (MAP.containsKey(c)) { // 是左括号 stack.push(c); } else if (MAP.containsValue(c)) { // 是右括号 // 检查栈是否为空 if (stack.isEmpty()) return false; // 取出栈顶元素进行比较 Character topElem = stack.pop(); if (MAP.get(topElem) != c) return false; } } return stack.isEmpty(); // 如果栈中还有元素，则不是有效的括号 } }
- 我学习数据结构与算法的全部代码：https://gitee.com/zgq666good/datastructureandalgorithm.git
- 学习资料来自于我偶像 ~ 李明杰（小码哥教育）
🌿如有错误，请不吝赐教🌿
