j2ee做网站2023年国家免费技能培训
栈（Stack）
-
栈是一种特殊的线性表，只能在一端进行操作。
-
往栈中添加元素的操作，一般叫做
push，入栈
-
从栈中移除元素的操作，一般叫做
pop，出栈（只能移除栈顶元素，也叫做：弹出栈顶元素）
-
后进先出的原则，Last In First Out，LIFO
我们可以将栈看做一个动态数组（ArrayList）或者一个线性表（List），这样很好的实现栈的添加和删除等操作。 -
下面通过将上一次我们写的ArrayList动态数组导入进去，变为Stack(栈)的一部分，进而更加方便的实现栈的添加、删除等操作。
-
对于动态数组，我们可以参考上篇文章ArrayList动态数组底层封装分析
import com.mj.list.ArrayList;
import com.mj.list.List;public class Stack<E>{/*这里之所以将list变为私有的，是因为如果直接继承ArrayList，会导致后期可以通过ArrayList里面的get、set等操作来实现Stack里面的数值变化。在我们平常，Stack（栈）是没有这些操作的，所以要将其变为私有的，防止被外面直接调用进行修改。 我们既可以直接将ArrayList变为Stack中的一部分，也可以将LinkedList变为Stack中的一部分*/private List<E> list = new ArrayList<>();/*** 元素的数量* @return*/public int size() {return list.size();}/*** 是否为空* @return*/public boolean isEmpty() {return list.isEmpty();}/*** 入栈* @param element*/public void push(E element) {list.add(element);}/*** 出栈* @return*/public E pop() {return list.remove(list.size()-1);}/*** 获取栈顶元素* @return*/public E top() {return list.get(list.size()-1);}/*** 清空栈中元素*/public void clear() {list.clear();}
}
测试：
public class Main {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(11);stack.push(22);stack.push(33);stack.push(44);while (!stack.isEmpty()) {System.out.println(stack.pop());}}
}
运行结果：
44
33
22
11
LeetCode — 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。
- 有效字符串需满足：
①左括号必须用相同类型的右括号闭合。
②左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
- 解法一：
import java.util.Stack;public class _20_有效的括号 {public boolean isValid(String s) {//[({})]while (s.contains("{}")|| s.contains("()")|| s.contains("{}")){s = s.replace("{}", "");s = s.replace("()", "");s = s.replace("[]", "");}return s.isEmpty();}
}
- 解法二：
import java.util.Stack;public class _20_有效的括号 {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 (c == '(' || c == '[' || c == '{') {//如果是左括号stack.push(c);}else {//右括号if (stack.isEmpty()) return false;char left = stack.pop();if (left == '(' && c != ')') return false;if (left == '[' && c != ']') return false;if (left == '{' && c != '}') return false;}}return stack.isEmpty();}
}
- 解法三：
import java.util.HashMap;
import java.util.Stack;public class _20_有效的括号 {private static HashMap<Character, Character> map = new HashMap<>();static {// key - value 键值对map.put('(', ')');map.put('[', ']');map.put('{', '}');}public boolean isValid3(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;if (c != map.get(stack.pop())) return false;}}return stack.isEmpty();}
}