一、前言

本篇文章从栈和队列的定义到 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还是有用的，不仅能学习到更多的知识，也能够对已有的知识加深印象