一、前言
本篇文章从栈和队列的定义到 java 实现，再到 LeetCode 232题来实现一下，怎么用栈来实现队列
在今天我开始刷栈和队列相关算法了，在 java中栈和队列的类是 Stack和 Queue， 但是在 java中我好像很少甚至根本就没有写过相关的代码，不知道小伙伴们是不是和我一样，这次就借着刷 LeetCode的机会来重温一下相关的知识
二、栈和队列
基础知识
栈和队列的基础知识应该是耳熟能详的了吧，栈是 先进后出 ，队列是 先进先出 示
栈有两种实现方式，一种是数组，一种是 链表 ，栈的先进后出如图所示：
队列的先进先出如图所示：
java中的栈
在 java中，类 Stack实现了一个标准的先入后出堆栈，通过查看源代码我们可以发现，Stack类实现了 Vector 类
Vector类实现了动态数组，和 ArrayList相似，但是两者是不同的
- Vector是同步的
- vector包含了许多方法，这些方法是不属于集合框架的
通过 idea 的方法提示，我们可以看到 Stack自定义了以下五个方法他们的作用分别是：
- push： 压栈，也可以称为进栈
- empty：判断当前栈是否为null
- peek: 查看栈顶部对象，不将其删除
- pop: 删除该堆栈的顶部对象，并返回所删除的对象
- search: 返回对象在堆栈中的位置，以 1为基数，0表示理想对象，返回值为 int类型
下面我们对 Stack类进行方法测试，测试结果如下图所示：
- 创建栈对象
- 判断当前栈是否为空
- 进行压栈，压栈元素为 a
- 判断当前栈是否为空
- 查看栈顶部对象
- 进行压栈，压栈元素为 b
- 查看栈顶部对象
- 调用父类 Vector的方法，查看当前栈内的元素
- 查看元素 a在栈中的位置
- 查看元素 b在栈中的位置
- 查看栈顶对象，并删除
- 调用父类 Vector的方法，查看当前栈内的元素
对栈不熟悉的建议花几分钟去调用方法看一下，虽然可能大概不常用
java中的队列
在 java中的队列是 Queue，但是这个类是一个接口，它定义了队列相关的方法，具体实现要看他的子类
Queue定义的方法如下：
- add：添加元素，失败会抛出异常
- offer：添加元素
- remove：删除元素，失败会抛出异常
- poll：返回第一个元素，并删除
- element：返回第一个元素
- peek：查看栈顶元素，不将其删除
本篇文章以 LinkedList为例去试验一下队列的几个方法，后面有机会的话，可以专门出一篇文章讲一下队列
三、实践
俗话说得好，好记性不如烂笔头，有没有学明白试一下就知道了，刚好今天做了 LeetCode上的一道题目，两个知识点都有所涉及
LeetCode 232. 用栈实现队列
题目描述
规定代码格式
同时 LeetCode规定了我们实现的代码格式，并告诉我们将要以下面注释部分的方式去实例化和调用我们实现的 MyQueue
思路分析
- 通过本篇文章前面的讲解，我们了解了栈和队列的定义和基本方法
- 由于栈是 先进后出 ，队列是 先进先出 ，那么想要用栈来实现队列肯定要有两个栈
- 一个栈用来存储元素，第二个栈用来模拟队列的先入先出
- 队列中添加元素 in栈中压入元素
- 队列中弹出元素，in栈的元素弹出并压入 out栈，全部压入后弹出首元素
- 具体如下图所示
注意题中 push方法的入参是 int类型
题中说明：所有操作都是合法的，代表着我们不用判断异常情况
只能使用栈来实现队列
代码展示
public class MyQueue {
Stack<Integer> inStack;
Stack<Integer> outStack;
// 构造方法 初始化 in栈和 out栈
public MyQueue() {
inStack = new Stack<>();
outStack = new Stack<>();
}
// 添加元素
public void push(int x) {
inStack.push(x);
}
public int pop() {
inToOut();
// 弹出 out栈的第一个元素
return outStack.pop();
}
public int peek() {
inToOut();
return outStack.peek();
}
public boolean empty() {
return inStack.empty() && outStack.empty();
}
public void inToOut(){
// 如果 out栈中还有元素，则返回
if (!outStack.empty()){
return;
}
// 只要 in栈元素中还有数据就弹出并添加到 out栈中
while (!inStack.empty()){
outStack.push(inStack.pop());
}
}
}
复制代码 关于pop方法
关于 pop方法在将 inStack栈中的元素压栈到 outStack之后，有的小伙伴可能会有疑问，这里后面为什么没有在把 outStack的元素在压栈会 inStack来保证队列的顺序
下面我画了一个流程图，来表示执行 push操作和 pop操作过程中队列， inStack和 outStack的元素变化情况
我们最后可以看到，outStack就是表明了部分队列的元素顺序，所以不用再 pop过程中重新将 outStack内的元素放入到 inStack中
提交结果
总结
事实证明小白刷 LeetCode还是有用的，不仅能学习到更多的知识，也能够对已有的知识加深印象
