当前位置：首页 > article >正文

数据结构：队列及其应用

article 2024/11/17 3:50:26

队列（Queue）是一种特殊的线性表，它的主要特点是先进先出（First In First Out，FIFO）。队列只允许在一端（队尾）进行插入操作，而在另一端（队头）进行删除操作。以下是对队列的详细介绍：

一、基本概念

队列的定义：队列是一种只允许在表的一端（队尾）进行插入操作，在另一端（队头）进行删除操作的线性表。
队头（Front）：队列中允许删除的一端，又称为队首。
队尾（Rear）：队列中允许插入的一端。
空队列：不包含任何元素的队列。

二、队列的主要操作

队列的主要操作包括入队（Enqueue）、出队（Dequeue）、查看队头元素（Peek/Front）和判断队列是否为空（IsEmpty）等。

入队（Enqueue）：在队列的队尾插入一个新元素。
出队（Dequeue）：从队列的队头删除一个元素，并返回该元素的值。
查看队头元素（Peek/Front）：返回队列队头元素的值，但不删除该元素。
判断队列是否为空（IsEmpty）：如果队列中没有任何元素，则返回true；否则返回false。

三、队列的分类（存储结构）

队列根据实现方式的不同，可以分为多种类型，如顺序队列、循环队列、链式队列等。

顺序队列：
使用数组实现的队列，队头和队尾指针分别指向队列的首尾元素。顺序队列在插入和删除操作时可能会出现“假溢出”现象，即队列未满但因指针限制无法继续插入元素的情况。

初始化：

//initialize
#define MaxSize 50
typedef struct
{
    int rear,front;//rear指向队尾元素的下一个值，front指向队头元素
    Elemtype data[MaxSize];
}SqQueue;

循环队列：
为了解决顺序队列的“假溢出”问题，引入了循环队列。在循环队列中，当队尾指针到达数组末尾时，会自动回到数组的开始位置，形成一个环状结构。循环队列需要牺牲一个存储单元来区分队列空和队列满的状态。

初始：front=rear=0；

队首指针进1：front=（front+1）%MaxSize

队尾指针进1：rear=（rear+1）%MaxSize

队长：（rear-front+Max Size）%MaxSize

队空判断条件：

循环队列为空的判断条件相对简单，即队头指针（front）和队尾指针（rear）相等。这是因为当队列为空时，没有元素被插入，所以队头和队尾都指向数组的起始位置（或某个约定的初始位置）。

队空判断条件：front == rear

队满判断条件：

循环队列为满的判断条件则较为复杂。由于队尾指针在达到数组末尾后会回到数组开头，因此当队尾指针再次指向队头指针时，队列可能已满，也可能为空。为了区分这两种情况，通常采用以下几种方法之一来判断队列是否满：

牺牲一个元素空间：
这是最常见的方法。在循环队列中，约定当(rear + 1) % MaxSize == front时，认为队列已满。这里，MaxSize是队列所使用数组的大小，%是取模运算符。这种方法通过牺牲数组中的一个元素空间来区分队列满和队列空的状态。当(rear + 1) % MaxSize == front时，虽然从逻辑上看队尾指针和队头指针相邻，但实际上队列中还有一个空位置没有被使用，因此认为队列已满。

队满判断条件（牺牲一个元素空间）：(rear + 1) % MaxSize == front

队空判断条件：front == rear

队长：(rear-front+MaxSize)%MaxSize

增设计数器或标志位：（size)
另一种方法是增设一个计数器（记录队列中元素的数量）或标志位（记录队列的当前状态，如是否进行过插入或删除操作）。然而，这种方法需要额外的存储空间，并且增加了操作的复杂性。队空：size=0; 队满：size=maxSize;
改变front和rear的定义域：
还有一种较为特殊的方法是通过改变front和rear的定义域来区分队列满和队列空的状态。例如，可以约定front的初始值为数组的最大索引加1（或某个大于数组最大索引的值），而rear的初始值为0。这样，当front等于rear时，队列为空；而当rear再次等于front时（在循环过程中），队列满。但这种方法在实际应用中较为少见，因为它改变了front和rear的常规用法。

