隊(duì)列是編程中一種有用的數(shù)據(jù)結(jié)構(gòu)。類似于電影院外的售票隊(duì)列，第一個(gè)進(jìn)入隊(duì)列的人就是第一個(gè)拿到票的人。

Java隊(duì)列遵循先進(jìn)先出 (FIFO)規(guī)則 - 先進(jìn)入的項(xiàng)目是先出的項(xiàng)目。

在上圖中，由于 1 在 2 之前保留在隊(duì)列中，因此它也是第一個(gè)從隊(duì)列中刪除的。它遵循先進(jìn)先出規(guī)則。

在編程術(shù)語(yǔ)中，將項(xiàng)目放入隊(duì)列稱為enqueue，從隊(duì)列中移除項(xiàng)目稱為dequeue。

我們可以使用任何編程語(yǔ)言(如 C、C++、Java、Python 或 C#)實(shí)現(xiàn)隊(duì)列，但規(guī)范幾乎相同。

隊(duì)列的基本操作

隊(duì)列是一個(gè)對(duì)象(一種抽象數(shù)據(jù)結(jié)構(gòu) - ADT)，它允許以下操作：

Enqueue : 向隊(duì)列末尾添加一個(gè)元素

Dequeue : 從隊(duì)列前面移除一個(gè)元素

IsEmpty : 檢查隊(duì)列是否為空

IsFull : 檢查隊(duì)列是否已滿

Peek：獲取隊(duì)列前端的值而不移除它

隊(duì)列的工作

隊(duì)列操作的工作方式如下：

兩個(gè)指針和跟蹤隊(duì)列的第一個(gè)元素

跟蹤隊(duì)列的最后一個(gè)元素

最初，設(shè)置值和-1

入隊(duì)操作

檢查隊(duì)列是否已滿

對(duì)于第一個(gè)元素，設(shè)置值到 0

增加索引 1

在指向的位置添加新元素 

出隊(duì)操作

檢查隊(duì)列是否為空

返回指向的值增加索引 1

對(duì)于最后一個(gè)元素，重置值和-1

我們通常使用數(shù)組來(lái)實(shí)現(xiàn) Java 和 C/++ 中的隊(duì)列。對(duì)于 Python，我們使用列表。

// Queue implementation in Java
public class Queue {
  int SIZE = 5;
  int items[] = new int[SIZE];
  int front, rear;
  Queue() {
    front = -1;
    rear = -1;
  }
  boolean isFull() {
    if (front == 0 && rear == SIZE - 1) {
      return true;
    }
    return false;
  }
  boolean isEmpty() {
    if (front == -1)
      return true;
    else
      return false;
  }
  void enQueue(int element) {
    if (isFull()) {
      System.out.println("Queue is full");
    } else {
      if (front == -1)
        front = 0;
      rear++;
      items[rear] = element;
      System.out.println("Inserted " + element);
    }
  }
  int deQueue() {
    int element;
    if (isEmpty()) {
      System.out.println("Queue is empty");
      return (-1);
    } else {
      element = items[front];
      if (front >= rear) {
        front = -1;
        rear = -1;
      } /* Q has only one element, so we reset the queue after deleting it. */
      else {
        front++;
      }
      System.out.println("Deleted -> " + element);
      return (element);
    }
  }

  void display() {
    /* Function to display elements of Queue */
    int i;
    if (isEmpty()) {
      System.out.println("Empty Queue");
    } else {
      System.out.println("\nFront index-> " + front);
      System.out.println("Items -> ");
      for (i = front; i <= rear; i++)
        System.out.print(items[i] + "  ");

      System.out.println("\nRear index-> " + rear);
    }
  }

  public static void main(String[] args) {
    Queue q = new Queue();

    // deQueue is not possible on empty queue
    q.deQueue();

    // enQueue 5 elements
    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);
    q.enQueue(4);
    q.enQueue(5);

    // 6th element can't be added to because the queue is full
    q.enQueue(6);

    q.display();

    // deQueue removes element entered first i.e. 1
    q.deQueue();

    // Now we have just 4 elements
    q.display();

  }
}

復(fù)雜性分析

使用數(shù)組的隊(duì)列中入隊(duì)和出隊(duì)操作的復(fù)雜度為O(1)。如果您pop(N)在 python 代碼中使用，那么復(fù)雜性可能O(n)取決于要彈出的項(xiàng)目的位置。

隊(duì)列的應(yīng)用

CPU調(diào)度、磁盤調(diào)度

當(dāng)兩個(gè)進(jìn)程之間異步傳輸數(shù)據(jù)時(shí)，隊(duì)列用于同步。例如：IO Buffers、管道、文件IO等

處理實(shí)時(shí)系統(tǒng)中的中斷。

呼叫中心電話系統(tǒng)使用隊(duì)列將呼叫他們的人按順序排列。