常见数据结构-队列

基础知识

队列是一种特殊的线性表，他的特殊性在于我们只能操作他头部和尾部的元素，中间的元素我们操作不了，我们只能在他的头部进行删除，尾部进行添加。就像大家排队到银行取钱一样，先来的肯定要排到前面，后来的只能排在队尾，所有元素都要遵守这个操作，没有VIP会员，所以走后门插队的现象是不可能存在的，他是一种先进先出的数据结构。我们来看一下队列的数据结构是什么样的

1，一般队列

image.png

他只能从左边进，右边出，队列实现方式一般有两种，一种是基于数组的，还一种是基于链表的，如果基于链表的倒还好说，因为链表的长度是随时都可以变的，这个实现起来比较简单。如果是基于数组的，就会稍微有点不同，因为数组的大小在初始化的时候就已经固定了，我们来看一下基于数组的实现，假如我们初始化一个长度是10的队列

在这里插入图片描述

front指向的是队列的头，tail指向的是队列尾的下一个存储空间，最初始的时候front=0，tail=0，每添加一个元素tail就加1，每移除一个元素front就加1，但是这样会有一个问题，如果一个元素不停的加入队列，然后再不停的从队列中移除，会导致tail和front越来越大，最后会导致队列无法再加入数据了，但实际上队列前面全部都是空的，这导致空间的极大浪费。我们自己来写一个简单的队列看一下

public class MyQueue<E> {

    private final Object[] data;
    private final int maxSize;
    private int size;
    private int front = 0;
    private int tail = 0;

    public MyQueue(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("队列容量必须大于0 : " + maxSize);
        }
        this.maxSize = maxSize;
        data = new Object[this.maxSize];
    }

    public void add(E e) {
        if (isFull()) {//这地方可以扩容也可以抛异常，为了方便这里我们就不在扩容了。
            throw new IllegalStateException("队列已经满了，无法再加入……");
        }
        data[tail++] = e;
        size++;
    }

    public E remove() {
        if (isEmpty()) {
            throw new IllegalStateException("队列是空的，无法移除……");
        }
        E t = (E) data[front];
        data[front++] = null;
        size--;
        return t;
    }

    //队列头和队列尾指向同一空间的时候，并且没到队尾，表示队列是空的
    public boolean isEmpty() {
        return front == tail && !isFull();
    }

    public boolean isFull() {//最后一个位置是不存储数据的
        return tail == maxSize - 1;
    }

    public int getSize() {
        return size;
    }
}

代码非常简单，当然队列的实现不一定是这一种方式，比如我们可以让tail指向队尾的元素，或者以链表的形式来实现都是可以的，不同的实现方式会导致上面的方法有所不同。我们来测试一下

public static void main(String[] args) {
    MyQueue myQueue = new MyQueue(10);
    System.out.println("isEmpty()=" + myQueue.isEmpty());
    System.out.println("isFull()=" + myQueue.isFull());
    System.out.println("getSize()=" + myQueue.getSize());
    for (int i = 0; i < 9; i++) {
        myQueue.add(i * 100);
        myQueue.remove();
    }
    System.out.println("----------------------------");
    System.out.println("isEmpty()=" + myQueue.isEmpty());
    System.out.println("isFull()=" + myQueue.isFull());
    System.out.println("getSize()=" + myQueue.getSize());
}

看一下打印的结果

    isEmpty()=true
    isFull()=false
    getSize()=0
    ----------------------------
    isEmpty()=false
    isFull()=true
    getSize()=0

我们添加了9次，然后又移除了9次，结果队列竟然满了，如果我们再添加一次的话肯定会抛异常，但实际上队列的size是0，还是空的，也就是说数组的每个位置只能使用一次，这样就造成了极大的浪费。那么前面使用过的空间还能不能再次利用了呢，实际上是可以的，我们可以把队列看成是环形的，当tail到达数组末尾的时候，如果数组的前面有空位子，我们可以让tail从头开始，这个时候一个新的队列就产生了，那就是双端队列。

2，双端队列

