数据结构(4)—队列
admin 于 2022年04月01日 发表在 C/C++开发笔记

队列(queue)也是一种重要的线性结构。与栈相同,实现一个队列同样需要顺序表或者链表为基础;与栈不同,队列是一种先进先出(first in first out,FIFO)的线性表。在队列中,允许插入数据的一端叫做队尾(rear),允许数据离开的一端叫作队头(front)。

在操作上有特殊的限制:数据只能从队尾进入队列,只能从队头取出队列。

队列的示意图,如下:

队列示意图队列示意图.png

1. 链队列

队列既可以用链表实现,也可以用顺序表实现。这里重点介绍用链表实现一个队列,这样的队列简称为链队列。

队列结构定义如下:

typedef int elemType_t; ///< 此处以int为例

// 结点参数
typedef struct node_t
{
    elemType_t data;
    struct node_t *next;
} node_t;           ///< 定义结点

// 队列参数
typedef struct
{
    node_t* front;   ///< 队头指针
    node_t* rear;    ///< 队尾指针
} queue_t;           ///< 定义队列

首先定义一个队列元素 node_t 结构体,因为要定义一个链队列,因此每个队列元素 node_t 不但要包括数据本身,还必须包括一个指针域,用来存放后继元素的指针(地址)。

定义一个 queue_t 类型,该类型也是一个结构体类型,包含两个域。front 域用来指向队列的头,即用来存放队头元素地址,它是一个node_t* 类型的变量; 同理,rear 域用来指向队列的尾。

1.1 创建一个队列

代码描述如下:

/**
 * @brief   创建一个空队列
 *
 * @param   *p_queue: 所要操作的队列
 * @return  0-初始化失败;1-初始化成功;
 *
 */
int init_queue(queue_t *p_queue)
{
    //创建一个头结点,队头队尾指针指向该结点
    p_queue->rear = (node_t*)malloc(sizeof(node_t));
    p_queue->front = p_queue->rear;

    //创建头结点失败
    if(!p_queue->front)
    {
        return 0;
    }

    // 头结点指针域置为NULL
    p_queue->front->next = NULL;

    return 1;
}

创建一个队列需要完成两个步骤:

(1)通过 malloc() 函数创建一个 node_t* 类型的结点,并将 p_queue->frontp_queue->rear 指针分别指向该头结点。

(2)将该头结点的指针域 next 置为 NULL

创建的空队列,其状态图如下:

创建好的空队列创建好的空队列.png

1.2 入队列操作

入队列操作就是将一个 node_t 类型的元素从队列的尾部进入队列。每当将一个队列元素插入队列,队列的尾指针都要进行修改(因此元素从队列的尾部进入队列),队头的指针不会发生改变。

入队列操作的代码描述如下:

/**
 * @brief   队列中添加一个结点
 *
 * @param   *p_queue: 所要操作的队列
 * @param   e: 所添加的结点内容
 * @return  0-失败;1-成功;
 *
 */
int put_queue(queue_t *p_queue, elemType_t e)
{
    node_t *node_p;

    //创建一个队列元素结点
    node_p = (node_t*)malloc(sizeof(node_t));
    node_p->data = e;
    node_p->next = NULL;

    if(!p_queue->front)
    {
        free(node_p);
        printf("队列不存在\n");
        return 0;
    }
    p_queue->rear->next = node_p;
    p_queue->rear = node_p;

    return 1;
}

首先,使用 malloc() 创建一个 node_t * 类型的元素结点。然后,将数据 e 赋值给该元素结点的数据域 node_p->data,并将该元素结点的指针域 next 置为NULL。

操作示意图,如下:

入队列操作过程示意图1.png入队列操作过程示意图1

最后,通过语句:

//原队尾next指针需要指向新结点
p_queue->rear->next = node_p;

//更新队尾结点
p_queue->rear = node_p;

将该元素结点从队列的尾部插入队列。

操作示意图,如下:

入队列操作过程示意图2.png入队列操作过程示意图2

1.3 出队列操作

出队列操作是将队列中的元素从队列的头部移出。每当从队列中移出数据时,队头指针不发生改变,但是头结点的 next 指针发生改变。队尾指针只有在原队列中只有一个元素,即队头等于队尾的情况下才会改变,否则不改变。

出队列代码描述,如下:

