- 用数组实现的栈，叫做 顺序栈：
- 顺序栈的实现非常简单，这里就不写代码了，写一下思路。先初始化一个数组，然后再用一个变量给这个数组里的元素进行计数，当有新元素需要入栈的时候，将这个新元素写入到数组的最后一个元素的后面，然后计数器加一。当需要做出栈操作时，将数组中最后一个元素返回，计数器减一。
- 当然在入栈前需要判断数组是否已经满了，如果数组大小等于计数器大小，则表明数组是满的。
- 出栈的时候也需要判断数组是不是空数组，如果计数器是0，则表明数组是空的。
- 从上面的实现流程可以看出，通过数组实现的栈，其入栈和出栈都是对单个元素进行操作，因此其入栈和出栈的时间复杂度都是O(1)，并且其入栈和出栈操作并没有额外开销更多空间，因此其空间复杂度也是O(1)的。
- 用链表实现的栈，叫做 链式栈：
- 实现思路是先定义一个链表节点的类，基于这个类去定义一个头节点Head。当有新元素需要入栈的时候，将这个新元素的Next指针指向头结点Head的Next节点，然后再将Head的Next指向这个新节点。当需要做出栈操作时，直接将Head所指向的节点返回，同时让Head指向下一个节点。
- 当然，在入栈和出栈时都需要判断链表是否为空的情况。
- 链式栈的入栈和出栈都是在处理头部节点，所以操作很简单，其时间和空间复杂度均为O(1)。
算法题：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
举例：字符串 "()"有效、"()[]{}"有效、"(]"无效、"([)]"无效、"{[]}"有效。
解题思路：
使用1个堆栈即可解决，依次遍历这个字符串，如果遇到是左括号就入栈到堆栈中，如果遇到的是右括号，则从堆栈中取出栈顶的第一个左括号，比对一下这个左括号和当前遇到的右括号是否匹配，如果不匹配这认为这整个字符串无效。如果能匹配，则OK，删除这个左括号和右括号，继续往后走，继续遍历字符串中剩下的字符，只要遇到左括号就入栈，只要遇到右括号就与将栈顶的左括号出栈与之比较。一直走到字符串结束，再来检查堆栈中是否还有元素，如果还有元素，则这个字符串同样无效，如果堆栈为空，则字符串有效。
就以这个思路实现一个初版代码：
class Solution {
public boolean isValid(String s) {
Stack<Character> satck = new Stack<Character>();
for(int i=0; i<s.length();i++){
char c = s.charAt(i);
if(c=='(' || c=='{' || c=='['){
satck.push(c);
}else{
if(satck.isEmpty()) return false;
char temp = satck.pop();
if( (temp=='('&&c==')') || (temp=='{'&&c=='}') || (temp=='['&&c==']') ){
continue;
}else{
return false;
}
}
}
return satck.isEmpty();
}
}
这个代码的时间复杂度o(n),空间复杂度o(n)搞定。
但是想了想，好像代码不是很优雅，写了一个优化版，提前将左右括号放入到MAP中，这个方法的时间和空间复杂度跟上面的一样。
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
HashMap<Character,Character> map = new HashMap<Character,Character>();
map.put('(', ')');
map.put('{','}' );
map.put('[', ']');
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(map.containsKey(c)){
stack.push(c);
}else{
if(stack.isEmpty()) return false;
char temp = stack.pop();
if(map.get(temp)!=c) return false;
}
}
return stack.isEmpty();
}
}
继续思考有没有更简洁的方法，竟然在leetcode上找到了一个：
但是这个方法并没有用到堆栈哦，它的思路是不断的遍历这个字符串，将字符串中的(){}[]全部调换成空字符串，如果最后全部替换完成了，并且字符串为空了，就说明字符串是有效的，否者就是无效的字符串。
class Solution {
public boolean isValid(String s) {
int length = s.length();
do{
length = s.length();
s = s.replaceAll("\\(\\)","").replaceAll("\\{\\}","").replaceAll("\\[\\]","");
}while(s.length()!=length);
return s.length()==0;
}
}
不过这个方法的时间复杂度要高一些。
以上，就是对数据结构中「 堆栈 」的一些思考。
码字不易啊，喜欢的话不妨转发朋友，或点击文章右下角的“在看”吧。
本文原创发布于微信公众号「 不止思考 」，欢迎关注。涉及 思维认知、个人成长、架构、大数据、Web技术 等。
声明：本文由网站用户香香发表，超梦电商平台仅提供信息存储服务，版权归原作者所有。若发现本站文章存在版权问题，如发现文章、图片等侵权行为，请联系我们删除。
