一、栈的简介
- 栈是一种特殊的线性表, 只能在
一端进行操作。 - 往栈中添加元素的操作，一般叫做
push，入栈。 - 从栈中移除元素的操作，一般叫做
pop，出栈(只能移除栈顶的元素)。 - 栈的内部实现可以
使用动态数组或双向链表实现。 - 栈的主要操作是在
尾部添加或删除元素。
image.png
二、栈的接口设计
public class Stack<E> {
// 使用动态数组实现栈
private List<E> list = new ArrayList<>();
// 元素的数量
public int size();
// 是否为空
public boolean isEmpty();
// 入栈
public void push(E element);
// 出栈
public E pop();
// 获取栈顶元素
public E top();
}
三、动态数组实现栈
public class Stack<E> {
// 使用 动态数组存储数组
private ArrayList<E> list;
public Stack() {
// 初始化方法中创建列表
this.list = new ArrayList<>();
}
public int size() {
// 栈中元素数量, 就是列表中存储的元素数量
return list.size();
}
public boolean isEmpty() {
// 栈是否空, 就是列表是否空
return list.isEmpty();
}
public void push(E element) {
// 入栈, 将元素添加到列表的最后面
list.add(element);
}
public E pop() {
// 出栈, 将列表中最后一个元素删除并返回
return list.remove(list.size() - 1);
}
public E top() {
// 查看栈顶元素, 就是查看列表中的最后一个元素
return list.get(list.size() - 1);
}
public void clear() {
// 清空栈, 就是清空列表
list.clear();
}
}
练习题
LeetCode20. 有效的括号
给定一个只包括 (，)，{，}，[，] 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
-
1- 遇见左字符，将左字符入栈
-
2- 遇见右字符
- 如果栈是空的，说明括号无效
- 如果栈不为空，将栈顶字符出栈，与右字符匹配
- 如果左右字符不匹配，说明括号无效
- 如果左右字符匹配，继续扫描下一个字符
-
3- 所有字符扫描完毕后
- 栈为空，说明括号有效
- 栈不为空，说明括号无效
解法1:
public boolean isValid(String s) {
while(s.contains("{}") || s.contains("[]") || s.contains("()")){
s.replace("{}", "");
s.replace("[]", "");
s.replace("()", "");
}
return s.isEmpty();
}
解法2:
public boolean isValid2(String s){
Stack<Character> stack = new Stack<>();
int len = s.length();
for(int i = 0; i < len; i++){
char c = s.charAt(i);
if(c == '(' || c == '[' || c == '{'){ // 左括号
stack.push(s.charAt(i)); // 左字符入栈
}else{ // 右括号
if(stack.isEmpty()) return false; // 没有左括号, 却匹配到了右括号，false
char left = stack.pop();
if(left == '(' && c != ')') return false; // 左右括号不匹配
if(left == '[' && c != ']') return false; // 左右括号不匹配
if(left == '{' && c != '}') return false; // 左右括号不匹配
}
} // 扫描完毕
return stack.isEmpty();
}
解法3:
static HashMap<Character, Character> map = new HashMap<>();
static {
map.put('(', ')');
map.put('[', ']');
map.put('{', '}');
}
public boolean isValid(String s){
Stack<Character> stack = new Stack<>();
int len = s.length();
for(int i = 0; i < len; i++){
char c = s.charAt(i);
if(map.containsKey(c)){ // 左括号，哈希表中有该键则入栈
stack.push(c);
}else{ // 右括号
if(stack.isEmpty()) return false;
char left = stack.pop();
if(c != map.get(left)) return false;
}
}
return stack.isEmpty();
}
LeetCode150. 逆波兰表达式求值
根据 逆波兰表示法，求表达式的值。
有效的算符包括+、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：
该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
提示：
1 <= tokens.length <= 104
tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"）
要么是一个在范围 [-200, 200] 内的整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String string : tokens) {
switch (string) {
case "+":
stack.push(stack.pop() + stack.pop());
break;
case "-":
stack.push(-stack.pop() + stack.pop());
break;
case "*":
stack.push(stack.pop() * stack.pop());
break;
case "/":
Integer right = stack.pop();
stack.push(stack.pop() / right);
break;
default:
stack.push(Integer.parseInt(string));
break;
}
}
return stack.pop();
}
}
网友评论