🍀栈(Stack)
🎋栈的概念
🎈栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则
- 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
- 出栈：栈的删除操作叫做出栈。出数据在栈顶。
比如下面数据的出栈与进栈
就像枪的弹匣一样，先压进去的子弹，最后出来
🎍栈的使用
在java中，提供了这些方法用于操作栈
使用如下：
import java.util.Stack; public class Main { public static void main(String[] args) { Stack<Integer> s = new Stack(); s.push(1); s.push(2); s.push(3); s.push(4); System.out.println(s.size()); // 获取栈中有效元素个数---> 4 System.out.println(s.peek()); // 获取栈顶元素---> 4 s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3 System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3 if(s.empty()){ System.out.println("栈为空"); }else{ System.out.println(s.size()); } } }
🌳 栈的模拟实现
从下图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的
接下来我们模拟实现一个栈
🚩栈的创建
我们创建一个MyStack的类，用于模拟实现我们的栈
- 我们的这里的模拟栈用数组的形式给大家呈现
- 创建一个int型的elem数组
- 再创建一个usedSize的常数，用于记录栈中元素个数
- 再给一个构造方法，构造栈初始的长度
代码实现如下：
public class MyStack { public int[] elem; public int usedSize; public MyStack() { this.elem = new int[10]; } }
🚩栈是否为空
若usedSize为0则为空，所以直接比较返回就好
代码实现如下
public boolean isEmpty() { return usedSize == 0; }
🚩压栈
做法如下：
- 首先对现有栈进行判断是否为满，若满则需要进行扩容
- 若没有满，则只需要将该元素放在数组elem下标为usedSize的位置
- 然后usedSize加一即可
代码实现如下：
//压栈 public void push(int val) { if(isFull()) { //扩容 elem = Arrays.copyOf(elem,2*elem.length); } elem[usedSize++] = val; } public boolean isFull() { return usedSize == elem.length; }
🚩出栈
做法如下：
- 首先得判断栈是否为空，若为空我们需要抛出异常
- 这里我们自定义一个异常为EmptyException如下
public class EmptyException extends RuntimeException{ public EmptyException() { } public EmptyException(String message) { super(message); } }
- 若不为空，则usedSize变为usedSize-1
- 然后返回usedSize下标的元素即可
代码实现如下：
//出栈 public int pop() { if(isEmpty()) { throw new EmptyException("栈是空的！"); } return elem[--usedSize]; } public boolean isEmpty() { return usedSize == 0; }
🚩获取栈顶元素
做法如下：
- 我们同样需要对栈进行是否为空的判断
- 若为空，抛出我们自定义栈为空的异常EmptyException
- 若不为空，则返回数组elem下标为usedSize-1的元素
代码实现如下：
public int peek() { if(isEmpty()) { throw new EmptyException("栈是空的！"); } return elem[usedSize-1]; }
🚩MyStack完整代码实现
import java.util.Arrays; public class MyStack { public int[] elem; public int usedSize; public MyStack() { this.elem = new int[10]; } //压栈 public void push(int val) { if(isFull()) { //扩容 elem = Arrays.copyOf(elem,2*elem.length); } elem[usedSize++] = val; } public boolean isFull() { return usedSize == elem.length; } //出栈 public int pop() { if(isEmpty()) { throw new EmptyException("栈是空的！"); } return elem[--usedSize]; } public boolean isEmpty() { return usedSize == 0; } public int peek() { if(isEmpty()) { throw new EmptyException("栈是空的！"); } return elem[usedSize-1]; } }
自定义异常
public class EmptyException extends RuntimeException{ public EmptyException() { } public EmptyException(String message) { super(message); } }
🎄概念区分（栈、虚拟机栈、栈帧）
栈（stack） ：是只允许在一端进行插入或删除的线性表，满足后入先出的特点。
虚拟机栈 ：逻辑结构，是具有特殊作用的一块内存空间 。 主管Java程序的运行，它保存方法的局部变量 (8种基本数据类型、对象的引用地址)、部分结果，并参与方法的调用和返回。
栈帧 ：函数从调用过程到结束的体现，一个函数从调用到销毁其中占用的空间，内部的局部变量统一放在栈帧中。 每个函数在运行时，jvm都会创建一个栈帧，然后将栈帧压入到虚拟机栈中，当函数调用结束时，该函数对应的栈帧会从虚拟机栈中出栈。
⭕总结
关于《 【数据结构】 栈（Stack）与栈的模拟实现》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！