/**
 * @brief   从队列中取出结点数据
 *
 * @param   *p_queue: 所要操作的队列
 * @param   *e: 存放取出结点的数据内容
 * @return  0-失败;1-成功;
 *
 */
int get_queue(queue_t *p_queue, elemType_t *e)
{
    node_t *p_node;

    // 队列为空,直接返回
    if(p_queue->front == p_queue->rear)
    {
        printf("异常退出:所要删除的队列为空!!\n");
        return 0;
    }

    // 取一个结点
    p_node  = p_queue->front->next;
    
    // 取出队头的数据内容
    *e = p_node->data; 
    
    // 更新队列指针
    p_queue->front->next = p_node->next;    
     // 若队列头尾相同,修改队尾指针    
    if(p_queue->rear == p_node)
    {
        p_queue->rear = p_queue->front;
    }
    free(p_node);

    return 1;
}

首先,判断队列是否为空,如果是空队列则返回,程序终止执行,否则继续执行。之后,先将队头元素(p_queue->front->nex 指向的队列元素结点)的指针赋值给 p_node,这样 p_node  就指向了队列的第一个元素。之后,将 p->data 赋值给变量 *e

最后通过语句:

    // 更新队列头为,原队列头的下一个结点
    p_queue->front->next = p_node->next;
    
     // 若队列头尾相同,修改队尾指针
    if(p_queue->rear == p_node)
    {
        p_queue->rear = p_queue->front;
    }
    free(p_node);

将队列的队头元素删除。需要注意一点,如果原队列中队头就是队尾,则说明删除队头元素后该队列为空,因此队尾指针 q->rear 必须修改,应当赋值为 q->front ,此时队列变为空,队头队尾指针同时指向头结点。

原队列不止一个元素情况下,出队列操作示意图如下:

出队列元素不止一个出队列元素不止一个.png

(a)未删除队首元素前的队列状态

出队列元素不止一个2出队列元素不止一个2.png

(b)删除队首元素后情形

原队列只有一个元素情况下,出队列操作示意图如下:

出队列元素一个.png出队列元素一个.png

(a)未删除队首元素前的队列状态

出队列元素一个2.png出队列元素一个2.png

(b)删除队首元素后情形

1.4 销毁一个队列

由于链队列建立在内存的动态区,因此当一个队列不再使用时,应当及时销毁,以避免占用过多的内存空间。

代码如下:

/**
 * @brief   销毁一个链表
 *
 * @param   *p_queue: 所要操作的队列
 * @return  无;
 *
 */
void destroy_queue(queue_t* p_queue)
{
    while(p_queue->front)
    {
        // 队头指针指向下一个结点
        p_queue->rear  = p_queue->front->next;
        // 释放内存
        free(p_queue->front);
        p_queue->front = p_queue->rear;
    }
}

通过以上代码可以完整销毁一个队列,最终 q->rearq->front 都为空。

1.5 示例

#include <stdio.h>
#include <stdlib.h>

typedef int elemType_t; ///< 此处以int为例

// 结点参数
typedef struct node_t
{
    elemType_t data;
    struct node_t *next;
} node_t;           ///< 定义结点

// 队列参数
typedef struct
{
    node_t* front;   ///< 队头指针
    node_t* rear;    ///< 队尾指针
} queue_t;           ///< 定义队列

/**
 * @brief   创建一个空队列
 *
 * @param   *p_queue: 所要操作的队列
 * @return  0-初始化失败;1-初始化成功;
 *
 */
int init_queue(queue_t *p_queue)
{
    //创建一个头结点,队头队尾指针指向该结点
    p_queue->rear = (node_t*)malloc(sizeof(node_t));
    p_queue->front = p_queue->rear;

    //创建头结点失败
    if(!p_queue->front)
    {
        return 0;
    }

    // 头结点指针域置为NULL
    p_queue->front->next = NULL;

    return 1;
}

/**
 * @brief   队列中添加一个结点
 *
 * @param   *p_queue: 所要操作的队列
 * @param   e: 所添加的结点内容
 * @return  0-失败;1-成功;
 *
 */
int put_queue(queue_t *p_queue, elemType_t e)
{
    node_t *node_p;

    //创建一个队列元素结点
    node_p = (node_t*)malloc(sizeof(node_t));
    node_p->data = e;
    node_p->next = NULL;

    if(!p_queue->front)
    {
        free(node_p);
        printf("队列不存在\n");
        return 0;
    }
    p_queue->rear->next = node_p;
    p_queue->rear = node_p;

    return 1;
}

