队列在编程中是一个很有用的数据结构。很像剧院大堂外的购票队伍，第一个进入排队的人也是第一个买到票的人。

队列遵循“先入先出(FIFO)”原则 - 第一个被放入的会第一个取出。

上面的图片中，1在2的前面被塞到队列里，1也是首先从队列里拿出来的。遵循"FIFO"原则。

我们可以在C、C++、Java、Python或者C#中实现队列，规范差不多都一样。

队列的基础操作

队列是一种允许进行以下操作的对象（一种抽象数据结构 ——ADT）：

• 入队（Enqueue）：将一个元素添加到队列的末尾。
• 出队（Dequeue）：从队列的前端移除一个元素。
• 判断是否为空（IsEmpty）：检查队列是否为空。
• 判断是否已满（IsFull）：检查队列是否已满。
• 查看队首元素（Peek）：获取队列前端元素的值，而不移除该元素。

队列的工作方式

队列的工作方式如下：

• 两个指针，分别是 “前指针（FRONT）” 和 “后指针（REAR）”。
• “前指针（FRONT）” 用于跟踪队列的第一个元素。
• “后指针（REAR）” 用于跟踪队列的最后一个元素。
• 初始化时，将 “前指针（FRONT）” 和 “后指针（REAR）” 的值都设置为 -1。

入队操作

• 检查队列是否已满
• 对第一个元素，设置FRONT的值为0
• REAR加1
• 将新元素添加到REAR所指向的位置

出队操作

• 检查队列是否为空
• 返回FRONT指向的值
• FRONT加1
• 如果是最后一个元素，FRONT和REAR的值重置为-1

队列在Python, Java, C和C++中的实现

我们通常在Java和C/++中使用数组实现队列。在Python中，使用列表实现

Python

# Queue implementation in Python

class Queue():

    def __init__(self, k):
        self.k = k
        self.queue = [None] * k
        self.head = self.tail = -1

    # Insert an element into the queue
    def enqueue(self, data):

        if (self.tail == self.k - 1):
            print("The queue is full\n")

        elif (self.head == -1):
            self.head = 0
            self.tail = 0
            self.queue[self.tail] = data
        else:
            self.tail = self.tail + 1
            self.queue[self.tail] = data

    # Delete an element from the queue
    def dequeue(self):
        if (self.head == -1):
            print("The queue is empty\n")

        elif (self.head == self.tail):
            temp = self.queue[self.head]
            self.head = -1
            self.tail = -1
            return temp
        else:
            temp = self.queue[self.head]
            self.head = self.head + 1
            return temp

    def printQueue(self):
        if(self.head == -1):
            print("No element in the queue")

        else:
            for i in range(self.head, self.tail + 1):
                print(self.queue[i], end=" ")
            print()


# Your Queue object will be instantiated and called as such:
obj = Queue(5)
obj.enqueue(1)
obj.enqueue(2)
obj.enqueue(3)
obj.enqueue(4)
obj.enqueue(5)
print("Initial queue")
obj.printQueue()

obj.dequeue()
print("After removing an element from the queue")
obj.printQueue()

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

  }
}

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 because the 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");
}

C++

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

  return 0;
}

队列的局限性

正如你在下面的图片中可以看到的，在进行了一些入队和出队操作后，队列的大小已经减小了。

并且只有当队列被重置时（即所有元素都已出队时），我们才能够在索引 0 和 1 的位置添加元素。

当后指针（REAR）到达最后一个索引位置后，如果我们能够在空出的位置（索引 0 和 1）存储额外的元素，我们就可以利用这些空位置。可以通过一种经过改进的队列，即循环队列来实现的。

复杂度分析

在使用数组实现的队列中，入队（enqueue）和出队（dequeue）操作的时间复杂度为O (1)。如果你在 Python 代码中使用pop(N)方法，那么其时间复杂度可能会是O (n)，这取决于要弹出的元素所在的位置。

队列的应用

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