数据结构之队列

(注释：整篇数据结构与算法文集，部分总结于王争的《数据结构与算法之美》和李明杰的《恋上数据结构与算法》，加上自己的理解，所以出了这个文集，仅做个人笔记记录所用。如你需要，请购买他们的正版资源，支持他们的原创)

队列是一种特殊的线性表，只能在头尾两端进行操作

• 队尾(rear):只能从队尾添加元素，一般叫做 enQueue，入队
• 队头(front):只能从队头移除元素，一般叫做 deQueue，出队
• 先进先出的原则，First In First Out，FIFO

队列接口的设计

• int size(); // 元素的数量
• boolean isEmpty(); // 是否为空
• void clear(); // 清空
• void enQueue(E element); // 入队
• E deQueue(); // 出队
• E front(); // 获取队列的头元素

队列的内部实现是否可以直接利用以前学过的数据结构?

动态数组、链表
优先使用双向链表，因为队列主要是往头尾操作元素

用栈来实现队列

https://leetcode-cn.com/problems/implement-queue-using-stacks/

WechatIMG145.png

双端队列

双端队列是能在头尾两端添加、删除的队列
-英文 deque 是 double ended queue 的简称

双端队列接口的设计 (可用链表来便捷的 实现双端队列)

-int size(); // 元素的数量
-boolean isE mpty(); // 是否为空
-void clear(); // 清空
-void enQueueRear(E element);// 从队尾入队
-E deQueueRear(); // 从队尾出队
-void enQueueFront(E element); // 从队头入队
-E deQueueFront(); // 从队头出队
-E front(); // 获取队列的头元素
-E rear(); // 获取队列的尾元素

用数组来实现队列

// 用数组实现的队列
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;
  }
}

当 a、b、c、d 依次入队之后，队列中的 head 指针指向下标为 0 的位置，tail 指针指向下标为 4 的位置。

image.png

当我们调用两次出队操作之后，队列中 head 指针指向下标为 2 的位置，tail 指针仍然指向下标为 4 的位置。

image.png
你肯定已经发现了，随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。这个问题该如何解决呢？

   // 入队操作，将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 指针移动到数组的最右边后，如果有新的数据入队，我们可以将 head 到 tail 之间的数据，整体搬移到数组中 0 到 tail-head 的位置。

image.png

这只是数组实现队列的其中一种的解法。之后空间还不足的话就需要动态扩容或者使用循环队列等等技术了。

循环队列 (可以理解为循环利用的队列)

以下内容为王争的授课内容，采用数组，辅以双指针的方式，先来看看双指针方式实现循环队列。

我们刚才用数组来实现队列的时候，在 tail==n 时，会有数据搬移操作，这样入队操作性能就会受到影响。那有没有办法能够避免数据搬移呢？

我们来看看循环队列的解决思路。循环队列，顾名思义，它长得像一个环。原本数组是有头有尾的，是一条直线。现在我们把首尾相连，扳成了一个环。我画了一张图，你可以直观地感受一下。

image.png

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

image.png

通过这样的方法，我们成功避免了数据搬移操作。看起来不难理解，但是循环队列的代码实现难度要比前面讲的非循环队列难多了。要想写出没有 bug 的循环队列的实现代码，我个人觉得，最关键的是，确定好队空和队满的判定条件。

在用数组实现的非循环队列中，队满的判断条件是 tail == n，队空的判断条件是 head == tail。那针对循环队列，如何判断队空和队满呢？

队列为空的判断条件仍然是 head == tail。但队列满的判断条件就稍微有点复杂了。我画了一张队列满的图，你可以看一下，试着总结一下规律。

image.png

就像我图中画的队满的情况，tail=3，head=4，n=8，所以总结一下规律就是：(3+1)%8=4。多画几张队满的图，你就会发现，当队满时，(tail+1)%n=head。

你有没有发现，当队列满时，图中的 tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。(为什么要浪费一个数组的存储空间，我的理解是这样的，其实主要问题就是为了能够很好的判断队满的条件是什么？如果不浪费一个数组空间，可能需要引入其他变量，去记录队列的实际容量，也是需要额外的内存空间，那如果浪费了一个数组空间，可以在不需要引入额外的变量的情况下，给出队满的判断条件。)

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;
  }
}

下面是MJ使用数组辅以单指针的方式，来实现循环队列。 (单指针是省略了尾指针，使用 (front+size)%length的方式求出最后一个要添加的位置，其实也就等同于上面的尾指针了。其实头指针也容易越界，所以也要取模操作front = (front + 1)%length )。下面代码实现循环队列的同时做了动态扩容。

