共计 2747 个字符，预计需要花费 7 分钟才能阅读完成。
介绍
栈是一种后进先出的线性表数据结构，分为栈顶和栈底两端，仅允许在表的一端插入元素，这一端被称为栈顶，另外一端称之为栈底。栈，只有两种操作，分为入栈（压栈）和出栈（退栈）；向栈中添加元素的操作叫做入栈，相反从栈中删除元素叫做出栈。
特点
只能从栈顶添加元素或者删除元素
后进先出的数据结构，Last In First Out（LIFO）
为了大家更好的形象了解我们通过示意图来看一下栈的入栈和出栈操作
<font color=’green’> 入栈操作示意图 </font>
<font color=’green’> 出栈操作示意图 </font>（后进的元素先出）
栈的基本操作
向栈中添加一个元素（入栈）
void push(E e)
从栈中删除一个元素（出栈）
E pop()
查看栈顶元素
E peek()
查看栈中元素个数
int getSize()
判断栈是否为空
boolean isEmpty()
实现栈的方式，实际上底层有多种实现方式，比如：动态数组等，这里我们使用 Java 语言本身为我们提供的集合 LinkedList
接口定义：Stack<E>
public interface Stack<E> {
/**
* 向栈中添加元素
*
* @param e
*/
void push(E e);
/**
* 从栈中删除元素
*/
void pop();
/**
* 获取栈顶元素
*
* @return
*/
E peek();
/**
* 获取栈中元素个数
*
* @return
*/
int getSize();
/**
* 判断栈中是否为空
*
* @return
*/
boolean isEmpty();
}
LinkedListStack<E> 类实现接口 Stack<E>
public class LinkedListStack<E> implements Stack<E> {
/**
* 存放栈元素
*/
LinkedList<E> list;
/**
* 构造栈结构
*/
public LinkedListStack() {
list = new LinkedList<>();
}
@Override
public void push(E e) {
list.addLast(e);
}
@Override
public void pop() {
list.removeLast();
}
@Override
public E peek() {
return list.getLast();
}
@Override
public int getSize() {
return list.size();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public String toString() {
return “LinkedListStack{” +
“list=” + list +
‘}’;
}
}
测试类：LinkedListStackTest
@Test
public void testLinkedListStack() {
// 栈
Stack<String> stack = new LinkedListStack<>();
// 准备入栈元素
List<String> prepareElements = Arrays.asList(“A”, “B”, “C”, “D”, “E”);
// 入栈
prepareElements.forEach(x -> {
stack.push(x);
System.out.println(“ 入栈操作：” + stack);
});
// 出栈
stack.pop();
System.out.println(“ 出栈操作：” + stack);
// 获取栈顶元素
String peekElement = stack.peek();
System.out.println(“ 栈顶元素：” + peekElement);
// 获取栈中元素的个数
int stackSize = stack.getSize();
System.out.println(“ 栈中元素个数：” + stackSize);
}
运行结果
入栈操作：LinkedListStack{list=[A]}
入栈操作：LinkedListStack{list=[A, B]}
入栈操作：LinkedListStack{list=[A, B, C]}
入栈操作：LinkedListStack{list=[A, B, C, D]}
入栈操作：LinkedListStack{list=[A, B, C, D, E]}
出栈操作：LinkedListStack{list=[A, B, C, D]}
栈顶元素：D
栈中元素个数：4
栈的应用
虚拟机栈的入栈和出栈操作
在 Java 虚拟机运行时数据区有一块被称之为：虚拟机栈，它是线程私有的，声明周期与线程相同。
我们编写的每个 Java 方法，每个方法都会在执行的时候同时都会创建一个栈帧（Stack Frame）用于存储局部变量表、操作数栈、动态链接、方法出口等信息。每一个方法从调用直至执行完成的过程，就对应这一个栈帧在虚拟机栈中入栈到出栈的过程。
现在我们假设有 A、B、C 三个方法，在 A 方法中调用 B 方法（A->B），在 B 方法中调用 C 方法（B->C），C 方法执行本方法业务逻辑。
当程序执行到 A() 方法的中的第二行时，此时程序会中断 A() 方法并开始调用 B() 方法，然后会在虚拟机栈中记录调用 B() 方法的栈帧，我这里暂且称之为 A2（实际存储的并不是 O(∩_∩)O 哈！）示意图如下：
同理，当程序执行到 B() 方法中第二行时，此时程序也会中断 B() 方法开始调用 C() 方法，然后同样地会在虚拟机栈中生成调用 C() 方法的栈帧并记录，我这里暂且称之为 B2，示意图如下：
当程序开始执行到 C() 方法时，直到执行完 C() 方法时，这时候，程序该如何执行呢？
此时就要查看一下虚拟机栈了，发现虚拟机栈，栈中栈顶的元素是 B2，我们的程序就知道了，它是执行到 B() 方法的 B2 位置就中断了，去执行 C() 方法了；现在 C() 方法执行完成之后，它就可以跳回到 B2 的位置继续执行了，当 B() 方法执行完之后，虚拟机栈中的 B2 栈帧也就可以出栈了，依次类推 ….
如果一个方法，使用递归调用，若递归临界点判断有误，则方法就会一直的被进行入栈操作，如果超过虚拟机栈的默认容量大小，则会出现我们常见的 StackOverflowError 异常
完整版代码 GitHub 仓库地址：Java 版数据结构 - 栈 欢迎大家【关注】和【Star】
本次我们完成的是基于 Java 自身自带的集合 LinkedList 来实现栈，有兴趣的童鞋，可以使用动态数组方式来实现；接下来，笔者还会一一的实现其它常见的数组结构。
静态数组
动态数组
栈
队列
链表
循环链表
二分搜索树
优先队列
堆
线段树
字典树
AVL
红黑树
哈希表
….
持续更新中，欢迎大家关注公众号：小白程序之路（whiteontheroad），第一时间获取最新信息！！！
笔者博客地址：http:www.gulj.cn