/**
 * @brief   从队列中取出结点数据
 *
 * @param   *p_queue: 所要操作的队列
 * @param   *e: 存放取出结点的数据内容
 * @return  0-失败;1-成功;
 *
 */
int get_queue(queue_t *p_queue, elemType_t *e)
{
    node_t *p_node;

    // 队列为空,直接返回
    if(p_queue->front == p_queue->rear)
    {
        printf("异常退出:所要删除的队列为空!!\n");
        return 0;
    }

    // 取一个结点
    p_node  = p_queue->front->next;

    // 取出队头的数据内容
    *e = p_node->data;

    // 更新队列指针
    p_queue->front->next = p_node->next;

    // 若队列头尾相同,修改队尾指针
    if(p_queue->rear == p_node)
    {
        p_queue->rear = p_queue->front;
    }
    free(p_node);

    return 1;
}

/**
 * @brief   销毁一个链表
 *
 * @param   *p_queue: 所要操作的队列
 * @return  无;
 *
 */
void destroy_queue(queue_t* p_queue)
{
    while(p_queue->front)
    {
        // 队头指针指向下一个结点
        p_queue->rear  = p_queue->front->next;
        // 释放内存
        free(p_queue->front);
        p_queue->front = p_queue->rear;
    }
}

int main()
{
    queue_t q_link;
    node_t  *p_node;
    int i = 0;

    // 1.创建链表
    printf("\n1.测试创建列表:\n");
    init_queue(&q_link);
    i = 0;
    if(q_link.front == q_link.rear)
    {
        printf("空队列创建成功 -> %d, %d\n", q_link.front->next, q_link.rear->next);
    }

    // 2.插入结点
    printf("\n2.测试队列添加结点:\n");
    put_queue(&q_link, 10);
    put_queue(&q_link, 20);
    put_queue(&q_link, 30);
    put_queue(&q_link, 40);
    put_queue(&q_link, 40);
    i = 0;
    p_node = q_link.front;
    while(q_link.rear != p_node)
    {
        p_node = p_node->next;
        printf("结点%d,对应数据%d\n", i, p_node->data);
        i++;
    }

    // 3.删除结点
    printf("\n3.测试删除队列结点:\n");
    for(i = 0; i < 2; i++)
    {
        elemType_t elem;
        get_queue(&q_link, &elem);
        printf("结点%d,取出数据%d\n", i, elem);
    }
    i = 0;
    p_node = q_link.front;

    printf("\n4.最终队列数据为:\n");
    while(q_link.rear != p_node)
    {
        p_node = p_node->next;
        printf("结点%d,对应数据%d\n", i, p_node->data);
        i++;
    }

    // 4.释放链表
    printf("\n5.测试释放结点:\n");
    destroy_queue(&q_link);
    if(q_link.rear == q_link.front)
        printf("释放队列成功\n");
    return 0;
}

2. 循环队列

所谓循环队列就是该队列与传统链队列不同,队列的空间是可以循环使用的。循环队列一般有固定的容量,与传统的队列相同,队列元素必须从队尾进入队列,必须从队头出队列。

如果在使用队列的过程中,不断有元素入队列,同时又不断有元素出队列,那么对于一般的链队列,只要队列不为空,其队头指针 front 和 队尾指针 rear 都不会发生改变,只是头结点的 next 指针和队尾的前一个结点的 next 指针会发生变化,而且链队列的长度也会随着入队列元素不断变化。

而对于循环队列,它的容量是固定的,并且他的队头指针和队尾指针都可以随着元素入出队列而发生改变,这样循环队列逻辑上就好像是一个环形的存储空间,主要队列中还有空单元未使用,就可以向队列中存放元素。

由于循环队列的这一特性,循环队列可作为缓冲池存储结果来存放数据,循环队列逻辑结构如下:

循环队列逻辑结构循环队列逻辑结构.png

如上图所示,图(a)为一个循环队列,该队列总容量为8B,实际长度为5B。为了方便操作,这里约定循环队列队列头指针 front 始终指向队头元素,队尾指针 rear 始终指向队尾元素的下一个空间。因此这里队头元素为 f,队尾元素为 b,该队列的实际可用空间为 7 B。

