# 隊列 > 原文： [https://www.programiz.com/dsa/queue](https://www.programiz.com/dsa/queue) #### 在本教程中，您將學習什么是隊列。 此外，您還將發現使用 C，C++ ，Java 和 Python 實現隊列的實現。 隊列是編程中有用的數據結構。 它類似于電影院大廳外面的售票隊列，在該隊列中，第一個進入隊列的人是第一個獲得票的人。 隊列遵循**先進先出（FIFO）**規則-先進入的項目也是先出來的項目。  FIFO 表示 在上圖中，由于 1 在 2 之前保留在隊列中，因此它也是第一個從隊列中刪除的隊列。 它遵循 **FIFO** 規則。 用編程術語來說，將項目放入隊列稱為“入隊”，而將項目從隊列中刪除則稱為“出隊”。 我們可以使用任何編程語言（例如 C，C++ ，Java，Python 或 C# ）來實現隊列，但是規范幾乎是相同的。 * * * ## 隊列規范 隊列是一個對象，或更具體地說，是一個允許執行以下操作的抽象數據結構（ADT）： * `enqueue`：將元素添加到隊列的末尾 * `dequeue`：從隊列的開頭刪除元素 * **`IsEmpty`**：檢查隊列是否為空 * **`IsFull`**：檢查隊列是否已滿 * `peek`：獲取隊列前面的值而不刪除它 * * * ## 隊列如何工作 隊列操作如下： 1. 兩個稱為`FRONT`和`REAR`的指針用于跟蹤隊列中的第一個和最后一個元素。 2. 初始化隊列時，我們將`FRONT`和`REAR`的值設置為 -1。 3. 排隊元素時，我們增加`REAR`索引的值，并將新元素放置在`REAR`指向的位置。 4. 在元素出隊時，我們返回`FRONT`指向的值，并增加`FRONT`索引。 5. 在排隊之前，我們檢查隊列是否已滿。 6. 在出隊之前，我們檢查隊列是否已經為空。 7. 當對第一個元素進行排隊時，我們將`FRONT`的值設置為 0。 8. 使最后一個元素出隊時，我們將`FRONT`和`REAR`的值重置為 -1。  隊列操作的原理 * * * ## Python，Java 和 C/C++ 示例 最常見的隊列實現是使用數組，但是也可以使用列表來實現。 ```py # Queue implementation in Python class Queue: def __init__(self): self.queue = [] # Add an element def enqueue(self, item): self.queue.append(item) # Remove an element def dequeue(self): if len(self.queue) < 1: return None return self.queue.pop(0) # Display the queue def display(self): print(self.queue) def size(self): return len(self.queue) q = Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.display() q.dequeue() print("After removing an element") q.display() ``` ```java // 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 queue because 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(); } } ``` ```c // Queue implementation in C #include <stdio.h> #define SIZE 5 void enQueue(int); void deQueue(); void display(); int items[SIZE], front = -1, rear = -1; int main() { //deQueue is not possible on empty queue deQueue(); //enQueue 5 elements enQueue(1); enQueue(2); enQueue(3); enQueue(4); enQueue(5); //6th element can't be added to queue because queue is full enQueue(6); display(); //deQueue removes element entered first i.e. 1 deQueue(); //Now we have just 4 elements display(); return 0; } void enQueue(int value) { if (rear == SIZE - 1) printf("\nQueue is Full!!"); else { if (front == -1) front = 0; rear++; items[rear] = value; printf("\nInserted -> %d", value); } } void deQueue() { if (front == -1) printf("\nQueue is Empty!!"); else { printf("\nDeleted : %d", items[front]); front++; if (front > rear) front = rear = -1; } } // Function to print the queue void display() { if (rear == -1) printf("\nQueue is Empty!!!"); else { int i; printf("\nQueue elements are:\n"); for (i = front; i <= rear; i++) printf("%d ", items[i]); } printf("\n"); } ``` ```cpp // Queue implementation in C++ #include <iostream> #define SIZE 5 using namespace std; class Queue { private: int items[SIZE], front, rear; public: Queue() { front = -1; rear = -1; } bool isFull() { if (front == 0 && rear == SIZE - 1) { return true; } return false; } bool isEmpty() { if (front == -1) return true; else return false; } void enQueue(int element) { if (isFull()) { cout << "Queue is full"; } else { if (front == -1) front = 0; rear++; items[rear] = element; cout << endl << "Inserted " << element << endl; } } int deQueue() { int element; if (isEmpty()) { cout << "Queue is empty" << endl; 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++; } cout << endl << "Deleted -> " << element << endl; return (element); } } void display() { /* Function to display elements of Queue */ int i; if (isEmpty()) { cout << endl << "Empty Queue" << endl; } else { cout << endl << "Front index-> " << front; cout << endl << "Items -> "; for (i = front; i <= rear; i++) cout << items[i] << " "; cout << endl << "Rear index-> " << rear << endl; } } }; int main() { Queue q; //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 queue because 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(); return 0; } ``` * * * ## 此實現的局限性 如您在下圖中所看到的，經過一些入隊和出隊后，隊列的大小已減小。  隊列限制 只有當所有元素都已出隊后，才能在重置隊列后使用索引 0 和 1。 在`REAR`到達最后一個索引之后，如果我們可以在空白空間（0 和 1）中存儲額外的元素，則可以利用這些空白空間。 這通過稱為[循環隊列](/data-structures/circular-queue)的修改隊列來實現。 * * * ## 隊列復雜度 使用數組的隊列中入隊和出隊操作的復雜度為`O(1)`。 * * * ## 隊列應用 * CPU 調度，磁盤調度 * 在兩個進程之間異步傳輸數據時，使用隊列進行同步。 例如：IO 緩沖區，管道，文件 IO 等 * 實時系統中的中斷處理。 * 呼叫中心電話系統使用隊列來保持人們按順序呼叫他們