1、数据结构 队列简介

队列数据结构是线性的。它遵循先进先出方法，即先进先出或后进后出。
在队列中，由于 FIFO 方法，插入顺序与删除元素的顺序相同。当存在单个资源并且多个用户想要使用该资源时，通常使用队列。例如，在线程和 CPU 调度算法中。

数据结构队列类似于现实生活中的队列。例如，排队等候购买电影票的人。

2、队列的表示形式

类似堆栈一样，队列也是一种抽象数据类型，但它遵循 FIFO 方法。在队列中，我们总是删除最近添加最少的元素。

队列在两端都是开放的，这与堆栈不同。因此，我们在队列中的两个不同端执行删除和插入操作。队列的两端分别是前端和后端。

Front 指向队列的索引，我们可以从中删除元素。Rear 指向队列的索引，我们从中插入元素。

可以按如下方式表示队列：

3、队列类型

队列数据结构有多种类型，先简单介绍一下线性队列：
线性队列

线性队列是一个简单的队列，其中一端发生插入，另一端发生删除。
在线性队列中，我们有时无法有效地利用内存。这是因为插入只能在后端进行。

线性队列的基本操作

队列执行的基本操作是：

enqueue（）：将元素插入队列。
dequeue（）：从队列中删除元素。
peek（）：打印/显示前面的元素而不删除它。
isfull（）：检查队列是否已满。
isempty（）：检查队列是否为空。

在给定的操作中，前两个操作是最重要的。其余三个用于在实施时提高前两个操作的效率。

enqueue（） 操作

void enQueue(int key)  
{
    if(Rear == SIZE-1){   
        print("Overflow");  
        return;
    }
    if(Front == -1){   
        Front = 0;  
        Rear = 0;   
        Queue[Rear] = key;
    }
    else{
        Rear = Rear + 1;    
        Queue[Rear] = key;
    }
}

如上述代码所示，不难看出其时间复杂度为O(1)。

因此，在排队操作中，我们需要记住以下几个关键点：

在执行 enqueue（） 操作时，我们检查了三种不同的情况。这些情况是：

• 当队列为空时
• 当队列已满时
• 其他情况

当队列已满时，后部将指向最后一个索引，即队列大小 – 1 个位置。在这种情况下，我们将返回溢出错误并退出程序。

当队列为空时，最初前部和后部都将指向无效索引，例如 -1。在这种情况下，当我们插入一个元素时，两者都将开始指向索引 0。

由于队列只有一个元素，因此在这种情况下，队列的前部和后部将是相同的。

如果队列既不空也不满，我们只需将后指针的值增加 1 并插入新元素即可。

dequeue（） 操作

在执行 dequeue（） 操作时，我们始终确保队列不是空的。如果队列已为空，则无需删除任何内容。在这种情况下，我们将返回下溢错误。如果队列不为空，我们将删除前节点并将前指针移动到下一个节点。

int deQueue()
{
    int temp;   
    if(Front == -1) 
    {
        printf("Underflow");
        break;
    }
    if(Front == Rear)   
    {
        temp = Queue[Front];
        Front = -1;
        Rear = -1;
        return temp;
    }
    else
    {
        temp = Queue[Front];
        Front = Front + 1;
        return temp;
    }
}

使用数组实现队列时，dequeue（） 操作的时间复杂度为 O（1）

在 dequeue（） 操作的情况下：

• 如果队列为空，则 Front 将指向无效索引。在这种情况下，我们将返回下溢错误并退出程序。
• 如果队列仅包含一个元素，则 Front 和 Rear 都将指向同一索引。在这种情况下，我们将删除该元素，并使前后指向任何无效索引。

isfull（） 操作

每当 rear 指向 SIZE（即队列的最大大小）时，isfull（） 操作就会返回 true。
isfull（） 操作是一个布尔运算，即它返回 true 或 false。

isfull（） 操作的代码如下所示：

bool isfull() {
   if(Rear == SIZE-1)
      return true;
   else
      return false;
}

isEmpty（） 操作

仅当队列为空时，它才会返回 true。就像 isfull（） 操作一样，它是一个布尔运算，因此它返回 true 或 false。

如果 Front 的值为 MIN 或指向无效索引，则队列为空。因此，此操作将返回 true。

bool isEmpty() {
   if(000Front < 0 || Front > Rear) 
      return true;
   else
      return false;
}

peek（） 操作

此操作返回队列前面的数据元素的值，而不删除它。

int peek() {
   return Queue[Front];
}

线性队列的应用

队列主要用于按特定性能顺序对项目进行排序，或者当单个资源有多个用户时。

队列数据结构的主要应用包括：

异步数据传输

可以利用队列来异步传输数据。异步传输是指两个进程之间的数据传输速率不同。例如，队列用于管道、文件输入/输出、用于异步数据传输的套接字。

单个资源的多个用户

每当需要让进程等待单个共享资源时，我们都会将它们维护在队列中。例如，打印机、CPU 等是共享资源。

用作缓冲剂

队列可用作缓冲区，主要在需要时存储数据。例如，在 MP3 播放器的情况下，队列用作缓冲区。CD播放器等

中断处理

每当进程中断时，它就会被送回并在队列中等待。因此，队列有助于中断处理。

维护播放列表

队列有助于维护任何类型的列表。我们可以在队列的帮助下维护歌曲或其他媒体的播放列表。