线性结构 -- 队列

青旅半醒 2022-09-11 12:30 232阅读 0赞

# 一 队列的基本概念 #

## 1.1 队列的定义和特点 ##

和栈相反，**队列**（Queue）是一种**先进先出**（First In First Out，FIFO）的**线性表**。它也是一种操作受限的线性表，它只允许在表的一端进行插入，而在另一端删除元素。

在队列中，允许插入的一端称为**队尾**（Rear），允许删除的一端称为**队头**（Front）。

假设队列为 q = (![a\_\{1\},a\_\{2\},...,a\_\{n\}][a_1_a_2_..._a_n])，那么 a1 就是队头元素，an 则是队尾元素。队列的元素是按照 ![a\_\{1\},a\_\{2\},...,a\_\{n\}][a_1_a_2_..._a_n] 的顺序进入的，退出队列也只能按照这个次序依次退出，也就是说，只有在 ![a\_\{1\},a\_\{2\},...,a\_\{n-1\}][a_1_a_2_..._a_n-1] 都离开队列之后，an 才能退出队列。下图 3.2 所示为队列的示意图。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_19_color_FFFFFF_t_70_g_se_x_16][]

## 1.2 队列的逻辑结构和存储表示 ##

*  队列的逻辑结构和线性表相同，都是**线性结构**。
 *  队列的抽象数据类型有两种典型的存储表示：基于数组的**顺序存储表示**和基于链表的**链式存储表示**。

> (1) 基于数组的顺序存储表示实现的队列称为**顺序队列**，顺序队列可以采用**顺序表**作为其存储表示，因此，可以在顺序队列的声明中用顺序表定义它的存储空间。  
> (2)基于链表的链式存储表示实现的队列称为**链式队列**，链式队列可以采用**单链表**作为其存储表示，因此，可以在链式队列的声明中用单链表定义它的存储空间。

## 1.3 队列的运算规则 ##

*  队列中没有任何元素时称为空队列。
 *  队列可定义为只允许在表的最末端进行插入和最前端进行删除的线性表。允许插入的一端叫队尾(rear)，允许删除的一端叫队头(front)。
 *  向一个队列插入新元素称为**入队**，它是把新元素放到队列的最末端，使之成为新的队尾元素。
 *  从一个队列删除元素称为**出队**，它是把队头元素删除，使其下一个元素成为新的队头元素。
 *  设定队列Q = (![a\_\{1\},a\_\{2\},...,a\_\{n\}][a_1_a_2_..._a_n])，称最先加入队列的元素 ![a\_\{1\}][a_1] 为队头，最后加入队列的元素 ![a\_\{n\}][a_n] 为队尾。根据先进先出原则，队列中各元素的入队和出队顺序相同，都是按 ![a\_\{1\},a\_\{2\},...,a\_\{n\}][a_1_a_2_..._a_n] 的顺序入队和出队。
 *  队列的模型：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_14_color_FFFFFF_t_70_g_se_x_16][]

# 二 队列的顺序表示和实现 — 循环队列 #

队列也有两种存储表示，顺序表示和链式表示。

和顺序栈相类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，还需附设两个整型变量 front 和 rear 分别指示队列头元素和队列尾元素的位置（后面分别称为头指针和尾指针）。

## 2.0 顺序队列的数据结构定义 ##

//- - - - - 队列的顺序存储结构 - - - - -
    #define MAXQSIZE 100    //最大队列长度
    
    //顺序队列元素类型定义
    typedef int QElemType;
    
    //顺序队列的顺序存储结构
    typedef struct {
        QElemType* base;    //动态分配存储空间的基地址
        int front;          //头指针，若队列不空，指向队头元素
        int rear;           //尾指针，若队列不空，指向队列尾元素的下一个位置
    } SqQueue;

为了在 C 语言中描述方便起见，在此**约定**：初始化创建空队列时，令 front=rear=0，每当在队列的尾部插入一个新元素时，尾指针rear 自增 1；每当在队列的头部删除一个元素时，头指针front 自减 1。因此，在非空队列中，头指针front 始终指向队列头元素，而尾指针rear 始终指向队列尾元素的下一个位置，如图 3.12 所示。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_20_color_FFFFFF_t_70_g_se_x_16][]

