基于数组实现循环队列（基于Java实现）

2020-12-14

字数统计: 727字 | 阅读时长≈ 2分

基于数组实现循环队列（基于Java实现）

基于数组实现循环队列的方法原理：

我们在用数组实现队列的时候，发现当tail = n时，就会有数据搬移的操作，这样一来入队操作的性能就会受到影响。那我们可以使用循环队列来解决这一问题。

循环队列，顾名思义，它长得像一个环。如下图所示：

我们可以看到，图中这个队列的大小为 8，当前 head=4，tail=7。当有一个新的元素 a 入队时，我们放入下标为 7 的位置。但这个时候，我们并不把 tail 更新为 8，而是将其在环中后移一位，到下标为 0 的位置。当再有一个元素 b 入队时，我们将 b 放入下标为 0 的位置，然后 tail 加 1 更新为 1。所以，在 a，b 依次入队之后，循环队列中的元素就变成了下面的样子：

通过上述的这种方法，就能够成功地避免数据搬移操作。但是要实现这个循环队列的代码难度比之前的非循环队列的代码实现要更难。其最为关键的是，确定好队空和队满的判定条件。

在循环队列中，你会发现队空的判断条件是：tail = head，而队满的条件是：(tail+1) % n = head。为什么队满的条件会是这个呢？其实你根据上述循环队列的插入删除操作，你就会发现当队列满的时候，tail和head之间是相邻，相差为1，又因为插入的时候，主要是在移动tail指针，所以它的队满的操作为(tail+1) % n = head。如下图，为一张队满的示意图：

具体实现代码如下：

package com.company;

public class CircularQueue {
    //数组：items，数组大小：n
    private String[] items;
    private int n = 0;
    //head表示对头下标，tail表示队尾下标
    private int head = 0;
    private int tail = 0;

    //申请一个大小为capacity的数组
    public CircularQueue(int capacity){
        items = new String[capacity];
        n = capacity;
    }

    //入队
    public boolean enqueue(String item){
        //队列满了
        if((tail + 1) % n == head) return false;
        items[tail] = item;
        tail = (tail + 1) % n;
        return true;
    }

    //出队
    public String dequeue(){
        //如果head==tail 表示队列为空
        if(head == tail) return null;
        String ret = items[head];
        head = (head + 1) % n;
        return ret;
    }
  
  
  public static void main(String[] args) {
        CircularQueue circularQueue = new CircularQueue(20);
        circularQueue.enqueue("abc");
        circularQueue.enqueue("edf");
        circularQueue.enqueue("hij");
        String a = circularQueue.dequeue();
        String b = circularQueue.dequeue();
        System.out.println(a);
        System.out.println(b);

    }
}

输出的结果：

1
2

abc
edf

通过上述的代码，可以知道虽然循环队列解决之前的数据搬移的情况，但是它带来一个缺点，就是当队列满的时候，tail指针指向的实际位置是没有存储数据的，所以，循环会浪费一个数组的存储空间。

本文作者： feng之锋
本文链接： http://example.com/2020/12/14/基于数组实现循环队列/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！