其他
363，数据结构-4,栈
基础知识
栈也是一种特殊的线性表，他只能对栈顶进行添加和删除元素。栈有入栈和出栈两种操作，他就好像我们把书一本本的摞起来，最先放的书肯定是摞在下边，最后放的书肯定是摞在了最上面，摞的时候不允许从中间放进去，拿书的时候也是先从最上面开始拿，不允许从下边或中间抽出来。
栈的原理图
栈的实现可以使用数组也可以使用链表，我们这里分析的主要是使用数组的形式。
代码实现
栈的实现其实非常简单，常见的就两种操作，一种是压栈一种是出栈，我们来看下代码
1public class Stack<E> {
2 private Object[] data;
3 private int size;
4
5 public Stack(int capacity) {
6 if (capacity <= 0)
7 throw new IllegalArgumentException("栈的大小必须大于0");
8 data = new Object[capacity];
9 }
10
11 public void push(E item) {
12 if (isFull())
13 throw new IllegalArgumentException("栈已经满了");
14 data[size++] = item;
15 }
16
17 public E pop() {
18 if (isEmpty())
19 throw new IllegalArgumentException("栈是空的");
20 E temp = (E) data[--size];
21 data[size] = null;
22 return temp;
23 }
24
25 public E peek() {
26 if (isEmpty())
27 throw new IllegalArgumentException("栈是空的");
28 return (E) data[size - 1];
29 }
30
31 public boolean isEmpty() {
32 return size() == 0;
33 }
34
35 public boolean isFull() {
36 return size() == data.length;
37 }
38
39 public int size() {
40 return size;
41 }
42}
这里为了方便，栈的空间大小在初始化的时候就就已经固定了，并且栈满的时候没有扩容，栈是一个非常有用的数据结构，尤其在算法中用到的还是比较多的。栈是一种先进后出的数据结构，他和队列正好相反，队列是一种先进先出的数据结构。
例子
我们来看个非常简单的例子，验证括号的有效性，括号只包含"("，")"，"["，"]"，"{"，"}"这6个字符，比如()，{()}，[](){}都是有效的，而{]，{(]}都是无效的。
我们来分析一下这道题，当我们遍历到括号的左半边的时候，我们把括号的右半边压栈，当我们遍历到括号右半边的时候，我们就把栈顶的元素弹出，然后在和我们遍历的符号比较看是否一样，我们以字符串"{([]())}"为例来画图分析一下，
搞懂了上面的图，写出代码就容易多了，我们来看下代码怎么实现
1public boolean isValid(String s) {
2 Stack<Character> stack = new Stack<>(s.length());
3 for (char c : s.toCharArray()) {
4 if (c == '(')
5 stack.push(')');
6 else if (c == '{')
7 stack.push('}');
8 else if (c == '[')
9 stack.push(']');
10 else if (stack.isEmpty() || stack.pop() != c)
11 return false;
12 }
13 return stack.isEmpty();
14}