队列数据结构

提示

队列的定义和原则：队列是一种先进先出（FIFO）的数据结构，类似于现实生活中的排队，先进入队列的元素将首先被处理。
基本操作：队列的基本操作包括入队（在队尾添加元素）、出队（从队首移除元素）、检查是否为空、检查是否已满，以及查看队首元素。
实现和应用：队列可以在多种编程语言中实现，常用于CPU调度、数据异步传输、处理中断以及呼叫中心等场景。

队列是编程中非常有用的数据结构。它类似于电影院外的购票队列，先进入队列的人将是第一个得到票的人。

队列遵循**先进先出（FIFO）**规则——首先进入的元素将是首先出来的元素。

队列的先进先出原则表示

在上图中，由于 1 比 2 先进入队列，所以它也是第一个从队列中移除的。它遵循FIFO规则。

在编程术语中，将元素放入队列称为入队（enqueue），从队列中移除元素称为出队（dequeue）。

我们可以在任何编程语言中实现队列，如 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/C++ 中实现队列。在 Python 的情况下，我们使用列表。

Python 代码

# Python 中的队列实现

class Queue:

    def __init__(self):
        self.queue = []

    # 添加元素
    def enqueue(self, item):
        self.queue.append(item)

    # 移除元素
    def dequeue(self):
        if len(self.queue) < 1:
            return None
        return self.queue.pop(0)

    # 显示队列
    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("移除一个元素后")
q.display()

Java 代码

// 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("队列已满");
    } 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语言队列实现

#include <stdio.h>
#define SIZE 5

void enQueue(int);
void deQueue();
void display();

int items[SIZE], front = -1, rear = -1;

int main() {
  // 在空队列上无法执行deQueue操作
  deQueue();

  // 入队5个元素
  enQueue(1);
  enQueue(2);
  enQueue(3);
  enQueue(4);
  enQueue(5);

  // 由于队列已满，无法添加第6个元素
  enQueue(6);

  display();

  // deQueue会移除最先入队的元素，即1
  deQueue();

  // 现在只有4个元素
  display();

  return 0;
}

void enQueue(int value) {
  if (rear == SIZE - 1)
    printf("\n队列已满!!");
  else {
    if (front == -1)
      front = 0;
    rear++;
    items[rear] = value;
    printf("\n插入 -> %d", value);
  }
}

void deQueue() {
  if (front == -1)
    printf("\n队列为空!!");
  else {
    printf("\n已删除 : %d", items[front]);
    front++;
    if (front > rear)
      front = rear = -1;
  }
}

// 打印队列的函数
void display() {
  if (rear == -1)
    printf("\n队列为空!!!");
  else {
    int i;
    printf("\n队列元素为:\n");
    for (i = front; i <= rear; i++)
      printf("%d  ", items[i]);
  }
  printf("\n");
}

// 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 << "队列已满";
    } else {
      if (front == -1) front = 0;
      rear++;
      items[rear] = element;
      cout << endl
         << "插入 " << element << endl;
    }
  }

  int deQueue() {
    int element;
    if (isEmpty()) {
      cout << "队列为空" << endl;
      return (-1);
    } else {
      element = items[front];
      if (front >= rear) {
        front = -1;
        rear = -1;
      } /* 队列只有一个元素，所以我们在删除后重置队列。 */
      else {
        front++;
      }
      cout << endl
         << "删除 -> " << element << endl;
      return (element);
    }
  }

  void display() {
    /* 用于显示队列元素的函数 */
    int i;
    if (isEmpty()) {
      cout << endl
         << "空队列" << endl;
    } else {
      cout << endl
         << "前索引-> " << front;
      cout << endl
         << "元素 -> ";
      for (i = front; i <= rear; i++)
        cout << items[i] << "  ";
      cout << endl
         << "后索引-> " << rear << endl;
    }
  }
};

int main() {
  Queue q;

  // 在空队列上无法执行deQueue操作
  q.deQueue();

  // 入队5个元素
  q.enQueue(1);
  q.enQueue(2);
  q.enQueue(3);
  q.enQueue(4);
  q.enQueue(5);

  // 由于队列已满，无法添加第6个元素
  q.enQueue(6);

  q.display();

  // deQueue会移除最先入队的元素，即1
  q.deQueue();

  // 现在只有4个元素
  q.display();

  return 0;
}

队列的局限性

如下图所示，在一些入队和出队操作后，队列的大小已经减小。

从满队列出队后，前面的空位无法再次使用

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

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

复杂性分析

使用数组实现的队列中，入队和出队操作的复杂性为O(1)。如果在Python代码中使用pop(N)，则复杂性可能为O(n)，取决于要弹出的项的位置。

队列的应用

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

队列数据结构

队列的基本操作​

队列的工作原理​

入队操作​

出队操作​

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

Python 代码​

Java 代码​

队列的局限性​

复杂性分析​

队列的应用​

推荐阅读​