综上所述，循环队列队空和队满的判断条件主要取决于所采用的具体实现方法。其中，“牺牲一个元素空间”的方法因其简单性和高效性而被广泛采用。

图解：

代码：

//initialize
void InitQueue(SqQueue &Q){
    Q.front=Q.rear=0;
}
//判断是否为空
bool isEempty(SqQueue Q){
    if(Q.rear===Q.front)
    return true;
    else
    return false;

}
//入队
bool EnQueue(SqQueue &Q,Elemtype x){
    if ((Q.rear+1)%MaxSize==Q.front)
    return false; 
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
        
}
//出队
bool DeQueue(SqQueue &Q,Elemtype &x){
    if(Q.front==Q.rear)
    return false;
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

链式队列：
使用链表实现的队列，每个节点包含数据域和指向下一个节点的指针。链式队列在插入和删除操作时不需要移动元素，具有较好的灵活性。

代码：

//
typedef struct{
    Elemtype  data;
    struct LinkNode *next;
}LinkNode;
typedef struct
{
    LinkNode *rear,*front;
}LinkQueue;

//initialize
void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));//建立头结点
    Q.front->next=NULL;
}

bool IsEmpty(LinkQueue Q){
    if(Q.front==Q.rear)
    return true;
    else
    return false;
}

void EnQueue(LinkQueue &Q,ElemType e){
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=e;
    s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
}

void DeQueue(LinkQueue &Q,ElemType &e){
    if(Q.front==Q.rear)
    return false;
    LinkNode *s=Q.front->next;
    e=s->data;
    Q.front->next=s->next;
    if(Q.rear==s)//队列中只有一个结点
    Q.front=Q.rear;//删除后变空
    free(s);
    return true;
}

双端队列：

1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的是4,1,3,2。

2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的是4,2,1,3。

3）既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的是4,2,3,1。

四、队列的应用场景

队列在实际应用中有着广泛的应用，如：

任务调度：在多任务系统中，可以使用队列来存储待执行的任务，系统按照队列中的顺序依次执行任务。
消息传递：在分布式系统中，队列可以用作消息传递的媒介，发送方将消息发送到队列中，接收方从队列中取出消息并进行处理。
缓存淘汰：在缓存系统中，可以使用队列的先进先出特性来淘汰最早进入缓存的数据项。
并发控制：在多线程或多进程环境中，队列可以用于控制对共享资源的访问顺序，防止数据竞争和死锁等问题。

队列在计算机系统中的应用

队列在计算机系统中的应用非常广泛，以下仅从两个方面来阐述：第一个方面是解决主机与外部设备之间速度不匹配的问题，第二个方面是解决由多用户引起的资源竞争问题。

缓冲区的逻辑结构（2009)：

对于第一个方面，仅以主机和打印机之间速度不匹配的问题为例做简要说明。主机输出数据给打印机打印，输出数据的速度比打印数据的速度要快得多，因为速度不匹配，若直接把输出的数据送给打印机打印，则显然是不行的。解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依次写入这个缓冲区，写满后就暂停输出，转去做其他的事情。打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求。主机接到请求后再向缓冲区写入打印数据。这样做既保证了打印数据的正确，又使主机提高了效率。由此可见，打印数据缓冲区中所存储的数据就是一个队列。

多队列出队／入队操作的应用（2016)：

对于第二个方面， CPU （即中央处理器，它包括运算器和控制器）资源的竞争就是一个典型的例子。在一个带有多终端的计算机系统上，有多个用户需要 CPU 各自运行自己的程序，它们分别通过各自的终端向操作系统提出占用 CPU 的请求。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把 CPU 分配给队首请求的用户使用。当相应的程序运行结束或用完规定的时间间隔后，令其出队，再把 CPU 分配给新的队首请求的用户使用。这样既能满足每个用户的请求，又使CPU能够正常运行。