图(b)为将队列图(a)的队首元素 f 出队列,将字符 a 入队列后,该队列情形。从图(b)中可以看出,对于循环队列,入队列操作就是向 rear 指向的空间赋值,然后指针 rear 再指向队尾元素的下一个空间。出队列操作就是将队头指针 front 向上移动一个单元。整个循环队列逻辑上就是一个首尾相接的环形缓冲区。

2.1 循环队列的实现

循环队列的几种状态图,如下:

循环队列的几种状态图循环队列的几种状态图.png

图(a)表示初始化一个循环队列,在内存中开辟一个 7B 大小的连续存储单元。这就标志着该循环队列最多存放 6B 元素,因为 rear 指针始终指向队尾元素的下一个单元。最后的循环队列队头指针 front 和队尾指针 rear 都指向 0 号单元。

图(b)表示向队列中存放了两个元素a、b。字符 a、b入队列的过程是:先将字符a存放到队尾指针 rear 指向的空间,rear 指针加 1,这样字符 a 入队列;同样地过程,将字符 b 存放到队尾指针 rear 指向的空间,rear 指针再加 1,这样字符 b 入队列。队尾指针 rear 始终指向队尾元素的下一个单元。

图(c)表示图(b)所示的队列将队首元素 a 出队列后队列的状态。队首元素 a 出队列的过程:将 front 所指向的元素返回,再将指针 front 加 1。队头指针 front 始终指向队头元素。

图(d)表示在图(c)所示队列的基础上,将 c、d、e、f、g 这5个字符元素入队列后队列的状态。此时队尾指针 rear 重新指向 0 号单元,这是因为 rear 不断加1后超出了循环队列的地址范围,于是采取取模运算处理的结果。因此,无论是入队列的 rear 加 1 操作,还是出队列的 front 加 1 操作,实际上就是模加操作,即:(rear+1)% 7(front + 1)%7。正是因为这样,才能在线性的内存空间上模拟出逻辑上的循环的队列。

2.2 定义一个循环队列

#define MAX_QUEUE_SIZE  6

typedef int elemType_t; ///< 此处以int为例

// 队列参数
typedef struct
{
    elemType_t *base;   ///< 队列基地址
    int front;          ///< 队头指针
    int rear;           ///< 队尾指针
} cycle_queue_t;        ///< 定义队列

2.3 初始化一个循环队列

/**
 * @brief   初始化一个循环队列
 *
 * @param   *p_queue: 所要操作的队列指针
 * @return  0-初始化失败;1-初始化成功;
 *
 */
int init_cycle_queue(cycle_queue_t *p_queue)
{
    p_queue->base = (elemType_t *)malloc(MAX_QUEUE_SIZE*sizeof(elemType_t));

    // 内存分配失败
    if(!p_queue -> base)
    {
        return 0;
    }

    p_queue->front = p_queue->rear = 0;

    return 1;
}

2.4 入队列操作

/**
 * @brief   入队列
 *
 * @param   *p_queue: 所要操作的队列指针
 * @param   e: 所添加的数据内容
 * @return  0-失败;1-成功;
 *
 */
int en_cycle_queue(cycle_queue_t *p_queue, elemType_t e)
{
    if(((p_queue->rear + 1) % MAX_QUEUE_SIZE) == p_queue->front)
    {
        printf("异常:队列已满!\n");
        return 0;
    }

    p_queue->base[p_queue->rear] = e;
    p_queue->rear = (p_queue->rear + 1) % MAX_QUEUE_SIZE;

    return 1;
}

2.5 出队列操作

/**
 * @brief   出队列
 *
 * @param   *p_queue: 所要操作的队列指针
 * @param   *e: 取出的结点数据内容
 * @return  0-失败;1-成功;
 *
 */
int de_cycle_queue(cycle_queue_t *p_queue, elemType_t *e)
{
    // 队列为空
    if(p_queue->front == p_queue->rear)
    {
        printf("队列为空!\n");
        return 0;
    }

    // 取出队头元素
    *e = p_queue->base[p_queue->front];

    // 队头指针加1
    p_queue->front = (p_queue->front + 1) % MAX_QUEUE_SIZE;

    return 1;
}

2.6 示例

#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE  6

typedef int elemType_t; ///< 此处以int为例

// 队列参数
typedef struct
{
    elemType_t *base;   ///< 队列基地址
    int front;          ///< 队头指针
    int rear;           ///< 队尾指针
} cycle_queue_t;        ///< 定义队列