假设当前队列分配的最大空间为 6，则当队列处于 图3.12(d) 所示的状态时，不可再继续插入新的队尾元素，否则会出现**溢出现象**，即因为数组越界而导致程序的非法操作错误。事实上，此时队列的实际可用空间并未占满，所以这种现象称为 “**假溢出**”。这是由 “队尾入队，队头出队” 这种受限操作造成的。

怎样解决这种 “假溢出” 问题呢？一个较为巧妙的办法是将顺序队列变成一个环状的空间，如图 3.13 所示，称之为**循环队列**。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_16_color_FFFFFF_t_70_g_se_x_16][]

头、尾指针以及队列元素之间的关系不变，只是在循环队列中，头、尾指针 “依环状增 1” 的操作可用 “模” 运算来实现。通过取模，头指针和尾指针就可以在顺序表空间内以头尾衔接的方式 “循环” 移动。如图 3.14 所示。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

> （1）在图 3.14(a) 中，队头元素是 J5，在元素 J6 入队之前，Q.rear 的值为 5（见图 3.12(d)的状态），当元素 J6 入队之后，通过 “模” 运算，Q.rear = (Q.rear + 1) % 6，得到 Q.rear 的值为 0（见图 3.14(a)的状态），而不会出现图 3.12(d) 的 “假溢出” 状态。
> 
> （2）在图 3.14(b) 中，J7、J8、J9、J10相继入队，此时队列空间均被占满，此时头、尾指针相同。
> 
> （3）在图 3.14(c) 中，若 J5 和 J6 相继从图 3.14(a) 所示的队列中出队，使队列此时呈现 “空” 的状态，头、尾指针的值也是相同的。

由此可见，对于循环队列不能以头、尾指针的指是否相同来判别队列空间是 “满” 还是 “空”。在这种情况下，如何判别队满还是队空呢？

**通常有以下两种处理方法**

（1）少用一个元素空间，即队列空间大小为 m 时，有 m-1 个元素就认为是队满。这样判断队空的条件不变，即当头、尾指针的值相同时，则认为队空；而当尾指针在循环意义上加 1 后是等于头指针，则认为队满。因此在循环队列中队空和队满的条件是：

Q.front = Q.rear                    //队空的条件
    
    (Q.rear+1) % MAXQSIZE == Q.front    //队满的条件

如图 3.14(d) 所示，当 J7、J8、J9 进入图 3.14(a) 所示的队列后，(Q.rear + 1) % MAXQSIZE 的值等于 Q.front，此时认为队满。

（2）另设一个标志位以区别队列是 “空” 还是 “满”。当标志位 tag 的值为0，并且头、尾指针的值相同时，则认为队空；当标志位 tag 的值为 1，并且头、尾指针的值相同时，则认为队满。因此，在循环队列中队空和队满的条件是：

//顺序队列的顺序存储结构
    typedef struct {
        QElemType* base;    //动态分配存储空间的基地址
        int front;          //头指针，若队列不空，指向队头元素
        int rear;           //尾指针，若队列不空，指向队列尾元素的下一个位置
        int tag;            //标志位（新增的成员）
    } SqQueue;
    
    Q.tag==0 && Q.rear==Q.front  //队空的条件
    Q.tag==1 && Q.rear==Q.front  //队满的条件

下面给出用第一种方法实现循环队列的基本操作，循环队列的类型定义与前面给出的顺序队列的类型定义是一样的。

## 2.1 循环队列的基本操作 ##

### 2.1.0 Status模块 ###

Status.h 模块：预定义了一些常量及类型，以增强C语言的描述功能。

//Status.h 模块：预定义了一些常量及类型，以增强C语言的描述功能。
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    //状态码
    #define TRUE        1   // 真/是
    #define FALSE       0   // 假/否
    #define OK          1   // 通过/成功
    #define ERROR       0   // 错误/失败
    
    //系统中已有此状态码定义，要防止冲突
    #ifndef OVERFLOW
    #define OVERFLOW    -2  //堆栈上溢
    #endif
    
    //系统中已有此状态码定义，要防止冲突
    #ifndef NULL
    #define NULL ((void*)0)
    #endif
    
    //状态码类型
    typedef int Status;
    
    //布尔类型
    typedef int Boolean;

