说完了链表,我们再看看栈。
栈是什么,很金典的比喻就是把 栈
比喻成叠盘子
,一个个叠上去,然后拿的时候会先拿最上面的,也就是最后叠上去的那个。
先进者后出、后进者先出,这就是栈结构
。
那么栈在实际应用中有什么场景呢?
可太多了,比如Activity中的任务栈,编译器实现方法表达式,浏览器的前进后退。
这里拿浏览器的前进后退做例子。
1)浏览网页,每打开一个网页就入栈A。比如这里打开了网页M和网页N。
2)点击后退,网页N出栈A,入栈B。
3)点击前进,网页N出栈B,入栈A。
在Java中,栈的对应类为Stack
。
//初始化栈
Stack<String> stack =new Stack<String>();
//入栈
stack.push("test");
//出栈,返回出栈的元素
String str=stack.pop();
还是老样子,来一题栈相关的算法题。
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
示例 1:输入:s = "()" 输出:true
示例 2:输入:s = "()[]{}" 输出:true
示例 4:输入:s = "([)]" 输出:false
示例 5:输入:s = "{[]}" 输出:true
解法就是利用栈了。
遇到左括号入栈,遇到右括号就把相应的左括号出栈,如果右括号和要出栈的这个元素不一致,就说明括号没有成对。
关于左括号和右括号的对应关系,可以用HashMap来存储,来一起看看:
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
Map<Character, Character> pairs = new HashMap<Character, Character>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
Deque<Character> stack = new LinkedList<Character>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (pairs.containsKey(ch)) {
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
stack.pop();
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
也有比较灵活的办法,就是入栈的时候就确定好括号的对应关系,直接入栈左括号对应的右括号。
public boolean isValid(String s) {
if(s.isEmpty())
return true;
Stack<Character> stack=new Stack<Character>();
for(char c:s.toCharArray()){
if(c=='(')
stack.push(')');
else if(c=='{')
stack.push('}');
else if(c=='[')
stack.push(']');
else if(stack.empty()||c!=stack.pop())
return false;
}
if(stack.empty())
return true;
return false;
}
需要遍历字符串,所以时间复杂度为 O(n)
栈的字符数量最大为n,Map数量为3,所以空间复杂度就是O(n)
https://time.geekbang.org/column/article/41222
感谢大家的阅读,有一起学习的小伙伴可以关注下公众号—
码上积木
❤️❤️ 每日三问知识点/面试题,积少成多。