队列: 排队买包子，还不允许插队的那种~

51 阅读 0 评论 34 点赞

我是靠谱客的博主独特外套，最近开发中收集的这篇文章主要介绍队列: 排队买包子，还不允许插队的那种~，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

前言

上一篇文章我们简单阐述了栈这个基本数据结构，我们知道了，栈最大的特点就是后进先出，以及入栈和出栈这两个基本的操作。今天我们再来学习与栈非常相似的另一个数据结构—队列，那么接下来我们看看队列到底是什么吧。

队列是什么

首先，当你看到队列这两个字的时候，你脑袋里面会不会联想到每天在早餐店排队买包子的场景呢？（什么？你不吃早餐），这个时候不考虑插队情况（拒绝插队，从你我做起）的话，那就是站在队列前面的人先买到包子，后来的人只能站在队尾等待，故先来的先买包子，也就是队列的先进先出。

上面我们提到不能插队，这个其实就是队列的限制，只能按照先进先出的规则，所以说队列同栈一样，也是一个操作受限的数据结构。画张图看看队列，如下图所示：

队列的基本操作

队列与栈相似，数组和链表均可以实现队列。其中基于数组实现的队列被称为顺序队列，基于链表实现的队列被称为链式队列。队列支持两种基本操作，分别是入队和出队，数据入队操作是在队列的队尾，数据的出队是在队列的队头。下面我们以基于数组实现的顺序队列为例，看看队列是如何进行入队和出队操作的。

我们先创建一个属于我们的队列，代码就不做解释了，该注释的都注释了，如下代码所示：

/**
 * msJava
 *
 * @Description 基于数组实现顺序队列
 * @Date 2021-08-01
 */
public class MyArrayQueue<E> {

    private Object[] array;
    //队列容量
    private int n=0;
    // 队头
    private int head=0;
    // 队尾
    private int tail=0;

    /**
     * 队列构造
     * @param capacity  队列容量
     */
    public MyArrayQueue(int capacity){
        array=new Object[capacity];
        n=capacity;
    }

    /**
     * 查看当前队列是否为空
     * @return
     */
    public boolean isEmpty() {
        return n == 0;
    }

    /**
     * 遍历当前队列
     */
    public void ergodic(){
        for (int i = head; i < tail; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
    
}

入队

我们先来画张图，再唠两毛钱的入队操作，如下图所示：

如上图中，当6、3、2、1、7、8依次入队之后，此时队头第一个红色块6，队尾是图中黄色块。当有新的数据9入队的时候是直接放到黄色块中的，当数据入队的后，队尾需要向后移动一个位置。

我们已经学习过数组了，知道了数组在创建的时候容量已经确定，那么我们基于数组实现其他的数据结构，比如栈和队列，都必然会涉及到数组已满的情况，那么当实现队列的时候，队列已满的情况，你该怎么办呢？类比我们前面文章谈到了，这个你可以好好想想哦。

队列入队的代码如下：

    /**
     * 入队
     * @param e
     * @return
     */
    public boolean enqueue(E e){
        if(n==tail){
            throw new RuntimeException("队列已满~" );
        }
        array[tail]=e;
        tail++;
        return true;
    }

出队

然后再画张图，我们看看出队操作，如下图所示：

如上图中，当6、3、2等依次出队，每次出队一个数据之后，队头都要向后移动一个位置。队列出队的代码如下：

   /**
     * 出队
     * @return
     */
    public E dequeue(){
        if(head==tail){
            throw new RuntimeException("队列为空~" );
        }
        E ref=(E)array[head];
        ++head;
        return ref;
    }