數(shù)據(jù)結(jié)構(gòu)與算法-設(shè)計一個雙端循環(huán)隊列

什么是隊列锋勺？

之前探討過一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)-棧搀崭，那是否有先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)呢？這就是我們本篇需要討論的另外一種操作受限的數(shù)據(jù)結(jié)構(gòu)-隊列虹茶。

隊列（queue）是一種操作受限的線性表刀森，只允許在表的一端進(jìn)行插入操作（入隊enqueue）而在另一端進(jìn)行刪除（出隊dequeue）的線性表踱启。進(jìn)行插入操作的端稱為隊尾，進(jìn)行刪除操作的一端稱為隊頭研底。隊列中沒有數(shù)據(jù)元素時稱為空隊列埠偿。

隊列的操作是按照先進(jìn)先出（first in first out）或后進(jìn)后出（last in last out）的原則進(jìn)行的。因此榜晦，隊列又被稱為FIFO表冠蒋。

隊列的分類

單向隊列（普通隊列）

相對于棧比較而言，隊列的實現(xiàn)稍微復(fù)雜點乾胶，棧的實現(xiàn)我們只需要一個棧頂指針就可以了抖剿，但是隊列需要兩個指針，一個是head指針识窿，指向隊頭斩郎，一個是tail指針，指向隊尾喻频。tail指針的任務(wù)就是尋找空位缩宜。

image

如果我們需要插入f字符串，那么我們只需要執(zhí)行queue[tail] = f即可半抱。
此時head = 0 tail = 6脓恕。
如果我們執(zhí)行兩次出隊操作膜宋，執(zhí)行兩次queue[head++] = null即可窿侈。
此時head = 2 tail = 6。

image

定義抽象類型

Queue.java

public interface Queue<T> extends Iterable<T> {
  void offer(T elem);
  T poll();
  T peek();
  int size();
  boolean isEmpty();
}

基于數(shù)組實現(xiàn)的隊列被稱為順序隊列

如何判斷隊空還是隊滿秋茫？

隊空：tail = queue.length

隊滿：head = tail

代碼實現(xiàn)

public class ArrayQueue<T> implements Queue<T> {

  private Object[] data;
  private int head;
  private int tail;
  private int size;
  private int capacity;
  private static final int DEFAULT_CAPACITY = 10;

  public ArrayQueue() {
    this(DEFAULT_CAPACITY);
  }

  public ArrayQueue(int capacity) {
    this.data = new Object[capacity];
    this.head = 0;
    this.tail = 0;
    this.capacity = capacity;
  }

  @Override
  public void offer(T elem) {
    if (tail == capacity) {
      return;
    }
    data[tail++] = elem;
    size++;
  }

  @Override
  public T poll() {
    if (isEmpty()) {
      throw new NoSuchElementException("queue is empty!");
    }
    T t = element(head);
    data[head] = null;
    head++;
    size--;
    return t;
  }

  @Override
  public T peek() {
    if (isEmpty()) {
      throw new NoSuchElementException("queue is empty!");
    }
    T t = element(head);
    return t;
  }

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

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

  @SuppressWarnings("unchecked")
  private T element(int index) {
    return (T) data[index];
  }

  @Override
  public Iterator<T> iterator() {
    return new Iterator<T>() {
      private int index = head;

      @Override
      public boolean hasNext() {
        return index < tail;
      }

      @Override
      public T next() {
        return element(index++);
      }

      @Override
      public void remove() {
        throw new UnsupportedOperationException();
      }
    };
  }
}

基于數(shù)組實現(xiàn)的隊列會有這樣一種情況：

例如上述的例子史简，出隊兩次之后，head = 2 tail = 6，head之前的兩個位置就會空著圆兵，但是我們隊滿的判斷是tail == capacity跺讯，所以出隊的話，head總要自增殉农，之前的位置就為空刀脏，如果此時tail移到最右邊，head之前還有位置超凳，此時的隊列是不滿的愈污，然而要入隊的話可能就會導(dǎo)致入隊失敗，那么我們需要對入隊的代碼轮傍，優(yōu)化下暂雹。

image

那么我們怎么實現(xiàn)，head前面的位置是空创夜，我們還能執(zhí)行入隊操作呢杭跪，對！就是利用數(shù)據(jù)搬移的技術(shù)驰吓。代碼如下：

// moved是否需要數(shù)據(jù)搬移
public void enqueue(T elem, boolean moved) {
    if (elem == null) {
      throw new NullPointerException();
    }
    if (isFull()) {
      doubleCapacity();
    }
    if (head != 0 && tail == capacity && moved) {
      System.arraycopy(data, head, data, 0, tail - head);
      for (int i = 0; i < head; i++) {
        data[data.length - i - 1] = null;
      }
      tail -= head;
      head = 0;
    }
    data[tail++] = elem;
    size++;
 }