### 2.1.1 循环队列的初始化操作 ###

【**算法描述**】C语言实现

/* 循环队列的初始化操作
     * 构造一个空队列Q
     * 初始化成功则返回OK，否则返回ERROR
    */
    Status InitQueue(SqQueue *Q)
    {
        if(!Q)
            return ERROR;
        
        Q->base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));
        if(!Q->base)
            exit(OVERFLOW);
        
        Q->front = Q->rear = 0;
        
        return OK;
    }

### 2.1.2 循环队列的销毁操作 ###

【**算法描述**】C语言实现

/* 循环队列的销毁操作
     * 释放循环队列Q所占的存储空间
    */
    Status DestroyQueue(SqQueue *Q)
    {
        if(!Q)
            return ERROR;
        
        if(Q->base != NULL)
            free(Q->base);
        Q.base = NULL;
        Q.front = Q.base = 0;
    
        return OK;
    }

### 2.1.3 循环队列的置空操作 ###

【**算法描述**】C语言实现

/* 循环队列的置空操作
     * 清理循环队列Q中存储的数据，但不释放顺序队列所占的存储空间
    */
    Status ClearQueue(SqQueue *Q)
    {
        if(!Q || !Q->base)
            return ERROR;
        
        Q.front = Q.rear = 0;
        
        return OK;
    }

### 2.1.4 循环队列的判空操作 ###

【**算法描述**】C语言实现

/* 循环队列的判空操作
     * 判断循环队列Q中是否含有有效数据
    */
    Status QueueIsEmpty(SqQueue *Q)
    {
        if(Q.front == Q.rear)
            return TRUE;
        else
            return FALSE;
    }

### 2.1.5 求循环队列的长度操作 ###

【**算法描述**】C语言实现

/* 求循环队列的长度操作
     * 返回循环队列Q的元素个数，即队列的长度
    */
    int QueueLength(SqQueue *Q)
    {
        if(!Q || !Q->base)
            return 0;
        else
            return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
    }

### 2.1.6 取队头元素操作 ###

【**算法描述**】C语言实现

/* 取队头元素操作
     * 获取循环队列Q的队头元素，将其存放到参数e中，不修改队头指针
     * 如果找到，返回OK；否则，返回ERROR
    */
    Status GetHead(SqQueue *Q, QElemType *e)
    {
        if(!Q || !Q->base || Q->front==Q->rear)
            return ERROR;
        
        *e = Q->base[Q->front];
        
        return OK;
    }

### 2.1.7 入队操作 ###

【**算法描述**】C语言实现

/* 入队操作
     * 在循环队列Q的尾部插入元素e为新的队尾元素
    */
    Status EnQueue(SqQueue *Q, QElemType e)
    {
        if(!Q || !Q->base)
            return ERROR;
        
        if((Q->rear + 1) % MAXQSIZE == Q->front)  //队满
            return ERROR;
        
        Q->base[Q->rear] = e;                     //新元素插入队尾
        
        Q->rear = (Q->rear + 1) % MAXQSIZE;       //尾指针加1
        
        return OK;
    }

### 2.1.8 出队操作 ###

【**算法描述**】C语言实现

/* 出队操作
     * 删除循环队列Q的队头元素，并用参数e接收其值
    */
    Status DeQueue(SqQueue *Q, QElemType *e)
    {
        if(!Q || !Q->base)
            return ERROR;
    
        if(Q->front == Q->rear)                   //队空
            return ERROR;
    
        *e = Q->base[Q->front];                   //出队
        
        Q->front = (Q->front + 1) % MAXQSIZE;     //头指针加1
        
        return OK;
    }

### 2.1.9 循环队列的遍历操作 ###

【**算法描述**】C语言实现

