数据结构奇妙旅程之栈和队列
温馨提示：这篇文章已超过401天没有更新，请注意相关的内容是否还可用！
꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱
ʕ̯•͡˔•̯᷅ʔ大家好，我是xiaoxie.希望你看完之后,有不足之处请多多谅解，让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客
本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶
个人主页：xiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客
系列专栏：xiaoxie的JAVA系列专栏——CSDN博客●'ᴗ'σσணღ*
我的目标:"团团等我💪( ◡̀_◡́ ҂)"
( ⸝⸝⸝›ᴥ‹⸝⸝⸝ )欢迎各位→点赞👍 + 收藏⭐️ + 留言📝+关注（互三必回）!
一.栈（Stack）
1.概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈
顶，另一端称为栈底。栈中的数据元素遵守后进先出 LIFO （ Last In First Out ）的原则。 压栈：栈的插入操作叫做进栈 / 压栈 / 入栈， 入数据在栈顶 。 出栈：栈的删除操作叫做出栈。 出数据在栈顶 。2.栈的模拟实现
可以看出栈Stack 是继承与Vector的， Vector和ArrayList类似，我们可以得到以下的栈的模拟实现，帮助我们更好的理解栈的使用。
//这是栈内存储Integer的模拟，当然栈是泛型，这里只是Integer的模拟
class MyStack {
public int[] arr;
public int size;
public MyStack() {
arr = new int[10];
}
//入栈
public int push(int e) {
ensureCapacity();
arr[size++] = e;
return e;
}
//判断栈是否满
private void ensureCapacity() {
if (size == arr.length) {
arr = Arrays.copyOf(arr, size * 2);
}
}
//栈顶元素
public int peek() {
if(empty()) {
System.out.println("栈为空，无元素");
return -1;
}
return arr[size-1];
}
//出栈
public int pop() {
int tmp = peek();
size--;
return tmp;
}
//判断栈是否为空
public boolean empty() {
return this.size == 0;
}
}
3.栈、虚拟机栈、栈帧有什么区别呢
栈、虚拟机栈和栈帧是计算机科学中的概念，它们之间有以下区别：
-
栈：栈是一种具有后进先出（Last-In-First-Out，LIFO）特性的数据结构，可以存储和检索数据。在计算机中，栈通常用于管理函数调用和局部变量的分配。栈在内存中是连续存储的一块区域，主要用于存储函数调用的上下文信息以及局部变量。
-
虚拟机栈：虚拟机栈是Java虚拟机（JVM）为每个线程分配的内存区域，用于存储方法的调用和执行信息。每个线程在执行方法时，都会在虚拟机栈中创建一个栈帧，栈帧中包含了方法的局部变量、操作数栈、方法返回地址等信息。
-
栈帧：栈帧是方法在虚拟机栈中的表示，用于存储方法的局部变量、操作数栈、方法返回地址等信息。每个方法在执行时，都会在虚拟机栈中创建一个对应的栈帧，方法的参数、局部变量以及中间计算结果都存储在栈帧中。当方法执行完毕后，对应的栈帧就会被销毁。
总结来说，栈是一种数据结构，用于存储和检索数据；虚拟机栈是Java虚拟机为每个线程分配的内存区域，用于存储方法的调用和执行信息；栈帧是方法在虚拟机栈中的表示，用于存储方法的局部变量、操作数栈、方法返回地址等信息。
4.栈的应用
155.最小栈
题目分析：
我们都知道栈是一个先进后出的数据结构，所以我们只使用一个普通栈是无法实现最小栈，应该要用两个栈来模拟实现最小栈。
如果两个栈都为空就先将元素入栈
然后下一个元素先入stack 栈 之后和minstack 比较如果
这样就通过用两个普通栈模拟最小栈了
class MinStack {
Stack stack;
Stack minstack;
public MinStack() {
stack = new Stack();
minstack = new Stack();
}
public void push(int val) {
stack.push(val);
if(minstack.empty()) {
minstack.push(val);
}else {
if(minstack.peek() >= val) {
minstack.push(val);
}
}
}
public void pop() {
int tmp = stack.pop();
if(tmp == minstack.peek()) {
minstack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minstack.peek();
}
}
1.面试进阶
是否可以不用辅助栈呢
栈中每个元素代表的是要压入元素与当前栈中最小值的差值 有个很重要问题： 在弹出时如何维护min？ 因为每次压入新的元素时，压入的都是与当前栈中最小值的差值（还未压入当前元素），故在弹出元素时，若弹出了当前最小值，因为栈中记录了当前元素与【之前】最小值的差值，故根据这个记录可以更新弹出元素后的最小值。 接下来看代码吧
class MinStack {
// 记录每个元素与【未压入】该元素时栈中最小元素的差值
LinkedList stack;
// 当前【已压入】栈中元素的最小值
private long min;
public MinStack() {
stack = new LinkedList();
}
public void push(int val) {
// 压入第一个元素
if(stack.isEmpty()){
min = val;
stack.addFirst(0L);
return;
}
// 栈不为空时，每次压入计算与min的差值后压入结果
stack.push((long)val-min);
// 更新min
min = Math.min((long)val,min);
// 上面两个语句是不能颠倒的！一定是先压入，在更新，因为min一定是当前栈中的最小值
}
public void pop() {
long pop = stack.removeFirst();
// 当弹出元素小于0时，说明弹出元素是当前栈中的最小值，要更新最小值
if(pop