實際上涧尿，基于數(shù)組實現(xiàn)的隊列還有一個問題，就是需要初始化數(shù)組大小檬贰，如果隊滿就不能添加元素现斋，所以想要添加元素，我們可以使用動態(tài)數(shù)組來實現(xiàn)偎蘸，對內(nèi)部數(shù)組進(jìn)行擴(kuò)容庄蹋，代碼如下：

private void doubleCapacity() {
  int newCapacity = capacity << 1;
  if (newCapacity < 0) {
    throw new IllegalStateException("illegal Capacity: " + newCapacity);
  }
  Object[] newData = new Object[newCapacity];
  System.arraycopy(data, head, newData, 0, tail - head);
  data = newData;
}

不過還是建議不要擴(kuò)容，不要使用數(shù)組來實現(xiàn)無界隊列迷雪，想要實現(xiàn)無界隊列限书，可以使用鏈表。

基于鏈表實現(xiàn)的隊列被稱為鏈?zhǔn)疥犃?/h4>

public class LinkedQueue<T> implements Queue<T> {

  private Node<T> head;
  private Node<T> tail;

  private int size;

  @Override
  public void offer(T elem) {
    if (tail == null) {
      Node<T> newNode = new Node<>(elem, null);
      head = newNode;
      tail = newNode;
    } else {
      tail.next = new Node<>(elem, null);
      tail = tail.next;
    }
    size++;
  }

  @Override
  public T poll() {
    if (isEmpty()) {
      throw new NoSuchElementException("queue is empty!");
    }
    T value = head.data;
    head = head.next;
    if (head == null) {
      tail = null;
    }
    size--;
    return value;
  }

  @Override
  public T peek() {
    if (isEmpty()) {
      throw new NoSuchElementException("queue is empty!");
    }
    T value = head.data;
    return value;
  }

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

  @Override
  public boolean isEmpty() {
    return head == null;
  }

  @Override
  public Iterator<T> iterator() {
    return new Iterator<T>() {
      private Node<T> p = head;

      @Override
      public boolean hasNext() {
        return p != null;
      }

      @Override
      public T next() {
        T data = p.data;
        p = p.next;
        return data;
      }
    };
  }

  private static class Node<T> {
    private T data;
    private Node<T> next;

    public Node(T data, Node<T> next) {
      this.data = data;
      this.next = next;
    }
  }
}

基于鏈表實現(xiàn)的隊列章咧，從代碼中可以看出倦西，鏈?zhǔn)疥犃惺遣恍枰獢U(kuò)容，不需要數(shù)據(jù)搬移赁严，也不需要判斷隊滿扰柠，這是一個無界隊列。這會引發(fā)一個問題疼约，如果無限添加數(shù)據(jù)卤档，有可能這個隊列會很大，造成內(nèi)存溢出或者其他意想不到的錯誤程剥。

循環(huán)隊列

我們剛才使用數(shù)組來實現(xiàn)的隊列劝枣，當(dāng)tail = n && head != 0 的時候，執(zhí)行入隊操作，會有數(shù)據(jù)搬移的操作舔腾，這樣入隊操作就會受到影響溪胶，畢竟數(shù)據(jù)搬移的操作時間復(fù)雜度為O(n)。想要解決這個問題稳诚，我們可以使用鏈?zhǔn)疥犃谢┎保擎準(zhǔn)疥犃幸灿袉栴}，就是可能會產(chǎn)生內(nèi)存溢出扳还。那有沒有更好的方案去實現(xiàn)呢?

之前我們學(xué)過循環(huán)鏈表懒熙，那隊列是否也可以循環(huán)起來利用呢？當(dāng)tail == capacity && head != 0的時候普办，是否可以將tail = 0呢工扎？對，就是這樣去實現(xiàn)一個循環(huán)隊列衔蹲，這樣既能解決入隊會有數(shù)據(jù)搬移的操作肢娘，也能解決無界問題，實現(xiàn)有界隊列舆驶。

image

注意：循環(huán)隊列會浪費一個數(shù)組的存儲空間橱健。

就為什么循環(huán)隊列會浪費一個數(shù)組的存儲空間，談?wù)勎覍Υ说睦斫馍沉紫任覀儼凑枕樞蜿犃械娜腙牪僮鱽硌菔疽幌隆?/p>

