队列数据结构

本文介绍了什么是队列数据结构,并用 C、C++、Java 和 Python 实现了队列。

队列是编程中一种有用的数据结构。类似于电影院外的售票队列,第一个进入队列的人就是第一个拿到票的人。

队列遵循**先进先出 (FIFO)**规则 - 先进入的项目是先出的项目。

先进先出原则的队列数据结构
先进先出原则的队列数据结构

在上图中,由于 1 在 2 之前进入到队列中,因此它也是第一个从队列中离开的。它遵循先进先出规则。

在编程术语中,将项目放入队列称为 enqueue,从队列中移除项目称为 dequeue

我们可以使用任何编程语言(如 C、C++、Java、Python 或 C#)实现队列,但规范几乎相同。

队列的基本操作

队列是一个抽象数据结构,它允许以下操作:

  • Enqueue : 向队列末尾添加一个元素
  • Dequeue : 从队列前面移除一个元素
  • IsEmpty : 检查队列是否为空
  • IsFull : 检查队列是否已满
  • Peek:获取队列前端的值而不移除它

队列的工作原理

以数组为底层实现的队列操作的工作方式如下:

  • 建立两个指针 FRONTREAR
    • FRONT 跟踪队列的第一个元素
    • REAR 跟踪队列的最后一个元素
  • 初始化 FRONTREAR 的值为 -1

入队操作

  • 检查队列是否已满
  • 对于第一个元素,设置 FRONT0
  • REAR 的值增加 1,在 REAR 指向的位置添加新元素

出队操作

  • 检查队列是否为空
  • 返回 FRONT 指向的值
  • FRONT 的值增加 1
  • 对于最后一个元素,重置值 FRONTREAR-1

演示如何在入队和出队操作期间修改前后索引
演示如何在入队和出队操作期间修改前后索引

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

我们通常使用数组来实现 Java 和 C/C++ 中的队列。对于 Python,我们使用列表。

使用 Python 实现队列

此 Python 程序使用 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 实现队列

此 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("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 实现队列

此 C 程序使用 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++ 实现队列

此 C++ 程序使用 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 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;
}

队列的限制

如下图所示,经过一些入队和出队后,队列的大小已经减小。因为前面的空间不能被重复利用。

从完整队列中出队后,前面的空间不能使用
队列的限制

并且我们只能在队列重置时(当所有元素都已出队时),才能重新使用索引 01

REAR 到达最后一个索引后,如果我们可以在空间(01)中存储新入队的元素,我们就可以利用这些空间。这是由称为循环队列的数据结构实现的。

复杂性分析

使用数组的队列中入队和出队操作的复杂度为 O(1)。如果您在 python 代码中使用 pop(N),那么复杂性可能是 O(n),这取决于要弹出的项目的位置。

队列的应用

  • CPU 调度、磁盘调度
  • 当两个进程之间异步传输数据时,队列用于同步。例如:IO Buffers、管道、文件 IO 等
  • 处理实时系统中的中断。
  • 呼叫中心电话系统使用队列将呼叫他们的人按顺序排列。

相关的教程