数据结构 之 栈(Stack)
1. 定义：
栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作；
进行数据插入的和删除的一端称为栈顶，另一端称为栈底；
栈这个数据结构遵从后进先出（先进后出）的原则；
如图所示，每次在栈中添加元素或者取出元素时，只能在栈顶进行操作，这就是后进先出的原则
类似于我们现实生活中的枪械的弹夹一般：
先装入弹夹的子弹，往往在弹夹的最下方，同时也是最后一个被发射出去的；
又例如：
这是我们qq的更新的弹窗，如果我们不关闭这个弹窗，就无法使用qq的其他功能，这个弹窗是最后一个弹出来的，同时也是第一个被关闭的，这里同样使用的栈这个数据结构；
从上图可以看出，Stack继承于Vector，Vevtor和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的；
2. 栈、虚拟机栈、栈帧的区别：
栈：如上所述，栈是一种后进先出的数据结构；
虚拟机栈：虚拟机栈是具有特殊作用的一块内存空间；
jvm为了对数据进行更好的管理，将内存按照不同的需求划分出来的一种结构
栈帧：一种结构，这种结构与函数调用相关的，内部：局部变量表、操作数栈......
每个方法在运行时，jvm都会创建一个栈帧，然后将栈帧压入到虚拟机栈中
当方法调用结束时，该方法对应的栈帧会从虚拟机栈中出栈
3.栈的常用方法和模拟实现：
3.1 常用方法：
方法作用Stack()构造一个大小为默认大小的栈Stack(int n) 构造一个大小为n的空栈 E push(E e)将e入栈，并返回eE pop() 获取栈顶元素并删除栈顶元素E peek()获取栈顶元素size()获取栈的元素个数empty() 检测栈是否为空
（在栈的模拟实现中，我们并不使用泛型，而是使用整形来代替泛型）
以上就是栈的常用方法，接下来我们开始模拟实现这些方法：
3.2 模拟实现：
首先我们来写一个My_Stack类：
public class My_Stack {
int[] elem; //模拟实现栈
int usedSize; //已使用的长度
int DEFAULT_CAPACITY = 10; //默认大小
}< 1 > 构造方法：
这里模拟实现两个构造方法：
一个是构造默认大小的栈
一个是构造指定大小的栈
public My_Stack() {
this.elem = new int[DEFAULT_CAPACITY]; //构造一个大小为默认大小的栈
}
public My_Stack(int n) {
this.elem = new int[n]; //构造一个大小为n的栈
}< 2 > push方法：
push方法是将给定的值进行入栈操作，并返回该值
在进行push方法的时候，我们需要判断栈是否满了，如果栈满了，我们就需要进行扩容，那我们就需要写一下判断栈是否满了和扩容的方法：
private boolean isFUll () {
return usedSize == elem.length; //返回数组长度是否等于使用大小 的值
}
private void grow (int[] elem) {
if (elem.length <= 64) {
elem = Arrays.copyOf(elem, elem.length * 2); //如果数组长度小于64，则进行二倍扩容
} else {
elem = Arrays.copyOf(elem, elem.length + elem.length >> 1); //如果大于64，则进行1.5倍扩容
}
}在此基础上，我们开始push方法的模拟实现：
public int push (int val) {
if (isFUll()) { //判断栈是否满了，如果满了，则进行扩容
grow(elem);
}
elem[usedSize++] = val; //在数组的最末尾进行插入，并将usedSize++
return val; //返回val的值
}< 3 > empty方法：
empty方法是判断栈是否为空，方法比较简单，如下：
public boolean empty () {
return usedSize == 0; //判断usedSize是否 = 0 即可
}< 4 > pop方法：
pop方法是将栈顶元素进行出栈操作，并返回该值：
在进行该操作的时候，我们同样需要判断，栈是否为空，若栈为空，则抛出异常：
异常的代码如下：
public class StackEmptyException extends RuntimeException{
public StackEmptyException () {
super();
}
public StackEmptyException (String str) {
super(str);
}
}随后进行pop方法的模拟实现：
public int pop () {
if (empty()) {
throw new StackEmptyException("该栈为空，不能进行pop操作!!!");
}
int ret = elem[usedSize]; //将elem[usedSize]的值保存下来
usedSize--; //usedSize--相当于删去数组最后一位元素
return ret; //返回被删掉的元素
}< 5 > peek方法：
peek方法是返回栈顶的元素，但不删除栈顶元素：
同样在使用peek方法时，我们需要判断栈是否为空，若为空，则需要抛出异常：
public int peek () {
if (empty()) { //判断是否为空
throw new StackEmptyException("该栈为空，不能进行peek操作!!!");
}
return elem[usedSize - 1]; //将栈顶元素进行返回
}< 6 > size方法：
public int size () {
return usedSize; //直接返回usedSize大小
}4. 模拟实现全部源码：
import java.util.Arrays;
public class My_Stack {
int[] elem; //模拟实现栈
int usedSize; //已使用的长度
int DEFAULT_CAPACITY = 10; //默认大小
public My_Stack() {
this.elem = new int[DEFAULT_CAPACITY]; //构造一个大小为默认大小的栈
}
public My_Stack(int n) {
this.elem = new int[n]; //构造一个大小为n的栈
}
public int push (int val) {
if (isFUll()) { //判断栈是否满了，如果满了，则进行扩容
grow(elem);
}
elem[usedSize++] = val; //在数组的最末尾进行插入，并将usedSize++
return val; //返回val的值
}
private boolean isFUll () {
return usedSize == elem.length; //返回数组长度是否等于使用大小 的值
}
private void grow (int[] elem) {
if (elem.length <= 64) {
elem = Arrays.copyOf(elem, elem.length * 2); //如果数组长度小于64，则进行二倍扩容
} else {
elem = Arrays.copyOf(elem, elem.length + elem.length >> 1); //如果大于64，则进行1.5倍扩容
}
}
public int pop () {
if (empty()) {
throw new StackEmptyException("该栈为空，不能进行pop操作!!!");
}
int ret = elem[usedSize]; //将elem[usedSize]的值保存下来
usedSize--; //usedSize--相当于删去数组最后一位元素
return ret; //返回被删掉的元素
}
public boolean empty () {
return usedSize == 0; //判断usedSize是否 = 0 即可
}
public int peek () {
if (empty()) { //判断是否为空
throw new StackEmptyException("该栈为空，不能进行peek操作!!!");
}
return elem[usedSize - 1]; //将栈顶元素进行返回
}
public int size () {
return usedSize; //直接返回usedSize大小
}
}5. 栈的应用场景：
1. 改变元素的序列
例如，将1 2 3 4依次进行入栈操作，期间可以进行出栈操作，那么我们可以得到许多出栈序列；
2. 将递归转换成循环
例如逆序打印链表
// 递归方式
void printList(Node head){
if(null != head){
printList(head.next);
System.out.print(head.val + " ");
}
}
// 循环方式
void printList(Node head){
if(null == head){
return;
}
Stack<Node> s = new Stack<>();
// 将链表中的结点保存在栈中
Node cur = head;
while(null != cur){
s.push(cur);
cur = cur.next;
}下面我为大家推荐几道关于栈的题，有兴趣的朋友可以去练练手：
1. 括号匹配
2. 逆波兰表达式求值
3. 出栈入栈次序匹配
4. 最小栈
以上就是栈的全部内容，感谢大家观看！！！！！