欧洲久久久久久久在线,色五月婷婷91,人妻在线专区

什么是隊列？

之前探討過一種先進后出的數據結構-棧，那是否有先進先出的數據結構呢？這就是我們本篇需要討論的另外一種操作受限的數據結構-隊列。

隊列（queue）是一種操作受限的線性表，只允許在表的一端進行插入操作（入隊enqueue）而在另一端進行刪除（出隊dequeue）的線性表。進行插入操作的端稱為隊尾，進行刪除操作的一端稱為隊頭。隊列中沒有數據元素時稱為空隊列。

隊列的操作是按照先進先出（first in first out）或后進后出（last in last out）的原則進行的。因此，隊列又被稱為FIFO表。

隊列的分類

單向隊列（普通隊列）

相對于棧比較而言，隊列的實現稍微復雜點，棧的實現我們只需要一個棧頂指針就可以了，但是隊列需要兩個指針，一個是head指針，指向隊頭，一個是tail指針，指向隊尾。tail指針的任務就是尋找空位。

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

基于數組實現的隊列被稱為順序隊列

如何判斷隊空還是隊滿？

隊空：tail = queue.length

隊滿：head = tail

代碼實現

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

基于數組實現的隊列會有這樣一種情況：

例如上述的例子，出隊兩次之后，head = 2 tail = 6，head之前的兩個位置就會空著，但是我們隊滿的判斷是tail == capacity，所以出隊的話，head總要自增，之前的位置就為空，如果此時tail移到最右邊，head之前還有位置，此時的隊列是不滿的，然而要入隊的話可能就會導致入隊失敗，那么我們需要對入隊的代碼，優(yōu)化下。

image

那么我們怎么實現，head前面的位置是空，我們還能執(zhí)行入隊操作呢，對！就是利用數據搬移的技術。代碼如下：

// moved是否需要數據搬移
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++;
 }

實際上，基于數組實現的隊列還有一個問題，就是需要初始化數組大小，如果隊滿就不能添加元素，所以想要添加元素，我們可以使用動態(tài)數組來實現，對內部數組進行擴容，代碼如下：

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

不過還是建議不要擴容，不要使用數組來實現無界隊列，想要實現無界隊列，可以使用鏈表。

基于鏈表實現的隊列被稱為鏈式隊列

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

基于鏈表實現的隊列，從代碼中可以看出，鏈式隊列是不需要擴容，不需要數據搬移，也不需要判斷隊滿，這是一個無界隊列。這會引發(fā)一個問題，如果無限添加數據，有可能這個隊列會很大，造成內存溢出或者其他意想不到的錯誤。

循環(huán)隊列

我們剛才使用數組來實現的隊列，當tail = n && head != 0 的時候，執(zhí)行入隊操作，會有數據搬移的操作，這樣入隊操作就會受到影響，畢竟數據搬移的操作時間復雜度為O(n)。想要解決這個問題，我們可以使用鏈式隊列，但是鏈式隊列也有問題，就是可能會產生內存溢出。那有沒有更好的方案去實現呢?

之前我們學過循環(huán)鏈表，那隊列是否也可以循環(huán)起來利用呢？當tail == capacity && head != 0的時候，是否可以將tail = 0呢？對，就是這樣去實現一個循環(huán)隊列，這樣既能解決入隊會有數據搬移的操作，也能解決無界問題，實現有界隊列。

image

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

就為什么循環(huán)隊列會浪費一個數組的存儲空間，談談我對此的理解，首先我們按照順序隊列的入隊操作來演示一下。

初始化一個容量為8的循環(huán)隊列，front=rear=0；
如果我們按照之前的順序隊列的實現方案來說的話，A進隊，我們需要執(zhí)行queue[rear] = A;rear++;
重復步驟2，因此讓BCDEFG進隊，那此時就是rear = 7;
此時H進隊，rear=7的位置確實有個空位，那H進隊以后，執(zhí)行queue[rear]=H;。由于是循環(huán)隊列，所以執(zhí)行rear=0；
由于rear指針的認為是尋找空位，但是queue[0]是有元素的，rear不能設置為0，所以應該在rear=7的時候就應該判斷出此時已經隊滿，不能讓H進隊。
其實主要問題是循環(huán)隊列判斷隊滿的條件是什么？如果不浪費空間，我們應該如何判斷呢？rear=queue.length?注意這是循環(huán)隊列，如果僅僅是這么判斷是不行的，front指針可能會在任意位置。rear=front=0也不能表示隊滿，也有可能隊空。這樣確實不好判斷，如果要判斷，我們可能需要引入第三方變量，也是需要一個額外的空間去存儲queue的size。那如果浪費一個存儲空間呢？此時隊空的判斷條件依然是front==rear，隊滿的判斷條件(rear + 1)%queue.length = front

代碼實現：

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）是指允許兩端都可以進行入隊和出隊操作的隊列，deque 是 “double ended queue” 的簡稱。那就說明元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊。

雙端隊列也是有兩種實現方式

基于數組實現的可以參考Java源碼java.util.ArrayDeque
基于鏈表實現的可以參考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ōu)先級隊列可以等我們討論堆這樣一種數據結構的時候，再來詳細的討論。阻塞隊列和并發(fā)隊列等以后學習并發(fā)編程的時候再來詳細討論。下面只提供一些概念上的內容，不提供具體代碼實現。

優(yōu)先級隊列

優(yōu)先隊列中的每個元素都有各自的優(yōu)先級，優(yōu)先級最高的元素最先得到服務；優(yōu)先級相同的元素按照其在優(yōu)先隊列中的順序得到服務。優(yōu)先隊列往往用堆來實現。

java.util.PriorityQueue

阻塞隊列

