队列 02 循环队列

队列接口Queue

  • 用接口Queue表示队列这种数据结构,具体的实现因底层使用到的数据结构的不同而不同;
public interface Queue<E> {

    int getSize();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E getFront();

}

循环队列LoopQueue

  • front 作为索引,指向队首的元素;
  • tail 作为索引,指向队尾元素的下一格,即新入队的元素要待的位置;
  • 队列为空的条件是 front == tail;
  • 队列为满的条件是 (tail + 1) % data.length == front;
  • 因为 capacity 中的空间要浪费一个,所以在初始化的时候是 (E[])new Object[capacity + 1] ,即:要创建容量为 10 的队列,就要在底层开辟一个长度为 10+1=11 的数组;
  • 同样的原因,在返回队列容量的时候,返回的是底层数组的长度减 1,即 data.length - 1,即:队列的容量是 10,底层数组的长度是 11,返回 11-1=10;
public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    private int front;
    private int tail;
    private int size;

    public LoopQueue(int capacity){
        data = (E[])new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue(){
        this(10);
    }

    public int getCapacity(){
        return data.length - 1;
    }

    @Override
    public boolean isEmpty(){
        return front == tail;
    }

    @Override
    public int getSize(){
        return size;
    }

    @Override
    public void enqueue(E e){
        if((tail + 1) % data.length == front)
            resize(getCapacity() * 2);

        data[tail] = e;
        tail = (tail + 1) % data.length;
        size ++;
    }

    @Override
    public E dequeue(){
        if(isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size --;
        if(size == getCapacity() / 4 && getCapacity() / 2 != 0)
            resize(getCapacity() / 2);
        return ret;
    }

    @Override
    public E getFront(){
        if(isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return data[front];
    }

    private void resize(int newCapacity){
        E[] newData = (E[])new Object[newCapacity + 1];
        for(int i = 0 ; i < size ; i ++)
            newData[i] = data[(i + front) % data.length];

        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
        res.append("front [");
        for(int i = front ; i != tail ; i = (i + 1) % data.length){
            res.append(data[i]);
            if((i + 1) % data.length != tail)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }

    public static void main(String[] args){
        LoopQueue<Integer> queue = new LoopQueue<>();
        for(int i = 0 ; i < 10 ; i ++){
            queue.enqueue(i);
            System.out.println(queue);

            if(i % 3 == 2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }

}
输出:

Queue: size = 1 , capacity = 10
front [0] tail
Queue: size = 2 , capacity = 10
front [0, 1] tail
Queue: size = 3 , capacity = 10
front [0, 1, 2] tail
Queue: size = 2 , capacity = 5
front [1, 2] tail
Queue: size = 3 , capacity = 5
front [1, 2, 3] tail
Queue: size = 4 , capacity = 5
front [1, 2, 3, 4] tail
Queue: size = 5 , capacity = 5
front [1, 2, 3, 4, 5] tail
Queue: size = 4 , capacity = 5
front [2, 3, 4, 5] tail
Queue: size = 5 , capacity = 5
front [2, 3, 4, 5, 6] tail
Queue: size = 6 , capacity = 10
front [2, 3, 4, 5, 6, 7] tail
Queue: size = 7 , capacity = 10
front [2, 3, 4, 5, 6, 7, 8] tail
Queue: size = 6 , capacity = 10
front [3, 4, 5, 6, 7, 8] tail
Queue: size = 7 , capacity = 10
front [3, 4, 5, 6, 7, 8, 9] tail

特别关注1:void enqueue(E e)

  • 当队列满时,队列要扩容;
  • 在维护游标 tail 的时候,不是简单的 tail++ ,而是 tail = (tail + 1) % data.length;
@Override
public void enqueue(E e){
    if((tail + 1) % data.length == front)
        resize(getCapacity() * 2);

    data[tail] = e;
    tail = (tail + 1) % data.length;
    size ++;
}

特别关注2:void resize(int newCapacity)

  • 扩容时的思路还是新建一个数组,把数组 data 中的元素复制到新数组中;
  • 新建数组的容量对应到底层开辟数组的长度还是要加 1,即 (E[])new Object[newCapacity + 1];
  • 老数组的元素在往新数组中“掉”的时候,注意老数组的队首元素和新数组索引为 0 的元素之间有一个 front 的偏移量;再加上老数组上的游标是从 front 开始,从 front 开始循环遍历,故新数组的游标 i 和老数组上的游标的对应关系为:i 对应 (i + front) % data.length;
  • 完成复制后,让游标 front 指向新数组的 0,游标 tail 指向新数组的 size;
  • 在刚复制完成的时候,size 逻辑上是队列的元素个数,作为索引指向新入队的元素将要待的位置;
private void resize(int newCapacity){
    E[] newData = (E[])new Object[newCapacity + 1];
    for(int i = 0 ; i < size ; i ++)
        newData[i] = data[(i + front) % data.length];

    data = newData;
    front = 0;
    tail = size;
}

特别关注3:E dequeue()

  • 出队的时候,若队列为空,则不允许出队操作;
  • 在取出队首元素和返回队首元素之间有两个操作:维护游标 front 和队列元素个数 size,缩容;
  • 维护游标 front 的时候,不是简单的 front++,而是让 front 在 data.length 的范围内“循环游走”,即:front = (front + 1) % data.length;
  • 缩容的时候采用 lazy 的策略,元素个数为容量 1/4 时,容量缩小为 1/2 ;
  @Override
public E dequeue(){
    if(isEmpty())
        throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

    E ret = data[front];

    data[front] = null;
    front = (front + 1) % data.length;
    size --;

    if(size == getCapacity() / 4 && getCapacity() / 2 != 0)
        resize(getCapacity() / 2);

    return ret;
}
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 一、基本数据类型 注释 单行注释:// 区域注释:/* */ 文档注释:/** */ 数值 对于byte类型而言...
    龙猫小爷阅读 4,532评论 0赞 16
  • 今天我们来介绍下集合Queue中的几个重要的实现类。关于集合Queue中的内容就比较少了。主要是针对队列这种数据结...
    Ruheng阅读 8,811评论 4赞 27
  • 容器的概念所谓STL容器,即是将最常运用的一些数据结构(data structures)实现出来。容器是指容纳特定...
    饭饭H阅读 495评论 0赞 0
  • 在泰国的时候,网上认识了一位在厦门读书的泰国女孩。很聊得来,因为她学的是汉语教学。她希望我在她毕业的时候我...
    阿木先森阅读 413评论 0赞 1
  • 愁,愁,愁 愁上心头,欲哭无泪。 唉声叹气,笔下矛盾。 窗外细雨,纷纷扰扰。 点点滴滴,汇不成行。 烦、烦、烦 此...
    小馒头0601阅读 276评论 0赞 1

友情链接更多精彩内容