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

2020-12-14

字数统计: 1.1k字 | 阅读时长≈ 4分

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

基于数组实现队列的原理：

基于数组实现的队列，使用两个指针，一个是head指针，指向的是队头；一个是tail指针，指向队尾。可以通过下面这张图片来进行理解，当a，b，c，d依次入队之后，队列中的head指针指向下标为0的位置，而tail指针指向的是下标为4的位置。当需要入队操作时，先进行判断一下该队列是否已满，判断的条件为：tail等于队列的长度n。如果队列已满，就返回fasle，否则，进行入队操作，同时tail进行自加，往后退一位；当需要出队操作时，先判断一下该队列是否为空，如果队列为空，则返回null值，判断条件为：head == tail，否则就将下标为head的值进行出队列操作，然后head再自加，即往后移动一位。

package com.company;

//用数组实现的队列，也叫顺序队列
public class ArrayQueue {
    //数组：items， 数组大小：n
    private String[] items;
    private int n = 0;
    //head表示对头的下标，tail表示对尾下标
    private int head = 0;
    private int tail = 0;

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

    //入队
    public boolean enqueue(String item){
        //如果tail==n，表示队列已经满了
        if(tail == n) return false;
        items[tail] = item;
        ++tail;
        return true;
    }

    //出队
    public String dequeue(){
        //如果head == tail，表示队列为空
        if(head == tail) return null;
         String ret = items[head];
        ++head;
        return ret;
    }

    public static void main(String[] args) {
        ArrayQueue arrayQueue = new ArrayQueue(20);
        arrayQueue.enqueue("abc");
        arrayQueue.enqueue("edf");
        arrayQueue.enqueue("hij");
        String a = arrayQueue.dequeue();
        String b = arrayQueue.dequeue();
        System.out.println(a);
        System.out.println(b);
    }
}

实现的结果为：

1
2

abc
edf

通过输出的结果，可以看出队列是一种”先进先出”的数据结构。

但是，你肯定也会发现，随着不停地进行入队，出队操作，head和tail都会持续往后移动。当tail移动到最右边，即使数组中还有空闲空间，也没有办法继续往队列中添加数据了。在以前的数组中，也遇到类似的情况，就是数组删除操作会导致数组中的数据不连续，当时采用的方法为数据搬移！但是，在队列中每一次进行出队操作时都相当于删除数组下标为0的数据，要搬移整个队列中的数据，这的确是一种办法，但是它会使得这样的出队操作的时间复杂度由原来的O(1)变为O(n)，大大增加了时间复杂度。

其实，我们还有另外一种解决方法，就是如果没有空闲空间了，我们只需要在入队时，再集中触发一次数据的搬移操作。借助这个思想，我们只需要稍微改造一下入队函数enqueue()的实现，就能够轻松地解决问题了。下面为具体的代码：

//入队操作，将item放入队尾
public boolean enqueue(String item){
  //如果tail==n，表示队列已经满了
  if(tail == n){
    //tail == n && head == 0，表示整个队列都占满了
    if(head == 0) return false;
    //数据搬移
    for(int i=head; i<tail; ++i){
      items[i-head] = items[i];
    }
    //搬移完了重新更新head和tail
    tail -= head;
    head = 0;
  }
  items[tail] = item;
  ++tail;
  return true;
}

原理图如下：

从这张图片中就能够更好地理解，队列中入队操作时的数据搬移。当tail==n时，再进行入队操作时，就要利用这种方法进行数据搬移操作，这样是一次性的数据搬移，并不像数组中的数据，每次删除数组中的数据就需要实现整体数据进行搬移。在这种实现思路中，出队操作的时间复杂度仍然是O(1)，并且出队操作的时间复杂度还是O(1)。这时，应该会有小伙伴会有疑问了，你是已经整体移动tail-head个数据了吗，如果数据足够大，那不就是时间复杂度为n吗？其实，这种想法是片面的。我们知道最差的时间复杂度为n，最好的时间复杂度为1，而一般来讲，tail-head个数据一般情况下都能够看做是常数的，用均摊分析法，那么这个入队操作的时间复杂度为O(1)的。

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