双端队列也是有两个指针，front指向队首，tail指向队尾的下一个存储单元，并且双端队列的队首和队尾都可以添加和删除元素，我们来看一下图

在这里插入图片描述

这样空间就可以循环利用了，不会造成浪费，我们来看下代码

public class MyQueue<E> {

    //存储的元素
    private Object[] data;

    //指向队列头，这个头并不是数组的第0个元素，如果这样
    // front就没有意义了，这个从下面的addFirst(E e)方
    // 法也可以看出，如果当front等于0的时候，在添加到
    // first，那么会添加到数组的末尾，并且front也指向
    // 数组的末尾
    private int front;

    //指向队列尾的下一个空间，可以这样理解，front指向
    // 的是第一个元素，tail指向的是最后一个元素的下一
    // 个，指的是空的。
    private int tail;

    public MyQueue(int numElements) {
        data = new Object[numElements];
    }

    //空间扩容，我们这里选择扩大一倍，当然也可以选择其
    // 他值，仅仅当满的时候才能触发扩容， 这时候front
    // 和tail都会指向同一个元素
    private void doubleCapacity() {
        int p = front;
        int n = data.length;//数组的长度
        //关键是r不好理解，举个例子，在数组中，front
        // 不一定是之前0位置的，他可以指向其他位置，
        // 比如原来空间大小为16，front为13，也就是第
        // 14个元素（数组是从0开始的），那么r就是16-13=3，
        // 也就是从front往后还有多少元素，待会copy的时候
        // 也是先从最后的r个元素开始
        int r = n - p;
        Object[] a = new Object[n << 1];//扩大一倍
        System.arraycopy(data, p, a, 0, r);//先copy后面的r个
        System.arraycopy(data, 0, a, r, p);//再copy前面的p个
        data = a;
        //重新调整front和tail的值
        front = 0;
        tail = n;
    }

    public void addFirst(E e) {
        //添加到front的前面，所以front-1
        front = (front - 1 + data.length) % data.length;
        data[front] = e;
        if (front == tail)//判断是否满了
            doubleCapacity();
    }

    public void addLast(E e) {
        //添加到最后一个，这个方法和addFirst有很明显的不同，
        // addFirst是添加的时候就要计算front的位置，而addLast
        // 方法是存值之后在计算tail的，/因为tail位置是没有
        // 存值的，他表示的末端元素的下一个，是空，所以存值之后
        //要计算tail的值
        data[tail] = e;
        tail = (tail + 1) % data.length;
        if (tail == front)//判断是否满
            doubleCapacity();
    }

    public E removeFirst() {//删除第一个
        if (isEmpty())
            throw new IllegalStateException("队列是空的，无法移除……");
        E result = (E) data[front];
        data[front] = null;
        // 删除第一个，这里的所有第一我们都认为是front所指的，
        // 不是数组的0位置，然后在计算front的值
        front = (front + 1) % data.length;
        return result;
    }

    public E removeLast() {//删除最后一个
        if (isEmpty())
            throw new IllegalStateException("队列是空的，无法移除……");
        tail = (tail - 1 + data.length) % data.length;
        E result = (E) data[tail];
        data[tail] = null;
        return result;
    }

    public E peekFirst() {
        if (isEmpty())
            throw new IllegalStateException("队列是空的，无法获取……");
        return (E) data[front];
    }

    public E peekLast() {
        if (isEmpty())
            throw new IllegalStateException("队列是空的，无法获取……");
        return (E) data[(tail - 1 + data.length) % data.length];
    }

    public int size() {//元素的size
        return (tail - front + data.length) % data.length;
    }

    //是否为空，在上面添加元素的时候也可能front==tail，当添加
    // 元素之后front==tail的时候就认为是满了，然后扩容，重新
    // 调整front和tail的值,所以扩容之后front就不可能等于tail。
    //如果没有触发上面添加元素的时候front等于tail我们就认为他是空的。
    public boolean isEmpty() {
        return front == tail;
    }
}

代码中都有详细的注释，就不在过多介绍。