原文： https://www.programiz.com/dsa/queue

在本教程中，您将学习什么是队列。 此外，您还将发现使用 C，C++ ，Java 和 Python 实现队列的实现。

队列是编程中有用的数据结构。 它类似于电影院大厅外面的售票队列，在该队列中，第一个进入队列的人是第一个获得票的人。

队列遵循先进先出（FIFO）规则-先进入的项目也是先出来的项目。

队列 - 图1

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。

队列 - 图2

队列操作的原理

Python，Java 和 C/C++ 示例

最常见的队列实现是使用数组，但是也可以使用列表来实现。

  1. # Queue implementation in Python
  3. class Queue:
  5.     def __init__(self):
  6.         self.queue = []
  8.     # Add an element
  9.     def enqueue(self, item):
  10.         self.queue.append(item)
  12.     # Remove an element
  13.     def dequeue(self):
  14.         if len(self.queue) < 1:
  15.             return None
  16.         return self.queue.pop(0)
  18.     # Display  the queue
  19.     def display(self):
  20.         print(self.queue)
  22.     def size(self):
  23.         return len(self.queue)
  25. q = Queue()
  26. q.enqueue(1)
  27. q.enqueue(2)
  28. q.enqueue(3)
  29. q.enqueue(4)
  30. q.enqueue(5)
  32. q.display()
  34. q.dequeue()
  36. print("After removing an element")
  37. q.display()
  1. // Queue implementation in Java
  3. public class Queue {
  4.   int SIZE = 5;
  5.   int items[] = new int[SIZE];
  6.   int front, rear;
  8.   Queue() {
  9.     front = -1;
  10.     rear = -1;
  11.   }
  13.   boolean isFull() {
  14.     if (front == 0 && rear == SIZE - 1) {
  15.       return true;
  16.     }
  17.     return false;
  18.   }
  20.   boolean isEmpty() {
  21.     if (front == -1)
  22.       return true;
  23.     else
  24.       return false;
  25.   }
  27.   void enQueue(int element) {
  28.     if (isFull()) {
  29.       System.out.println("Queue is full");
  30.     } else {
  31.       if (front == -1)
  32.         front = 0;
  33.       rear++;
  34.       items[rear] = element;
  35.       System.out.println("Inserted " + element);
  36.     }
  37.   }
  39.   int deQueue() {
  40.     int element;
  41.     if (isEmpty()) {
  42.       System.out.println("Queue is empty");
  43.       return (-1);
  44.     } else {
  45.       element = items[front];
  46.       if (front >= rear) {
  47.         front = -1;
  48.         rear = -1;
  49.       } /* Q has only one element, so we reset the queue after deleting it. */
  50.       else {
  51.         front++;
  52.       }
  53.       System.out.println("Deleted -> " + element);
  54.       return (element);
  55.     }
  56.   }
  58.   void display() {
  59.     /* Function to display elements of Queue */
  60.     int i;
  61.     if (isEmpty()) {
  62.       System.out.println("Empty Queue");
  63.     } else {
  64.       System.out.println("\nFront index-> " + front);
  65.       System.out.println("Items -> ");
  66.       for (i = front; i <= rear; i++)
  67.         System.out.print(items[i] + "  ");
  69.       System.out.println("\nRear index-> " + rear);
  70.     }
  71.   }
  73.   public static void main(String[] args) {
  74.     Queue q = new Queue();
  76.     // deQueue is not possible on empty queue
  77.     q.deQueue();
  79.     // enQueue 5 elements
  80.     q.enQueue(1);
  81.     q.enQueue(2);
  82.     q.enQueue(3);
  83.     q.enQueue(4);
  84.     q.enQueue(5);
  86.     // 6th element can't be added to queue because queue is full
  87.     q.enQueue(6);
  89.     q.display();
  91.     // deQueue removes element entered first i.e. 1
  92.     q.deQueue();
  94.     // Now we have just 4 elements
  95.     q.display();
  97.   }
  98. }
  1. // Queue implementation in C
  3. #include <stdio.h>
  4. #define SIZE 5
  6. void enQueue(int);
  7. void deQueue();
  8. void display();
  10. int items[SIZE], front = -1, rear = -1;
  12. int main() {
  13.   //deQueue is not possible on empty queue
  14.   deQueue();
  16.   //enQueue 5 elements
  17.   enQueue(1);
  18.   enQueue(2);
  19.   enQueue(3);
  20.   enQueue(4);
  21.   enQueue(5);
  23.   //6th element can't be added to queue because queue is full
  24.   enQueue(6);
  26.   display();
  28.   //deQueue removes element entered first i.e. 1
  29.   deQueue();
  31.   //Now we have just 4 elements
  32.   display();
  34.   return 0;
  35. }
  37. void enQueue(int value) {
  38.   if (rear == SIZE - 1)
  39.     printf("\nQueue is Full!!");
  40.   else {
  41.     if (front == -1)
  42.       front = 0;
  43.     rear++;
  44.     items[rear] = value;
  45.     printf("\nInserted -> %d", value);
  46.   }
  47. }
  49. void deQueue() {
  50.   if (front == -1)
  51.     printf("\nQueue is Empty!!");
  52.   else {
  53.     printf("\nDeleted : %d", items[front]);
  54.     front++;
  55.     if (front > rear)
  56.       front = rear = -1;
  57.   }
  58. }
  60. // Function to print the queue
  61. void display() {
  62.   if (rear == -1)
  63.     printf("\nQueue is Empty!!!");
  64.   else {
  65.     int i;
  66.     printf("\nQueue elements are:\n");
  67.     for (i = front; i <= rear; i++)
  68.       printf("%d  ", items[i]);
  69.   }
  70.   printf("\n");
  71. }
  1. // Queue implementation in C++
  3. #include <iostream>
  4. #define SIZE 5
  6. using namespace std;
  8. class Queue {
  9.    private:
  10.   int items[SIZE], front, rear;
  12.    public:
  13.   Queue() {
  14.     front = -1;
  15.     rear = -1;
  16.   }
  18.   bool isFull() {
  19.     if (front == 0 && rear == SIZE - 1) {
  20.       return true;
  21.     }
  22.     return false;
  23.   }
  25.   bool isEmpty() {
  26.     if (front == -1)
  27.       return true;
  28.     else
  29.       return false;
  30.   }
  32.   void enQueue(int element) {
  33.     if (isFull()) {
  34.       cout << "Queue is full";
  35.     } else {
  36.       if (front == -1) front = 0;
  37.       rear++;
  38.       items[rear] = element;
  39.       cout << endl
  40.          << "Inserted " << element << endl;
  41.     }
  42.   }
  44.   int deQueue() {
  45.     int element;
  46.     if (isEmpty()) {
  47.       cout << "Queue is empty" << endl;
  48.       return (-1);
  49.     } else {
  50.       element = items[front];
  51.       if (front >= rear) {
  52.         front = -1;
  53.         rear = -1;
  54.       } /* Q has only one element, so we reset the queue after deleting it. */
  55.       else {
  56.         front++;
  57.       }
  58.       cout << endl
  59.          << "Deleted -> " << element << endl;
  60.       return (element);
  61.     }
  62.   }
  64.   void display() {
  65.     /* Function to display elements of Queue */
  66.     int i;
  67.     if (isEmpty()) {
  68.       cout << endl
  69.          << "Empty Queue" << endl;
  70.     } else {
  71.       cout << endl
  72.          << "Front index-> " << front;
  73.       cout << endl
  74.          << "Items -> ";
  75.       for (i = front; i <= rear; i++)
  76.         cout << items[i] << "  ";
  77.       cout << endl
  78.          << "Rear index-> " << rear << endl;
  79.     }
  80.   }
  81. };
  83. int main() {
  84.   Queue q;
  86.   //deQueue is not possible on empty queue
  87.   q.deQueue();
  89.   //enQueue 5 elements
  90.   q.enQueue(1);
  91.   q.enQueue(2);
  92.   q.enQueue(3);
  93.   q.enQueue(4);
  94.   q.enQueue(5);
  96.   //6th element can't be added to queue because queue is full
  97.   q.enQueue(6);
  99.   q.display();
  101.   //deQueue removes element entered first i.e. 1
  102.   q.deQueue();
  104.   //Now we have just 4 elements
  105.   q.display();
  107.   return 0;
  108. }

此实现的局限性

如您在下图中所看到的，经过一些入队和出队后，队列的大小已减小。

队列 - 图3

队列限制

只有当所有元素都已出队后，才能在重置队列后使用索引 0 和 1。

在REAR到达最后一个索引之后，如果我们可以在空白空间（0 和 1）中存储额外的元素，则可以利用这些空白空间。 这通过称为循环队列的修改队列来实现。

队列复杂度

使用数组的队列中入队和出队操作的复杂度为O(1)。

队列应用

  • CPU 调度，磁盘调度
  • 在两个进程之间异步传输数据时，使用队列进行同步。 例如：IO 缓冲区，管道，文件 IO 等
  • 实时系统中的中断处理。
  • 呼叫中心电话系统使用队列来保持人们按顺序呼叫他们