数据结构笔记——队列

2024-02-22 10:56:22

一、队列的类型定义

队列（queue）是限定仅在表尾进行插入操作，仅在表头进行删除操作的线性表。表尾称为队尾（rear），表头称为队头（front），不含元素的表称为空队列。

队列的特点除了具有线性表的所有特点之外，还有自己特有的性质，它具有先进先出（first in first out，简称FIFO）的结构。

入队：插入元素的操作；出队：删除元素的操作。

设队列大小为MAXQSIZE，如果rear = MAXQSIZE时，发生溢出，而溢出又有两种情况：

真溢出：溢出情况下，队头指向基地址（说明队内不存在空余空间）；假溢出：溢出情况下，队头不指向基地址（说明队内存在空余空间没有被使用）。

队列有两种表示方式（存储方式）：一种是顺序结构存储，我们叫做顺序队列；另一种是链式结构存储，我们叫做链队列。这会在后面分别介绍。

队列的基本操作：

InitQueue(&Q)    // 构造一个空队列Q
DestroyQueue(&Q)    // 销毁队列Q
ClearQueue(&Q)    // 将Q清为空队列
IsEmpty(Q)    // 判断队列Q是否为空队列
QueueLength(Q)    // 返回队列Q的长度
GetHead(Q, &e)    // 用e返回Q的队头元素
EnQueue(&Q, e)    // 插入元素e为新的队尾元素
DeQueue(&Q, &e)    // 删除Q的队头元素并用e返回

二、顺序队列（循环队列）

顺序队列是用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，还需附设两个指针 front 和 rear 分别指示队列头元素和队列尾元素的位置。

顺序队列的图示结构：

由于队列有先进先出的特点，会导致顺序存储时出现如上问题，即元素出队后的空间产生了浪费的情况，使得会出现顺序队列空间未占满却无法再继续让新元素入队，而继续给它分配新的空间就太过于浪费了。

有一个巧妙的办法很好地解决了这个问题，就是将顺序队列假想成一个环状空间，称之为循环队列，这样就可以将已经出队的元素的空间再次利用起来。

循环队列判断队列的空或者满，有两种方法，一种是另设一个标志位来判断队列是否空或满；

另一种是舍弃一个元素的空间，通过判断队列头指针是否在尾指针的下一位置来判断队列是否已满。

一般来说，多采用第二种的存储方式，舍弃一个空间来规范队列的判断。

循环队列的图示结构：

循环队列的代码实现：

1.存储结构：

#define MAXQSIZE 100    // 最大队列长度
typedef struct{
    QElemType *base;    // 初始化的动态分配存储空间
    int front;    // 头指针，若队列不空，指向队列头元素
    int rear;    // 尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;

2.初始化操作：

Status InitQueue(SqQueue &Q){
    // 构造一个空队列Q
    Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
    if(!Q.base) exit(OVERFLOW);    // 存储分配失败
    Q.front = Q.rear = 0;    // 初始化头指针和尾指针均位于0处
    return OK;
} // InitQueue

时间复杂度：

3.求长度操作：

int QueueLength(SqQueue Q){
    // 返回队列Q中元素的个数，即队列的长度
    return ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE);
} // QueueLength

时间复杂度：

4.入队操作：

Status EnQueue(SqQueue &Q, QElemType e){
    // 插入元素e为Q的新的队尾元素
    if((Q.rear + 1) % MAXQSIZE == Q.front) return ERROR;    // 队列已满
    Q.base[Q.rear] = e;    // 插入元素e
    Q.rear = (Q.rear + 1) % MAXQSIZE;    // rear指向下一个空位置
    return OK;
} // EnQueue

时间复杂度：

5.出队操作：

Status DeQueue(SqQueue &Q, QElemmType &e){
    // 删除Q的队头元素，用e返回其值
    if(Q.front == Q.rear) return ERROR;    // 队列为空
    e = Q.base[Q.front];    // 将队头元素赋给e
    Q.front = (Q.front + 1) % MAXQSIZE;    // front指向下一个元素
    return OK;
} // DeQueue

时间复杂度：

6.取队头操作：

SElemType GetHead(SqQueue Q){
    // 返回队头元素，且不删除该元素
    if(Q.front != Q.rear)    // 队列不为空
        return Q.base[Q.front];    // 返回队头指针元素
} // GetHead

时间复杂度：

三、链队列

链队列即用链表表示的队列。一个链队列需要头指针和尾指针分别指向队头和队尾才能唯一确定。为了操作方便，给链队列添加一个头结点，并令头指针指向头结点，这样队空的判断条件为头尾指针均指向头结点。

链队列的图示结构：

链队列的代码实现：

1.存储结构：

typedef struct QNode{
    QElemType data;    // 数据元素
    struct QNode *next;    // 指针元素
}QNode, *QueuePtr;

typedef struct{
    QueuePtr front;    // 队头指针
    QueuePtr rear;    // 队尾指针
}LinkQueue;

2.初始化操作：

Status InitQueue(LinkQueue &Q){
    // 构造一个空队列Q
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front) exit(OVERFLOW);    // 分配失败
    Q.front->next = NULL;    // 队头指针初始化为空
    reutrn OK;
} // InitQueue

时间复杂度：

3.销毁操作：

Status DestroyQueue(LinkQueue &Q){
    // 销毁队列Q
    while(Q.front){    // 从头结点开始循环删除每一个结点
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
    return OK;
} // DestroyQueue

时间复杂度：

4.入队操作：

Status EnQueue(LinkQueue &Q, QElemType e){
    // 插入元素e为Q的新队尾元素
    p = (QueuePtr)malloc(sizeof(QNode));    // 创建一个新结点p
    if(!p) exit(OVERFLOW);    // 分配失败
    p->data = e;    // 将e赋给p结点的值
    p->next = NULL;    // p结点指针为空
    Q.rear->next = p;    // 队尾结点的指针指向p结点
    Q.rear = p;    // 队尾指针指向p
    return OK;
} // EnQueue

时间复杂度：

5.出队操作：

Status DeQueue(LinkQueue &Q, QElemType &e){
    // 删除Q的队头元素，并用e返回其值
    if(Q.front == Q.rear) return ERROR;    // 若队列为空
    p = Q.front->next;    // p指向队头结点
    e = p->data;    // 将值赋给e
    Q.front->next = p->next;    // 头指针指向新的队头结点
    if(Q.rear == p) Q.rear = Q.front;    // p指向队尾，则队列仅剩队尾元素，释放后队列为空
    free(p);    // 释放结点
    return OK;
} // DeQueue

时间复杂度：

6.取队头操作：

QElemType GetHead(LinkQueue Q, QElemType &e){
    // 用e返回链队列Q的队头元素，且不令其出队
    if(Q.front == Q.rear) return ERROR;    // 若队列为空
    e = Q.front->next->data;
    return OK;
} // GetHead

时间复杂度：

总结

基于队列先进先出的特点，常用于解决排队问题，先入队的先出队，后入队的后出队，从而实现有秩序的效果。

除此之外，队列的基本操作时间复杂度大部分都很小，但缺点是只能在队头取出元素，在队尾插入元素。

码农公寓

一、队列的类型定义

二、顺序队列（循环队列）

三、链队列

相关文章