白话文讲栈
思考题
给定一个仅包含字符：(,),[,]的字符串，确定输入字符串是否有效。
字符串有效的定义如下：
- 开括号必须用同一类型的括号闭合。
- 开方括号必须按正确顺序闭合。
// 示例1
Input: "()"
Output: true
// 示例2
Input: "()[]{}"
Output: true
// 示例3
Input: "(]"
Output: false可以先思考一下这个问题，是否可以结合栈解决呢？
栈
栈（stack）又名堆栈，它是一种操作受限的线性表。其限制是仅允许在线性表头进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。
- 向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
- 从一个栈删除元素又称作出栈、退栈或弹栈，它是把栈顶元素删掉，使下方的元素成为新的栈顶元素；
栈按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
关于栈我列举一个很贴切的例子，就是一摞叠在一起的书。假设我们平时放书的时候，都是从下往上一本一本的放，取书的时候也都是从上往下一本一本的取，不能从中间任意位置抽取和放置，这就是典型的栈结构。
一叠书.png
如何实现栈呢？
前面我们讲解过数组和链表，栈也可以使用这两个数据结构去实现。基于数组实现的栈，我们称之为数组栈。基于链表实现的栈，我们称之为链式栈。由于数组的特性，数组栈的空间是有界的，当栈的空间不满足需求时，需要执行扩容。而链表理论上则是无界的，因为实际受到物理资源限制。
// 基于数组实现的顺序栈
public class ArrayStack {
private String[] items; // 数组
private int count; // 栈中元素个数
private int n; // 栈的大小
// 初始化数组，申请一个大小为 n 的数组空间
public ArrayStack(int n) {
this.items = new String[n];
this.n = n;
this.count = 0;
}
// 入栈操作
public boolean push(String item) {
// 数组空间不够了，直接返回 false，入栈失败。
if (count == n) return false;
// 将 item 放到下标为 count 的位置，并且 count 加一
items[count] = item;
++count;
return true;
}
// 出栈操作
public String pop() {
// 栈为空，则直接返回 null
if (count == 0) return null;
// 返回下标为 count-1 的数组元素，并且栈中元素个数 count 减一
String tmp = items[count-1];
--count;
return tmp;
}
}了解了定义和基本操作，那它的操作的时间、空间复杂度是多少呢？
不管是顺序栈还是链式栈，我们存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。
注意，这里存储数据需要一个大小为 n 的数组，并不是说空间复杂度就是 O(n)。因为，这 n 个空间是必须的，无法省掉。所以我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。
空间复杂度分析是不是很简单？时间复杂度也不难。不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是 O(1)。
Java中的栈的实现
Java中的栈我们主要关注Stack类，它继承自Vector。Vector是线程安全容器，但由于使用synchronized锁，在要求高性能高并发环境下并不推荐。
Stack使用数组存储元素，但凡使用数组构建的数据结构都会有一个共通的问题——需要扩容。在JDK8中，默认情况下Stack的扩容规则是当栈的大小等于容量大小时，则将当前容量扩大为现在容量的两倍。如果要修改默认扩容行为，可以通过构造器设定扩容的步长，以求更合理的配置扩容。
Object (java.lang)
AbstractCollection (java.util)
AbstractList (java.util)
Vector (java.util)
Stack (java.util)解答思考题
使用栈这种数据结构，使得我们很容易解决诸如逆波兰式、汉诺塔等问题。熟悉栈的定义并不难，但我们对栈的理解不能仅仅停留在静态栈的层面上，更多的需要思考栈的动态性，结合这些动态性我们可以解决哪些问题。
class Solution {
public boolean isValid(String s) {
if ((s.length() & 1) == 1) {
return false;
}
HashMap<Character, Character> symbolMap = new HashMap<>();
symbolMap.put(')', '(');
symbolMap.put('}', '{');
symbolMap.put(']', '[');
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
switch (c) {
case ')':
case '}':
case ']':
if (stack.empty()) {
return false;
} else if (Objects.equals(stack.lastElement(), symbolMap.get(c))) {
stack.pop();
} else {
stack.push(c);
}
break;
default:
stack.push(c);
break;
}
}
return stack.empty();
}
}
腾讯云开发者