初始化一個容量為8的循環(huán)隊列拘荡，front=rear=0；
如果我們按照之前的順序隊列的實現(xiàn)方案來說的話撬陵，A進(jìn)隊珊皿，我們需要執(zhí)行queue[rear] = A;rear++;
重復(fù)步驟2，因此讓BCDEFG進(jìn)隊巨税，那此時就是rear = 7;
此時H進(jìn)隊蟋定，rear=7的位置確實有個空位，那H進(jìn)隊以后草添，執(zhí)行queue[rear]=H;驶兜。由于是循環(huán)隊列，所以執(zhí)行rear=0远寸；
由于rear指針的認(rèn)為是尋找空位抄淑，但是queue[0]是有元素的，rear不能設(shè)置為0驰后，所以應(yīng)該在rear=7的時候就應(yīng)該判斷出此時已經(jīng)隊滿肆资，不能讓H進(jìn)隊。
其實主要問題是循環(huán)隊列判斷隊滿的條件是什么倡怎？如果不浪費空間迅耘，我們應(yīng)該如何判斷呢？rear=queue.length?注意這是循環(huán)隊列监署，如果僅僅是這么判斷是不行的颤专，front指針可能會在任意位置。rear=front=0也不能表示隊滿钠乏，也有可能隊空栖秕。這樣確實不好判斷，如果要判斷晓避，我們可能需要引入第三方變量簇捍，也是需要一個額外的空間去存儲queue的size。那如果浪費一個存儲空間呢俏拱？此時隊空的判斷條件依然是front==rear暑塑，隊滿的判斷條件(rear + 1)%queue.length = front

代碼實現(xiàn)：

public class ArrayCircularQueue<T> implements Queue<T> {

  private Object[] data;
  private int head;
  private int tail;
  private int n;
  private static final int DEFAULT_CAPACITY = 10;

  public ArrayCircularQueue() {
    this(DEFAULT_CAPACITY);
  }

  public ArrayCircularQueue(int capacity) {
    data = new Object[capacity + 1];
    head = 0;
    tail = 0;
    n = capacity + 1;
  }

  @Override
  public void offer(T elem) {
    if (isFull()) {
      throw new RuntimeException("Queue is full");
    }
    data[tail] = elem;
    tail = adjustIndex(tail);
  }

  @Override
  public T poll() {
    if (isEmpty()) {
      throw new RuntimeException("Queue is empty");
    }
    T element = element(head);
    head = adjustIndex(head);
    return element;
  }

  @Override
  public T peek() {
    if (isEmpty()) {
      throw new RuntimeException("Queue is empty");
    }
    return element(head);
  }

  @Override
  public int size() {
    return (tail + n - head) >= n ? tail - head : tail + n - head;
  }

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

  public boolean isFull() {
    return (tail + 1) % n == head;
  }

  @Override
  public Iterator<T> iterator() {
    return new Iterator<T>() {
      private int p = head;

      @Override
      public boolean hasNext() {
        return p != tail;
      }

      @Override
      public T next() {
        return element(p++);
      }
    };
  }

  private int adjustIndex(int index) {
    return (index + 1) % n;
  }

  @SuppressWarnings("unchecked")
  private T element(int index) {
    return (T) data[index];
  }
}

雙端隊列

雙端隊列（deque）是指允許兩端都可以進(jìn)行入隊和出隊操作的隊列，deque 是 “double ended queue” 的簡稱锅必。那就說明元素可以從隊頭出隊和入隊事格，也可以從隊尾出隊和入隊。

雙端隊列也是有兩種實現(xiàn)方式

基于數(shù)組實現(xiàn)的可以參考Java源碼java.util.ArrayDeque
基于鏈表實現(xiàn)的可以參考java源碼java.util.LinkedList

雙端循環(huán)隊列代碼示例：

public class ArrayCircularDeque<T> implements Deque<T> {

  private int head;
  private int tail;
  private Object[] data;
  private int n;

  private static final int DEFAULT_CAPACITY = 10;

  public ArrayCircularDeque() {
    this(DEFAULT_CAPACITY);
  }

  public ArrayCircularDeque(int capacity) {
    data = new Object[capacity + 1];
    head = 0;
    tail = 0;
    n = capacity + 1;
  }

  @Override
  public void offerFirst(T t) {
    if (isFull()) {
      throw new RuntimeException("deque is full");
    }
    head = (head - 1 + n) % n;
    data[head] = t;
  }

  @Override
  public void offerLast(T t) {
    if (isFull()) {
      throw new RuntimeException("deque is full");
    }
    data[tail] = t;
    tail = (tail + 1) % n;
  }

  @Override
  public T pollFirst() {
    if (isEmpty()) {
      throw new RuntimeException("deque is empty");
    }
    T elements = elements(head);
    data[head] = null;
    head = (head + 1) % n;
    return elements;
  }