簡單來說，在隊列的基礎上加上了阻塞操作。隊空的時候，不允許出隊，阻塞，等有數據才返回。隊滿的時候，不允許入隊，等有空閑位置才能插入。

那么其實這就是一個典型的，生產者，消費者模型！?。?/strong>

這種基于阻塞隊列實現的生產者，消費者模型，可以有效地協調生產和消費的速度。當生產者生產的數據速度過快，消費者來不及消費，存儲數據的隊列很快滿了，這個時候生產者就阻塞等待，直到消費者消費了數據。生產者才會被喚醒繼續(xù)生產。

我們還可以協調生產者消費者的個數，來提高數據的處理效率。

java.util.concurrent.ArrayBlockingQueue

并發(fā)隊列

最簡單的方式就是在enqueue,dequeue方法上加鎖，但是鎖粒度大并發(fā)度會比較低，同一時刻僅允許一個存或者取。實際上，基于數組實現的循環(huán)隊列，利用CAS原子操作，可以實現非常高效的并發(fā)隊列，這就是循環(huán)隊列比鏈式隊列應用更加廣泛的原因。

java.util.concurrent.ConcurrentLinkedQueue

隊列的應用場景

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

線程池沒有空閑線程時，新的任務請求線程資源時，線程池該如何處理？各種處理策略又是如何實現的呢？我們一般有兩種處理策略。第一種是非阻塞的處理方式，直接拒絕任務請求；另一種是阻塞的處理方式，將請求排隊，等到有空閑線程時，取出排隊的請求繼續(xù)處理。那如何存儲排隊的請求呢？我們希望公平地處理每個排隊的請求，先進者先服務，所以隊列這種數據結構很適合來存儲排隊請求。

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

基于鏈表的實現方式，可以實現一個支持無限排隊的無界隊列（unbounded queue），但是可能會導致過多的請求排隊等待，請求處理的響應時間過長。所以，針對響應時間比較敏感的系統，基于鏈表實現的無限排隊的線程池是不合適的。

而基于數組實現的有界隊列（bounded queue），隊列的大小有限，所以線程池中排隊的請求超過隊列大小時，接下來的請求就會被拒絕，這種方式對響應時間敏感的系統來說，就相對更加合理。不過，設置一個合理的隊列大小，也是非常有講究的。隊列太大導致等待的請求太多，隊列太小會導致無法充分利用系統資源、發(fā)揮最大性能。

除了前面講到隊列應用在線程池請求排隊的場景之外，隊列可以應用在任何有限資源池中，用于排隊請求，比如數據庫連接池等。實際上，對于大部分資源有限的場景，當沒有空閑資源時，基本上都可以通過“隊列”這種數據結構來實現請求排隊。

除了池化資源還有那些排隊場景呢？

超市排隊結賬

肯德基排隊取餐

Web服務器請求管理

可以用來跟蹤最近添加的X個元素。當隊列中超過的x個元素，只要將超過的元素從隊頭中取出，那么剩下的就是最近添加的x個元素。

經典的滑動窗口算法

廣度優(yōu)先搜索(BFS)圖遍歷

隊列的復雜度分析

操作復雜度

enqueue O(1) 如果涉及到數據搬移，擴容那就是o(n)

dequeue O(1)

peek O(1)

棧和隊列的區(qū)別

棧是先進后出，隊列是先進先出。

棧主要是兩個操作，入棧，出棧。隊列主要是兩個操作，入隊，出隊

棧只允許在一端進行操作，隊列只允許一端進行刪除，另一端插入。

總結

隊列最大的特點就是先進先出，主要的兩個操作是入隊和出隊。

用數組實現的叫順序隊列，用鏈表實現的叫鏈式隊列。

在數組實現隊列的時候，會有數據搬移操作，要想解決數據搬移的問題，我們需要循環(huán)隊列。

循環(huán)隊列最難的地方是要確定好隊空和隊滿的判定條件。

循環(huán)隊列解決了兩個問題，數據搬移和無界。

循環(huán)隊列為什么需要浪費一個數組的存儲空間，我的理解是為了更方便的判斷隊滿的條件，不需要引入size這個變量，不需要額外的內存空間，如果在并發(fā)編程里也無需考慮size變量的線程安全性。

雙端隊列比普通隊列的操作更加靈活。

其余的高級隊列，我的理解是隊列的一種應用。例如阻塞隊列，并發(fā)隊列，優(yōu)先級隊列。

隊列的應用場景很廣泛，主要是判斷出是否是一個排隊的請求。池化資源，訂單系統等等。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

數據結構與算法-設計一個雙端循環(huán)隊列

數據結構與算法-設計一個雙端循環(huán)隊列

什么是隊列？

隊列的分類

單向隊列（普通隊列）

定義抽象類型

基于數組實現的隊列被稱為順序隊列

基于鏈表實現的隊列被稱為鏈式隊列

循環(huán)隊列

雙端隊列

其余分類

優(yōu)先級隊列

阻塞隊列

并發(fā)隊列

隊列的應用場景

隊列的復雜度分析

棧和隊列的區(qū)別

總結

友情鏈接更多精彩內容

操作	復雜度
enqueue	`O(1)` 如果涉及到數據搬移，擴容那就是`o(n)`
dequeue	`O(1)`
peek	`O(1)`

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

數據結構與算法-設計一個雙端循環(huán)隊列

什么是隊列？

隊列的分類

單向隊列（普通隊列）

定義抽象類型

基于數組實現的隊列被稱為順序隊列

基于鏈表實現的隊列被稱為鏈式隊列

循環(huán)隊列

雙端隊列

其余分類

優(yōu)先級隊列

阻塞隊列

并發(fā)隊列

隊列的應用場景

隊列的復雜度分析

棧和隊列的區(qū)別

總結

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

什么是隊列？