数据结构详解：顺序队列的实现与应用

数据结构详解：顺序队列的实现与应用

引用

CSDN

1.

https://blog.csdn.net/Cym20231111/article/details/145787940

在讲解顺序队列之前，我们先来了解一下队列的基本概念。

队列的基本概念

队列，就像排队时的队列一样，是一种特殊的线性表。其特殊之处在于：只能在固定的两端进行操作。这种操作方式使得队列呈现出“先进先出”的逻辑特性。

在队列中，两端的操作被赋予了特定的名称：

1. 队头：可以删除节点的一端
2. 队尾：可以插入节点的一端
3. 入队：将节点插入到队尾之后，函数名通常为enQueue()
4. 出队：将队列的头节点从队列中剔除，函数名通常为outQueue()
5. 取队头：取得队头的元素但不出队，函数名通常为front()

顺序队列

队列可以采用顺序存储方式形成循环队列。循环队列通过更新队头和队尾的下标信息，可以循环利用整个队列空间，入队和出队操作时不需要移动队列中的数据。

循环队列图解：

为了区分循环队列中的满队（队列为满）和空队（队列为空），需要空出至少一个存储位置：

1. 当 front 与 rear 相等时，队列为空
2. 当 rear 循环+1 与 front 相等时，队列为满

管理循环队列除了需要一块连续的内存之外，还需要记录队列的总容量、当前队列的元素个数、当前队头、队尾元素位置，如果有多线程还需要配互斥锁和信号量等信息。

顺序循环队列的管理结构体设计

图解：

示例代码：

// 学生结构体
typedef struct student
{
    int id;                 // 学生的学号
    char name[128];         // 学生的姓名

}stu_t, *stu_p;

// 顺序循环队列管理结构体设计
typedef struct sequence_queue
{
    stu_p data_p;           // 顺序循环队列的内存的入口
    int capacity;           // 顺序循环队列的总容量
    int front;              // 顺序循环队列的队头的元素下标
    int rear;               // 顺序循环队列的队尾的元素下标

}sq_queue_t, *sq_queue_p;

初始化顺序循环队列

图解：

示例代码：

/**
  * @brief    初始化顺序循环队列
  * @note     None
  * @param    cap_size：队列的容量
  * @retval   成功：返回指向队列的内存的指针
  *           失败：返回NULL
  */ 
sq_queue_p SEQUENCE_QUEUE_Init( int cap_size ) 
{
    // 1、申请顺序队列的堆内存空间(申请堆区1)
    sq_queue_p p = malloc( sizeof( sq_queue_t ) );
    bzero( p, sizeof( sq_queue_t ) );

    // 2、给该内存空间(堆区1)进行赋值操作
    if ( p != NULL)
    {
        // 堆区1里面的堆区2的空间
        p->data_p = malloc( sizeof( stu_t ) * cap_size );
        if ( p->data_p == NULL )
        {
            free(p);
            return NULL;
        }
        // 堆区1的特征遍历
        p->capacity   = cap_size;
        p->front      = 0;
        p->rear       = 0;

    }

    else
      return NULL;

    // 3、成功返回0
    return p;

}

判断顺序循环队列是否为空

示例代码：

/**
  * @brief    判断顺序循环队列是否为空
  * @note     None
  * @param    p：指向队列的管理结构体的指针
  * @retval   如果队列为空：  返回true
  *               队列为非空：返回false
  */ 
bool SEQUENCE_QUEUE_IfEmpty( sq_queue_p p ) 
{
    return ( p->front == p->rear );

}

判断顺序循环队列是否为满

示例代码：

/**
  * @brief    判断顺序循环队列是否为满
  * @note     None
  * @param    p：指向队列的管理结构体的指针
  * @retval   如果队列为满：  返回true
  *               队列为非满：返回false
  */ 
bool SEQUENCE_QUEUE_IfFull( sq_queue_p p ) 
{
    return ( ( p->rear + 1 ) % ( p->capacity ) == p->front );
}

入队 --- 插入数据

示例代码：

/**
  * @brief    入队
  * @note     None
  * @param    p：    指向顺序循环队列的管理结构体的指针
  *           data： 要赋值的数据 
  * @retval   成功： 返回0
  *           失败： 返回非0
  */ 
int SEQUENCE_QUEUE_EnQueue( sq_queue_p p, stu_t data ) 
{
    // 1、判断队列是否是满的
    if ( SEQUENCE_QUEUE_IfFull(p) )
        return -1;
    
    // 2、在队列的队尾插入数据
    p->data_p[ p->rear ].id = data.id;
    strcpy( p->data_p[ p->rear ].name, data.name );

    // 3、队尾标志+1
    p->rear = ( p->rear+1 ) % ( p->capacity );        // 因为是循环队列，因此需要取余操作

    // 4、成功返回
    return 0;

}

出队 --- 删除数据

示例代码：

/**
  * @brief    出队
  * @note     None
  * @param    p：指向顺序循环队列的管理结构体的指针
  * @retval   成功：返回0
  *           失败：返回非0
  */ 
int SEQUENCE_QUEUE_OutQueue( sq_queue_p p ) 
{
    // 1、判断队列是否是空的
    if ( SEQUENCE_QUEUE_IfEmpty(p) )
        return -1;
    
    // 2、在队列的队头删除数据
    bzero( &p->data_p[ p->front ], sizeof( stu_t ) );        // 清空数据(这一步其实可以不用)
    p->front = ( p->front+1 ) % ( p->capacity );             // 因为是循环队列，因此需要取余操作

    // 3、成功返回
    return 0;

}

获取队头的数据 --- 查询数据

示例代码：

/**
  * @brief    获取队头的数据
  * @note     None
  * @param    p：指向顺序循环队列的管理结构体的指针
  * @retval   成功：返回指向队列的队头的数据的指针
  *           失败：NULL
  */ 
stu_p SEQUENCE_QUEUE_GetFrontData( sq_queue_p p ) 
{
    // 1、判断队列是否是空的
    if ( SEQUENCE_QUEUE_IfEmpty(p) )
        return NULL;
    
    // 2、将指针队头的数据的指针返回
    return &( p->data_p[ p->front ] );
}

遍历整个队列

示例代码：

/**
  * @brief    遍历整个队列
  * @note     None
  * @param    p：指向顺序循环队列的管理结构体的指针
  * @retval   成功：返回0
  *           失败：返回非0
  */ 
int SEQUENCE_QUEUE_ShowQueue( sq_queue_p p ) 
{
    // 1、判断队列是否是空的
    if ( SEQUENCE_QUEUE_IfEmpty(p) )
        return -1;
    
    // 2、遍历整个顺序队列
    printf("================顺序队列里的数据===============\n\n");
    for ( int i = p->front; i != p->rear; i++, i = i % ( p->capacity ) )        // 由于是循环队列，因此需要取余操作
    {
        printf("sq_queue[%d] = 学生的ID：%d, 学生的姓名：%s\n", i, p->data_p[i].id, p->data_p[i].name);
    }

    printf("==============================================\n\n");

    // 3、成功返回0
    return 0;

}

销毁队列

示例代码：

/**
  * @brief    销毁队列
  * @note     None
  * @param    p：指向顺序循环队列的管理结构体的指针
  * @retval   None

  */ 
int SEQUENCE_QUEUE_UnInit( sq_queue_p p ) 
{
    free( p->data_p );
    free(p);

}

以上内容是关于顺序队列的详细讲解，包括其基本概念、实现方式以及相关操作的代码示例。通过这些内容，读者可以全面了解顺序队列的原理和应用。