/* 循环队列的遍历操作
     * 访问循环队列Q的所有元素，并输出其值
    */
    Status QueueTraverse(SqQueue *Q)
    {
        if(!Q || !Q->base)
            return ERROR;
    
        int i = Q->front;
        while(i != Q->rear)
        {
            printf("%d, ", Q->base[i]);
            i = (i + 1) % MAXQSIZE;              //指向下一个元素
        }
        printf("\n");
        
        return OK;
    }

# 三 队列的链式表示和实现 — 链队列 #

链队是指采用链式存储结构实现的队列。通常链队列用单链表来表示，如图 3.15 所示。一个链队列显然需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。这里和线性表的单链表一样，为了方便操作，给链队列添加一个头结点，并令**头指针始终指向头结点**。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_10_color_FFFFFF_t_70_g_se_x_16][]

## 3.0 链队列的数据结构定义 ##

//循环队列元素类型定义
    typedef int QElemType;
    
    //---------- 队列的链式存储结构 ----------/
    //链队列结点类型定义
    typedef struct QNode
    {
        QElemType      data;
        struct QNode  *next;
    }QNode, *QueuePtr;
    
    //队列指针类型定义
    typedef struct
    {
        QueuePtr front;          //队头指针
        QueuePtr rear;           //队尾指针
    }LinkQueue;

## 3.1 链队列的基本操作 ##

### 3.1.0 Status模块 ###

Status.h 模块：预定义了一些常量及类型，以增强C语言的描述功能。

### 3.1.1 链队列的初始化操作 ###

【**算法描述**】C语言实现

/* 链队列的初始化操作
     * 构造一个空队列Q
     * 初始化成功则返回OK，否则返回ERROR
     * 【注意】这里的空队列是带有头结点的
    */
    Status InitQuene_L(LinkQueue *Q)
    {
        if(!Q)
            return ERROR;
        
        Q->rear = Q->front =(QNode*)malloc(sizeof(QNode));  //创建带头结点的队列
        if(!Q->front)
            exit(OVERFLOW);
    
        Q->front->next=NULL;
        
        return OK;
    }

### 3.1.2 链队列的销毁操作 ###

【**算法描述**】C语言实现

/* 链队列的销毁操作
     * 释放链队列Q所占的存储空间
    */
    Status DestroyQueue_L(LinkQueue *Q)
    {
        if(!Q)
            return ERROR;
    
        while(Q->front != NULL)
        {
            Q->rear = Q->front->next;
            free(Q->front);
            Q->front = Q->rear;
        }
        
        return OK;
    }

### 3.1.3 链队列的置空操作 ###

【**算法描述**】C语言实现

/* 链队列的置空操作
     * 释放链队列中所有非头结点的存储空间
    */
    Status ClearQueue_L(LinkQueue *Q)
    {
        if(!Q)
            return ERROR;
    
        Q->rear = Q->front->next;            //尾指针初始指向第一个元素
        while(Q->rear != NULL)
        {
            Q->front->next = Q->rear->next;  //头结点的指针域指向待删除结点的后继结点
            free(Q->rear);
            Q->rear = Q->front->next;        //尾指针指向新的队头元素
        }
        Q->rear = Q->front;                  //头、尾指针均指向头结点
        
        return OK;
    }

### 3.1.4 链队列的判空操作 ###

【**算法描述**】C语言实现

/* 链队列的判空操作
     * 判断队列中是否包含有效数据
     * 队列为空，返回TRUE；否则，返回FALSE
    */
    Status QueueIsEmpty_L(LinkQueue *Q)
    {
        if(Q->rear == Q->front)
            return TRUE;
        else
            return FALSE;
    }

### 3.1.5 求链队列的长度操作 ###

【**算法描述**】C语言实现

/* 求链队列的长度操作
     * 返回链队列中的元素个数，即队列的长度
    */
    int QueueLength_L(LinkQueue *Q)
    {
        int count = 0;
        QueuePtr p = Q->front;
        while(p != Q->rear)
        {
            count++;
            p = p->next;
        }
        
        return count;
    }

### 3.1.6 取链队列队头元素操作 ###

【**算法描述**】C语言实现