  @Override
  public T pollLast() {
    if (isEmpty()) {
      throw new RuntimeException("deque is empty");
    }
    T elements = elements(tail);
    data[tail] = null;
    tail = (tail - 1 + n) % n;
    return elements;
  }

  @Override
  public T peekFirst() {
    if (isEmpty()) {
      throw new RuntimeException("deque is empty");
    }
    return elements(head);
  }

  @Override
  public T peekLast() {
    if (isEmpty()) {
      throw new RuntimeException("deque is empty");
    }
    return elements((tail - 1 + n) % n);
  }

  @Override
  public void offer(T elem) {
    offerLast(elem);
  }

  @Override
  public T poll() {
    return pollFirst();
  }

  @Override
  public T peek() {
    return peekFirst();
  }

  @Override
  public int size() {
    return (tail + n - head) >= n ? tail - head : tail + n - head;
  }

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

  public boolean isFull() {
    return (tail + 1) % n == head;
  }

  @Override
  public Iterator<T> iterator() {
    return new Iterator<T>() {
      private int p = head;

      @Override
      public boolean hasNext() {
        return p != tail;
      }

      @Override
      public T next() {
        return elements(p++);
      }
    };
  }

  @SuppressWarnings("unchecked")
  private T elements(int index) {
    return (T) data[index];
  }
}

其余分類

下面的隊列的分類舉例搞隐，應(yīng)該都屬于隊列的使用的實際案例驹愚，不太屬于隊列的分類，我覺得歸類為實際使用案例會更加貼切一點吧劣纲。下面的代碼目前不提供手動代碼實現(xiàn)逢捺，優(yōu)先級隊列可以等我們討論堆這樣一種數(shù)據(jù)結(jié)構(gòu)的時候，再來詳細(xì)的討論癞季。阻塞隊列和并發(fā)隊列等以后學(xué)習(xí)并發(fā)編程的時候再來詳細(xì)討論劫瞳。下面只提供一些概念上的內(nèi)容，不提供具體代碼實現(xiàn)绷柒。

優(yōu)先級隊列

優(yōu)先隊列中的每個元素都有各自的優(yōu)先級柠新，優(yōu)先級最高的元素最先得到服務(wù)；優(yōu)先級相同的元素按照其在優(yōu)先隊列中的順序得到服務(wù)辉巡。優(yōu)先隊列往往用堆來實現(xiàn)恨憎。

java.util.PriorityQueue

阻塞隊列

簡單來說，在隊列的基礎(chǔ)上加上了阻塞操作郊楣。隊空的時候憔恳，不允許出隊，阻塞净蚤，等有數(shù)據(jù)才返回钥组。隊滿的時候，不允許入隊今瀑，等有空閑位置才能插入程梦。

那么其實這就是一個典型的点把，生產(chǎn)者，消費者模型Ｓ旄健＠商印！

這種基于阻塞隊列實現(xiàn)的生產(chǎn)者挺份，消費者模型褒翰，可以有效地協(xié)調(diào)生產(chǎn)和消費的速度。當(dāng)生產(chǎn)者生產(chǎn)的數(shù)據(jù)速度過快匀泊，消費者來不及消費优训，存儲數(shù)據(jù)的隊列很快滿了，這個時候生產(chǎn)者就阻塞等待各聘，直到消費者消費了數(shù)據(jù)揣非。生產(chǎn)者才會被喚醒繼續(xù)生產(chǎn)。

我們還可以協(xié)調(diào)生產(chǎn)者消費者的個數(shù)躲因，來提高數(shù)據(jù)的處理效率妆兑。

java.util.concurrent.ArrayBlockingQueue

并發(fā)隊列

最簡單的方式就是在enqueue,dequeue方法上加鎖，但是鎖粒度大并發(fā)度會比較低毛仪，同一時刻僅允許一個存或者取搁嗓。實際上，基于數(shù)組實現(xiàn)的循環(huán)隊列箱靴，利用CAS原子操作腺逛，可以實現(xiàn)非常高效的并發(fā)隊列，這就是循環(huán)隊列比鏈?zhǔn)疥犃袘?yīng)用更加廣泛的原因衡怀。

java.util.concurrent.ConcurrentLinkedQueue

隊列的應(yīng)用場景

線程池棍矛，java和python中的并發(fā)編程里，在線程池中都有隊列的身影抛杨。