/**
 * @brief   初始化一个循环队列
 *
 * @param   *p_queue: 所要操作的队列指针
 * @return  0-初始化失败;1-初始化成功;
 *
 */
int init_cycle_queue(cycle_queue_t *p_queue)
{
    p_queue->base = (elemType_t *)malloc(MAX_QUEUE_SIZE*sizeof(elemType_t));

    // 内存分配失败
    if(!p_queue -> base)
    {
        return 0;
    }

    p_queue->front = p_queue->rear = 0;

    return 1;
}

/**
 * @brief   入队列
 *
 * @param   *p_queue: 所要操作的队列指针
 * @param   e: 所添加的数据内容
 * @return  0-失败;1-成功;
 *
 */
int en_cycle_queue(cycle_queue_t *p_queue, elemType_t e)
{
    if(((p_queue->rear + 1) % MAX_QUEUE_SIZE) == p_queue->front)
    {
        printf("异常:队列已满!\n");
        return 0;
    }

    p_queue->base[p_queue->rear] = e;
    p_queue->rear = (p_queue->rear + 1) % MAX_QUEUE_SIZE;

    return 1;
}

/**
 * @brief   出队列
 *
 * @param   *p_queue: 所要操作的队列指针
 * @param   *e: 取出的结点数据内容
 * @return  0-失败;1-成功;
 *
 */
int de_cycle_queue(cycle_queue_t *p_queue, elemType_t *e)
{
    // 队列为空
    if(p_queue->front == p_queue->rear)
    {
        printf("队列为空!\n");
        return 0;
    }

    // 取出队头元素
    *e = p_queue->base[p_queue->front];

    // 队头指针加1
    p_queue->front = (p_queue->front + 1) % MAX_QUEUE_SIZE;

    return 1;
}

/**
 * @brief   打印队列内容
 *
 * @param   *p_queue: 所要操作的队列
 * @return  0-失败;1-成功;
 *
 */
int dump_cycle_queue(cycle_queue_t *p_queue)
{
    int i, start_pos = 0;
    int valid_len = 0;

    if(p_queue->front == p_queue->rear)         // 队列为空
    {
        printf("队列为空!\n");
        return 0;
    }
    else if(p_queue->front > p_queue->rear)     // 队列已转圈
    {
        int pos = 0;
        valid_len = MAX_QUEUE_SIZE + p_queue->rear - p_queue->front;
        start_pos = p_queue->front;
        for(i = 0; i < valid_len; i++)
        {
            pos = (start_pos + i) % MAX_QUEUE_SIZE;
            printf("结点数据:%d\n", p_queue->base[pos]);
        }
    }
    else                                        // 循环未转圈
    {
        valid_len = p_queue->rear - p_queue->front;
        start_pos = p_queue->front;
        for(i = 0; i < valid_len; i++)
        {
            printf("结点数据:%d\n", p_queue->base[start_pos + i]);
        }
    }

    return 1;
}

int main()
{
    cycle_queue_t q_link;
    elemType_t    elem;
    int i = 0;

    // 1.创建链表
    printf("\n1.测试创建循环队列:\n");
    if(init_cycle_queue(&q_link))
    {
        printf("创建循环队列成功!\n");
    }

    // 2.插入结点
    printf("\n2.测试队列添加结点:\n");
    en_cycle_queue(&q_link, 10);
    en_cycle_queue(&q_link, 20);
    en_cycle_queue(&q_link, 30);
    en_cycle_queue(&q_link, 40);
    en_cycle_queue(&q_link, 50);
    dump_cycle_queue(&q_link);

    // 3.删除结点
    printf("\n3.测试删除队列结点:\n");
    de_cycle_queue(&q_link, &elem);
    printf("删除结点:%d\n", elem);
    de_cycle_queue(&q_link, &elem);
    printf("删除结点:%d\n", elem);
    printf("\n新的队列数据:\n");
    dump_cycle_queue(&q_link);

    // 4.再次插入结点
    printf("\n4.测试再次添加结点:\n");
    en_cycle_queue(&q_link, 60);
    en_cycle_queue(&q_link, 70);
    dump_cycle_queue(&q_link);
}

示例运行结果如下:

循环队列运行结果.png循环队列运行结果

参考来源:

1.《妙趣横生的算法(C语言实现)》                           杨峰  编著

注意:本站所有文章除特别说明外,均为原创,转载请务必以超链接方式并注明作者出处。 标签:数据结构,队列