你有用过 java中的栈和队列吗？怎么用栈来实现队列呢

深碍√TFBOYSˉ_ 2023-10-01 23:53 3阅读 0赞

## 一、前言 ##

本篇文章从栈和队列的定义到 java实现，再到 LeetCode 232题来实现一下，怎么用栈来实现队列

在今天我开始刷栈和队列相关算法了，在 java中栈和队列的类是 Stack和 Queue， 但是在 java中我好像很少甚至根本就没有写过相关的代码，不知道小伙伴们是不是和我一样，这次就借着刷 LeetCode的机会来重温一下相关的知识

## 二、栈和队列 ##

### 基础知识 ###

栈和队列的基础知识应该是耳熟能详的了吧，栈是**先进后出**，队列是**先进先出**示

栈有两种实现方式，一种是数组，一种是链表，栈的先进后出如图所示：

![format_png][]

队列的先进先出如图所示：

![format_png 1][]

### java中的栈 ###

在 java中，类 Stack实现了一个标准的先入后出堆栈，通过查看源代码我们可以发现，Stack类实现了 Vector类

> Vector类实现了动态数组，和 ArrayList相似，但是两者是不同的
> 
>  *  Vector是同步的
>  *  vector包含了许多方法，这些方法是不属于集合框架的

通过 idea的方法提示，我们可以看到 Stack自定义了以下五个方法他们的作用分别是：

*  push： 压栈，也可以称为进栈
 *  empty：判断当前栈是否为null
 *  peek: 查看栈顶部对象，不将其删除
 *  pop: 删除该堆栈的顶部对象，并返回所删除的对象
 *  search: 返回对象在堆栈中的位置，以 1为基数，0表示理想对象，返回值为 int类型

![format_png 2][]

下面我们对 Stack类进行方法测试，测试结果如下图所示：

*  创建栈对象
 *  判断当前栈是否为空
 *  进行压栈，压栈元素为 a
 *  判断当前栈是否为空
 *  查看栈顶部对象
 *  进行压栈，压栈元素为 b
 *  查看栈顶部对象
 *  调用父类 Vector的方法，查看当前栈内的元素
 *  查看元素 a在栈中的位置
 *  查看元素 b在栈中的位置
 *  查看栈顶对象，并删除
 *  调用父类 Vector的方法，查看当前栈内的元素

![format_png 3][]

> 对栈不熟悉的建议花几分钟去调用方法看一下，虽然可能大概不常用

### java中的队列 ###

在 java中的队列是 Queue，但是这个类是一个接口，它定义了队列相关的方法，具体实现要看他的子类

![format_png 4][]

Queue定义的方法如下：

*  add：添加元素，失败会抛出异常
 *  offer：添加元素
 *  remove：删除元素，失败会抛出异常
 *  poll：返回第一个元素，并删除
 *  element：返回第一个元素
 *  peek：查看栈顶元素，不将其删除

本篇文章以 LinkedList为例去试验一下队列的几个方法，后面有机会的话，可以专门出一篇文章讲一下队列

![format_png 5][]

## 三、实践 ##

俗话说得好，好记性不如烂笔头，有没有学明白试一下就知道了，刚好今天做了 LeetCode上的一道题目，两个知识点都有所涉及

### LeetCode 232. 用栈实现队列 ###

#### 题目描述 ####

![format_png 6][]

#### 规定代码格式 ####

同时 LeetCode规定了我们实现的代码格式，并告诉我们将要以下面注释部分的方式去实例化和调用我们实现的 MyQueue

![format_png 7][]

#### 思路分析 ####

*  通过本篇文章前面的讲解，我们了解了栈和队列的定义和基本方法
 *  由于栈是**先进后出**，队列是**先进先出**，那么想要用栈来实现队列肯定要有两个栈
 *  一个栈用来存储元素，第二个栈用来模拟队列的先入先出
 *  队列中添加元素 in栈中压入元素
 *  队列中弹出元素，in栈的元素弹出并压入 out栈，全部压入后弹出首元素
 *  具体如下图所示

![format_png 8][]

> 注意题中 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中

![format_png 9][]

#### 提交结果 ####

![format_png 10][]

## 总结 ##

事实证明小白刷 LeetCode还是有用的，不仅能学习到更多的知识，也能够对已有的知识加深印象

[format_png]: https://img-blog.csdnimg.cn/img_convert/bb20d06df0ad8df289af15379888191e.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/af80018acd00440d8bd974930ce6102f.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/8ab67795e25af3cae69d91839cd15f9d.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/f7eb5debcc3d41e516da6673159af0e9.webp?x-oss-process=image/format,png
[format_png 4]: https://img-blog.csdnimg.cn/img_convert/ac1e6214af0364a2beea8253f77da48e.webp?x-oss-process=image/format,png
[format_png 5]: https://img-blog.csdnimg.cn/img_convert/4bb0c18a9ed01fd2c4096e8b069714b2.webp?x-oss-process=image/format,png
[format_png 6]: https://img-blog.csdnimg.cn/img_convert/807c3ab946b53612bf8eb610e6e5ad84.webp?x-oss-process=image/format,png
[format_png 7]: https://img-blog.csdnimg.cn/img_convert/d61cfe91152ede1570e39e3d0af3e426.webp?x-oss-process=image/format,png
[format_png 8]: https://img-blog.csdnimg.cn/img_convert/3c21fc70eba4d24faac0cfa06be9b0de.webp?x-oss-process=image/format,png
[format_png 9]: https://img-blog.csdnimg.cn/img_convert/518a5595780d0731b2bd52fe42e34c09.webp?x-oss-process=image/format,png
[format_png 10]: https://img-blog.csdnimg.cn/img_convert/9737e2a775c000494eaf5c6308fbde0a.webp?x-oss-process=image/format,png