package com.mj.circle;

@SuppressWarnings("unchecked")
public class CircleQueue<E> {
    private int front;
    private int size;
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;
    
    public CircleQueue() {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }
    
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
    
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[index(i)] = null;
        }
        front = 0;
        size = 0;
    }

    public void enQueue(E element) {
       //入队前先判断容量够不够存，size是当前容量，size + 1就是需要看看有没有额外一个容量，有的话才能add
        ensureCapacity(size + 1);
        // element[(front+size)%elements.length] = element;
        elements[index(size)] = element;
        size++;
    }

    public E deQueue() {
        E frontElement = elements[front];
        elements[front] = null;
        //front = (front + 1)%length ;
        front = index(1);
        size--;
        return frontElement;
    }

    public E front() {
        return elements[front];
    }
    
    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("capcacity=").append(elements.length)
        .append(" size=").append(size)
        .append(" front=").append(front)
        .append(", [");
        for (int i = 0; i < elements.length; i++) {
            if (i != 0) {
                string.append(", ");
            }
            
            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }
    
//因为几处地方都用到了(*+front)%elements.length，所以把这个提出来，需要的地方直接把*传进来。
    private int index(int index) {

                return  (front + index)%elements.length;
        
                //index += front;
        //return index - (index >= elements.length ? elements.length : 0);
    }
    
    /**
     * 保证要有capacity的容量
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        
        // 新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            //扩容时数据搬迁不是单纯的的0元素放0元素，而是front元素放在新的数组0的位置，依次放入。
            //newElements[i] = elements[(i+front)%elements.length];
            newElements[i] = elements[index(i)];
        }
        elements = newElements;
        
        // 重置front
        front = 0;
    }
}

循环双端队列(此处使用了数组来实现循环双端队列。因为如果用链表太过于 简单)

循环双端队列相比上面的循环队列，特别需要注意的是在头部入队的问题。其实头部坐标也很好解决。如果0的位置有值的话，依旧往头部入队，其实是要入到整个数组的最后一个元素处，如果front-1的话就变成-1了，此时如果-1+length的话就是需要入队的头部位置了

      package com.mj.circle;

@SuppressWarnings("unchecked")
public class CircleDeque<E> {
    private int front;
    private int size;
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;
    
    public CircleDeque() {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }
    
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[index(i)] = null;
        }
        front = 0;
        size = 0;
    }

    /**
     * 从尾部入队
     * @param element
     */
    public void enQueueRear(E element) {
        ensureCapacity(size + 1);
        
        elements[index(size)] = element;
        size++;
    }

    /**
     * 从头部出队
     * @param element
     */
    public E deQueueFront() {
        E frontElement = elements[front];
        elements[front] = null;
        front = index(1);
        size--;
        return frontElement;
    }

    /**
     * 从头部入队
     * @param element
     */
    public void enQueueFront(E element) {
        ensureCapacity(size + 1);
        
        front = index(-1);
        elements[front] = element;
        size++;
    }

    /**
     * 从尾部出队
     * @param element
     */
    public E deQueueRear() {
        int rearIndex = index(size - 1);
        E rear = elements[rearIndex];
        elements[rearIndex] = null;
        size--;
        return rear;
    }

    public E front() {
        return elements[front];
    }

    public E rear() {
        return elements[index(size - 1)];
    }

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("capcacity=").append(elements.length)
        .append(" size=").append(size)
        .append(" front=").append(front)
        .append(", [");
        for (int i = 0; i < elements.length; i++) {
            if (i != 0) {
                string.append(", ");
            }
            
            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }
    
    private int index(int index) {
       //先让front和index相加，看看是不是负数。如果是负数就说明是从头部入队，此时加上整个数组长度就可得到入队坐标。如果是正数，就按着之前的取模。
        index += front;
        if (index < 0) {
            return index + elements.length;
        }
        return index %  elements.length;
       //上面的那句取模运算可以优化
      /**
      n = 11 (坐标)
      m = 10 (数组长度)
      在此处n限定于小于2m的情况下
      if(n>=m){
      return n-m;
      }else {
      return n;
      }
      所以可以总结为下面这句
      return index - (index >= elements.length ? elements.length : 0);
      */
        
    }
    
    /**
     * 保证要有capacity的容量
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        
        // 新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[index(i)];
        }
        elements = newElements;
        
        // 重置front
        front = 0;
    }
}