写在前面
这一篇我们来学习栈，栈也是非常重要的数据结构，需要好好理解和掌握。
栈初识
栈是一种线性结构，相比与数组，栈对应的操作是数组的子集。不过栈只能从一端添加元素，也只能从一端取出元素(这一端称之为栈顶)。你可以把栈理解为我们常见的竖状容器：
记住添加元素和取出元素都只能从栈顶位置开始存取。从图中你也知道栈是一种后进先出的数据结构（先进来的在底部，后面的最先出去）。因此后进先出英文就是Last ln First Out (LIFO)。
栈的应用
你在使用office办公软件的时候，经常会使用撤销操作，Undo操作(撤销)是无处不在的。
假设你需要在word里面打一行字: "沉迷学习无法自拔"，然后你一不小心将"无法"打成"不法"，然后你就要使用ctrl+Z或者撤销操作，这样"不法"就从栈里面给压出来了，然后你再去写入"无法自拔"，这样句子就写完了。如果你想写"沉迷OSC，无法自拔"，你就要多次执行撤销操作，最后写入"沉迷OSC，无法自拔"即可。
另一个例子是程序调用的系统栈(这个例子对于理解递归有很大的作用)
我们来看这张图片，这里模拟计算机中程序的调用系统栈：
现在我们开始启动程序：当函数A运行到函数B的时候，会去调用函数B; 而函数B运行到函数C的时候，会去调用函数C;而函数C运行到函数3的时候继续往后走。。。
但是这样调用顺序计算机必须要记录下来的，这里就是使用系统栈来完成这个目的的，A2代表运行到A函数第二行，B2代表运行到B函数第二行，然后有了这个系统栈，等到最后程序运行完了以后，就会依次使用出栈的方式开始往前执行程序，最后返回执行A函数，等到A函数执行完发现栈里面是空的，那么整个程序就真的执行完毕了。下面我们使用代码来模拟栈。
栈
关于栈，它是一种非常简单的数据结构，而且里面提供的方法也是有限的，一般是这5种方式：
Stack<E> void push(E e); // 向栈中添加元素 E pop(); // 弹出栈顶元素 E peek( ); // 查看栈顶元素 int getSize(); // 获取栈中元素个数 boolean isEmpty(); // 判断栈是否为空
这个就不存在直接删除某个元素的操作了，只能依次通过删除栈顶的元素来慢慢实现删除该元素的目的。
其实从用户的角度来说，只要能支持这些操作就行。至于具体的底层实现，用户是不关心的，因为它实际上底层有多种实现方式。
这里我们就把栈定义为一个接口，然后只要能实现这个接口就可以，这也就是我们前面所说的用户只需要具有这些功能即可的目的。在test包下面新建一个Stack包，然后在里面新建一个接口Stack.java文件，里面的代码如下：
Interface Stack<E> implement ArrayStack<E> int getSize(); boolean isEmpty(); void push(E e); E pop(); E peek();
我们复制之前创建的数组ArrayElement.java文件，因为我们即将实现的ArrayElementStack会用到它。注意前面的addList()方法就是addLast()方法，我打错了，你们记得修改过来哈
前面说过，我们的peek方法是查看栈顶的元素，因此我们需要在ArrayElement.java文件里面新增两个方法，用于获取数组首位和末尾的元素：
/**
* 获取开头位置的元素
*
* **/
public E getFirst(){
return get(0);
}
/**
* 获取末尾位置的元素
*
* @return 末尾位置的元素
* **/
public E getLast(){
return get(size-1); //这里不可以使用data[size-1]，因为假设size==0就会出现不合法的索引号。
}
最后打开Stack包，然后在里面新建ArrayElementStack.java文件，这里我就附上完整的ArrayElementStack文件代码：
package com.suanfa.test.Stack;
import com.suanfa.test.Array.ArrayElement;
//自己定义的数组栈
public class ArrayElementStack<E> implements Stack<E> {
//定义一个数组
ArrayElement<E> arrayElement;
public ArrayElementStack(){
arrayElement =new ArrayElement<>();
}
public ArrayElementStack(int capaciy){
arrayElement =new ArrayElement<>(capaciy);
}
//实现stack接口中的方法
//实现stack接口中的getSize方法
@Override
public int getSize(){
return arrayElement.getSize();
}
/**
* 实现stack接口中的isEmpty方法
*
* @return
*/
@Override
public boolean isEmpty(){
return arrayElement.isEmpty();
}
/**
* 实现stack接口中的push方法
*
* @param e 待添加的元素
* @return
*/
@Override
public void push(E e){
arrayElement.addLast(e);
}
/**
* 实现stack接口中的pop方法
*
* @return 栈顶刚删除的元素
*/
@Override
public E pop(){
return arrayElement.removeLast();
}
/**
* 实现stack接口中的Peek方法
*
* @return 查看栈顶的元素
*/
@Override
public E peek(){
return arrayElement.getLast();
}
/**
*
* @return 查看栈的容量
*/
public int getCapacity(){
return arrayElement.getCapacity();
}
/**
*
* @return 输出栈的元素
*/
public String toString(){
//使用StringBuilder；来创建新的字符串对象
StringBuilder res =new StringBuilder();
res.append("Stack");
res.append("[");
for(int i=0;i<arrayElement.getSize();i++){
res.append(arrayElement.get(i));
//判断是否是最后一个元素，从而是否需要在后面添加逗号
if(i != arrayElement.getSize()-1){
res.append(",");
}
}
res.append("]top");
return res.toString();
}
}
现在你可能要说，我们无法查看和插入元素到栈里面，我前面也说了，栈这种数据结构比较特殊，是无法进行选择插入和查看其它元素的（除了栈顶元素），当然你硬是要这样也是可以的，自己定义方法呗，就是感觉逻辑上说不过去而已。
现在我们来新建一个测试文件ArrayElementStackTest.java文件，里面写入以下代码：
package com.suanfa.test.Stack;
public class ArrayElementStackTest {
public static void main(String [] args){
ArrayElementStack<Integer> stack =new ArrayElementStack<>();
for(int i=0;i<5;i++){
stack.push(i);
System.out.println(stack);
}
System.out.println("*******************************************");
stack.pop();
System.out.println(stack);
}
}
//运行结果
Stack[0]top
Stack[0,1]top
Stack[0,1,2]top
Stack[0,1,2,3]top
Stack[0,1,2,3,4]top
*******************************************
Stack[0,1,2,3]top
栈的时间复杂度分析
ArrayStack<E> void push(E e) // O(1) 均摊（触发resize也是O(1)） E pop() // O(1) 均摊 （触发resize也是O(1)） E peek() // O(1) int getSize() // O(1) boolean isEmpty() // O(1)
注意这里面的push和pop操作，尽管都是在末尾进行，但是有可能触发resize。一旦触发resize，但均摊来算还是O(1)。
栈的应用（续）
在前面的栈的应用介绍里，我们介绍了编辑器undo操作（撤销）和操作系统中的系统调用栈这两个例子，但是都是简单的介绍并没有用代码去实现一个例子。下面要举的这个例子，就是需要用代码来实现的。
通常我们在用IDE进行开发的时候，如果你忘记对括号进行闭合，IDE是会给你报错提示的，那么这个对括号匹配，IDE是如何实现的呢？下面就通过用代码来模拟实现一下。其实这也是leetCode的第二十道题，题目是这样的：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
这个题目是什么意思呢？举个例子：{ [ ( ) ] }首先将左侧符号（其实是指 { [ (）压入栈，然后在开始进行匹配右侧符号的时候，将该符号与栈顶元素进行匹配，如果一样就出栈，继续前面的操作，直到所有字符扫描完毕，栈为空则表明匹配成功。否则，一旦出现栈顶元素与该匹配字符不合，就立即判断该符号匹配不正确。
也就是说栈顶元素反映了在嵌套的层次关系中，最近的需要匹配的元素。
最后的运行代码如下：
import java.util.Stack;
class Solution {
public boolean isValid(String s) {
Stack<Character> stack =new Stack<>();
for(int i =0;i<s.length();i++){
char c =s.charAt(i);
if(c == '['|| c == '(' || c == '{'){
stack.push(c);
}else{
if(stack.isEmpty()){
return false;
}
char charTop =stack.pop();
if(c ==']'&&charTop !='['){
return false;
}
if(c ==')'&&charTop !='('){
return false;
}
if(c =='}'&&charTop !='{'){
return false;
}
}
}
return stack.isEmpty();
}
}
上面我们使用的是Java提供给我们的Stack，后面我们会使用到自己编写的Stack来完成这个功能。注意上面charTop中的pop操作，它完成了取出栈顶元素和保存栈顶元素这两个功能。
关于LeetCode的更多说明，首先你肯定好奇为什么我们在前面不需要添加main方法，而LeetCode就能运行呢？那是因为LeetCode会自动创建该类的一个main方法，请注意该方法必须是public修饰，因为它会在该类的外部创建自己的Main来调用执行该类中你定义的方法。
当然，你在提交的时候即使添加了main方法，系统也不会报错的，因为不会执行它。但是请注意不要将自己Package的语句也加入到里面，这个是会报错的。LeetCode只允许你提交一个类，多的则不可以。那么你就可以把其他类当做该类的内部类就能达到这个目的。
你也看到了LeetCode上面关于栈这一块有39个问题，但是我们不是说你现在学到了栈这个数据结构，就要把那39道题目全部都做完了，才能继续学习下一个数据结构，这是不正确的。你不要有完美主义的思想，有时候能做就做，不做就放弃吧，等到后面再来看的时候就发现原来这么简单呐，反正我是经常有这种情况的。所以，有时候完美主义不但没有帮助你学会某个东西，而是相反却成了你成功路上的绊脚石。