数据结构06 队列

笔记仓库：https://github.com/nnngu/LearningNotes

---

上一篇讲了栈，这一篇要讲的是我们常用的队列，我会从以下几个方面进行总结。

1、什么是队列 

2、队列的存储结构

3、队列的常用操作及实现代码

1、什么是队列 

（1）首先，队列也是一种特殊的线性表，它是一种操作受限的线性表。只允许在表的一端进行元素插入，而在另一端进行元素删除。允许插入的一端称为队尾，允许删除的一端称为队头。

（2）队列与现实生活中的排队类似（如下图），新加入的成员总是在队尾，而排在队列最前面的总是最先离开队列，即先进先出 First In First Out (FIFO)，因此队列就是先进先出线性表。

 （3）线性表分为顺序表和链表，所以队列也分为顺序队列和链式队列，为了方便演示，下文所使用的队列都是顺序队列。

2、队列的存储结构

用java语言自己封装一个顺序队列：

SeqQueue.java

/**
 * 封装一个顺序队列
 */
public class SeqQueue {
    // 保存数据
    public Object[] data;

    // 头指针
    public int head;

    // 尾指针
    public int rear;

    // 队列的最大容量
    public int maxSize;

    public SeqQueue(int maxSize) {
        this.maxSize = maxSize;
        data = new Object[maxSize];
    }
}

3、队列的常用操作及实现代码

3-1、初始化队列

思路：构造一个空队列，并将头指针head和尾指针rear都设置为0。

代码：SeqQueueOperate.java

/**
 * 封装队列的常见操作
 */
public class SeqQueueOperate {
    /**
     * 初始化
     *
     * @param maxSize
     * @return
     */
    public SeqQueue init(int maxSize) {
        SeqQueue queue = new SeqQueue(maxSize);
        queue.head = 0;
        queue.rear = 0;
        return queue;
    }
}

3-2、入队

思路：若队列没有满，则将数据插入到尾指针rear指向的位置，然后再将rear加1。

代码：在 SeqQueueOperate.java 中添加方法

    /**
     * 入队
     */
    public void enter(SeqQueue queue, Object obj) {
        // 判断队列是否已经满了
        if (queue.rear >= queue.maxSize) {
            return;
        }
        queue.data[queue.rear] = obj;
        queue.rear++;
    }

3-3、出队

思路：若队列不为空，则将头指针指向的元素删除，然后将头指针加1。

代码：在 SeqQueueOperate.java 中添加方法

    /**
     * 出队
     */
    public Object dequeue(SeqQueue queue) {
        // 判断队列是否为空
        if (queue.head == queue.rear) {
            return null;
        }
        Object obj = queue.data[queue.head];
        queue.data[queue.head] = null;
        queue.head++;
        return obj;
    }

3-4、取队头

思路：若队列不为空，则返回队头元素。

代码：在 SeqQueueOperate.java 中添加方法

    /**
     * 取队头
     */
    public Object getHead(SeqQueue queue) {
        // 判断队列是否为空
        if (queue.head == queue.rear) {
            return null;
        }
        Object obj = queue.data[queue.head];
        return obj;
    }

3-5、取队长

思路：即尾指针 - 头指针的值。

代码：在 SeqQueueOperate.java 中添加方法

    /**
     * 取队长
     */
    public int getLength(SeqQueue queue) {
        return queue.rear - queue.head;
    }

3-6、判队空

思路：只需要判断头指针和尾指针是否相等即可

代码：在 SeqQueueOperate.java 中添加方法

    /**
     * 判断队列是否为空
     */
    public boolean isEmpty(SeqQueue queue) {
        return queue.head == queue.rear;
    }

3-7、判队满

思路：只需判断尾指针与maxSize是否相等即可

代码：在 SeqQueueOperate.java 中添加方法

    /**
     * 判断队列是否已经满了
     */
    public boolean isFull(SeqQueue queue) {
        return queue.rear >= queue.maxSize;
    }

4、测试

添加一个用来测试的类

QueueTest.java

/**
 * 用来测试
 */
public class QueueTest {
    public static void main(String[] args) {
        SeqQueueOperate seqQueueOperate = new SeqQueueOperate();
        // 最大容量设置为5
        int maxSize = 5;
        SeqQueue queue = seqQueueOperate.init(maxSize);
        System.out.println("队列的最大容量是：" + maxSize);

        // 当前队列的长度
        System.out.println("当前队列的长度是：" + seqQueueOperate.getLength(queue));
        System.out.println("");

        System.out.println("===========入队start ===========");
        System.out.println("插入6个元素试试");
        seqQueueOperate.enter(queue, 1);
        seqQueueOperate.enter(queue, 2);
        seqQueueOperate.enter(queue, 3);
        seqQueueOperate.enter(queue, 4);
        seqQueueOperate.enter(queue, 5);
        seqQueueOperate.enter(queue, 6);
        System.out.println("===========入队end =============");
        // 当前队列的长度
        System.out.println("当前队列的长度是：" + seqQueueOperate.getLength(queue));
        System.out.println("");

        // 出队
        System.out.println("===========出队start ===========");
        Object obj = seqQueueOperate.dequeue(queue);
        System.out.println("出队的元素是：" + obj);
        System.out.println("===========出队end =============");
        // 当前队列的长度
        System.out.println("当前队列的长度是：" + seqQueueOperate.getLength(queue));
        System.out.println("");

        System.out.println("------------------------------------");
        System.out.println("队头元素是：" + queue.data[queue.head]);
        System.out.println("队尾元素是：" + queue.data[queue.rear-1]);
    }
}

测试结果：

 注意：在一个非空的队列中，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一个位置。