/* 取队头元素操作
     * 获取链队列Q的队头元素，将其存放到参数e中，不修改队头指针
     * 如果找到，返回OK；否则，返回ERROR
    */
    Status GetHead_L(LinkQueue *Q, QElemType *e)
    {
        if(!Q || !Q->front || Q->front==Q->rear)
            return ERROR;
    
        *e = Q->front->next->data;  //获取队头元素的值，并赋值给*e
        
        return OK;
    }

### 3.1.7 链队列的入队操作 ###

【**算法描述**】C语言实现

/* 入队操作
     * 在链队列Q的尾部插入元素e为新的队尾元素
    */
    Status EnQueue_L(LinkQueue *Q, QElemType e)
    {
        if(!Q || !Q->front)
            return ERROR;
    
        QueuePtr p = (QNode*)malloc(QNode);
        if(!p)
            exit(OVERFLOW);
    
        p->data = e;
        p->next = NULL;
        Q->rear->next = p;    //将当前队尾结点的指针域指向新结点p
        Q->rear = p;          //队尾指针rear指向新的队尾结点p
        
        return OK;
    }

### 3.1.8 链队列的出队操作 ###

【**算法描述**】C语言实现

/* 出队操作
     * 删除链队列Q的队头元素，并用参数e接收其值
    */
    Status DeQueue_L(LinkQueue *Q, QElemType *e)
    {
        if(!Q || !Q->front || Q->rear==Q->front)
            return ERROR;
    
        QueuePtr p = Q->front->next;  //p指向队列的队头元素
        *e = p->data;
        Q->front->next = p->next;     //头结点的指针域指向当前队头结点的后继结点
        if(Q->rear == p)              //最后一个元素被删除，队尾指针指向头结点
            Q->rear = Q->front;
        free(p);
    
        return OK;
    }

### 3.1.9 链队列的遍历操作 ###

【**算法描述**】C语言实现

/* 链队列的遍历操作
     * 访问链队列Q的所有元素，并输出其值
    */
    Status QueueTraverse_L(LinkQueue *Q)
    {
        if(!Q || !Q->front)
            return ERROR;
        
        QueuePtr p = Q->front->next;  //p初始指向队列的队头元素
        while(p != NULL)
        {
            printf("%d->", p->data);
            p = p->next;
        }
        printf("\n");
        
        return OK;
    }

# 参考 #

《数据结构(C语言版)》严蔚敏，吴伟民 (编著)

《数据结构(C语言版-第2版)》严蔚敏 , 李冬梅 , 吴伟民 (编著)

[第3章 栈和队列 - 循环队列][3_ _ -]

[第3章 栈和队列 - 队列的链式存储][3_ _ - 1]

[《数据结构(严蔚敏-C语言版)》- 队列的顺序存储][-C_-]

[《数据结构(严蔚敏-C语言版)》- 队列的链式存储][-C_- 1]

[a_1_a_2_..._a_n]: https://latex.codecogs.com/gif.latex?a_%7B1%7D%2Ca_%7B2%7D%2C...%2Ca_%7Bn%7D
[a_1_a_2_..._a_n-1]: https://latex.codecogs.com/gif.latex?a_%7B1%7D%2Ca_%7B2%7D%2C...%2Ca_%7Bn-1%7D
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/8c8b35faa1414e4dbd8d27446cd6202e.png
[a_1]: https://latex.codecogs.com/gif.latex?a_%7B1%7D
[a_n]: https://latex.codecogs.com/gif.latex?a_%7Bn%7D
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/56c27a91a8dc4bb998a541669f424f5b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/a5455e57c84e4a36a2a3fca757c44021.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/bcf8dde7e902483caeb9d2c11cee55a4.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/88e10e4686864bf6a400174c6de4f513.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_10_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/e822a4caeb074d0e871d76b0511167b9.png
[3_ _ -]: https://www.cnblogs.com/kangjianwei101/p/5225735.html
[3_ _ - 1]: https://www.cnblogs.com/kangjianwei101/p/5225734.html
[-C_-]: https://blog.csdn.net/Attention_0/article/details/81257073
[-C_- 1]: https://blog.csdn.net/Attention_0/article/details/81257596