線程池沒有空閑線程時够委，新的任務(wù)請求線程資源時，線程池該如何處理怖现？各種處理策略又是如何實現(xiàn)的呢茁帽？我們一般有兩種處理策略。第一種是非阻塞的處理方式屈嗤，直接拒絕任務(wù)請求潘拨；另一種是阻塞的處理方式，將請求排隊饶号，等到有空閑線程時铁追，取出排隊的請求繼續(xù)處理。那如何存儲排隊的請求呢茫船？我們希望公平地處理每個排隊的請求琅束，先進(jìn)者先服務(wù)扭屁，所以隊列這種數(shù)據(jù)結(jié)構(gòu)很適合來存儲排隊請求。

我們前面說過涩禀，隊列有基于鏈表和基于數(shù)組這兩種實現(xiàn)方式料滥。這兩種實現(xiàn)方式對于排隊請求又有什么區(qū)別呢？

基于鏈表的實現(xiàn)方式埋泵，可以實現(xiàn)一個支持無限排隊的無界隊列（unbounded queue）幔欧，但是可能會導(dǎo)致過多的請求排隊等待罪治，請求處理的響應(yīng)時間過長丽声。所以，針對響應(yīng)時間比較敏感的系統(tǒng)觉义，基于鏈表實現(xiàn)的無限排隊的線程池是不合適的雁社。

而基于數(shù)組實現(xiàn)的有界隊列（bounded queue），隊列的大小有限晒骇，所以線程池中排隊的請求超過隊列大小時霉撵，接下來的請求就會被拒絕，這種方式對響應(yīng)時間敏感的系統(tǒng)來說洪囤，就相對更加合理徒坡。不過，設(shè)置一個合理的隊列大小瘤缩，也是非常有講究的喇完。隊列太大導(dǎo)致等待的請求太多，隊列太小會導(dǎo)致無法充分利用系統(tǒng)資源剥啤、發(fā)揮最大性能锦溪。

除了前面講到隊列應(yīng)用在線程池請求排隊的場景之外，隊列可以應(yīng)用在任何有限資源池中府怯，用于排隊請求刻诊，比如數(shù)據(jù)庫連接池等。實際上牺丙，對于大部分資源有限的場景则涯，當(dāng)沒有空閑資源時，基本上都可以通過“隊列”這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)請求排隊冲簿。

除了池化資源還有那些排隊場景呢是整？
- 超市排隊結(jié)賬
- 肯德基排隊取餐
- Web服務(wù)器請求管理
可以用來跟蹤最近添加的X個元素。當(dāng)隊列中超過的x個元素民假，只要將超過的元素從隊頭中取出浮入，那么剩下的就是最近添加的x個元素。
- 經(jīng)典的滑動窗口算法
廣度優(yōu)先搜索(BFS)圖遍歷

隊列的復(fù)雜度分析

操作	復(fù)雜度
enqueue	`O(1)` 如果涉及到數(shù)據(jù)搬移羊异，擴(kuò)容那就是`o(n)`
dequeue	`O(1)`
peek	`O(1)`

棧和隊列的區(qū)別

棧是先進(jìn)后出事秀，隊列是先進(jìn)先出彤断。
棧主要是兩個操作，入棧易迹，出棧宰衙。隊列主要是兩個操作，入隊睹欲，出隊
棧只允許在一端進(jìn)行操作供炼，隊列只允許一端進(jìn)行刪除，另一端插入窘疮。

總結(jié)

隊列最大的特點就是先進(jìn)先出袋哼，主要的兩個操作是入隊和出隊。
用數(shù)組實現(xiàn)的叫順序隊列闸衫，用鏈表實現(xiàn)的叫鏈?zhǔn)疥犃小?/p>
在數(shù)組實現(xiàn)隊列的時候涛贯，會有數(shù)據(jù)搬移操作，要想解決數(shù)據(jù)搬移的問題蔚出，我們需要循環(huán)隊列弟翘。
循環(huán)隊列最難的地方是要確定好隊空和隊滿的判定條件。
循環(huán)隊列解決了兩個問題骄酗，數(shù)據(jù)搬移和無界稀余。
循環(huán)隊列為什么需要浪費一個數(shù)組的存儲空間，我的理解是為了更方便的判斷隊滿的條件趋翻，不需要引入size這個變量睛琳，不需要額外的內(nèi)存空間，如果在并發(fā)編程里也無需考慮size變量的線程安全性嘿歌。
雙端隊列比普通隊列的操作更加靈活掸掏。
其余的高級隊列，我的理解是隊列的一種應(yīng)用宙帝。例如阻塞隊列丧凤，并發(fā)隊列，優(yōu)先級隊列步脓。
隊列的應(yīng)用場景很廣泛愿待，主要是判斷出是否是一個排隊的請求。池化資源靴患，訂單系統(tǒng)等等仍侥。