数据结构(顺序队列)

队列

基本概念

队列是最常见的概念，日常生活经常需要排队，仔细观察队列会发现，队列是一种逻辑结构，是一 种特殊的线性表。特殊在：

• 只能在固定的两端操作线性表

只要满足上述条件，那么这种特殊的线性表就会呈现一种“先进先出”的逻辑，这种逻辑就被称为队列。

• 队头：可以删除节点的一端
• 队尾：可以插入节点的一端
• 入队：将节点插入到队尾之后
• 出队：将队头节点从队列中剔除

由于这种固定两端操作的简单约定，队列获得了“ 先进先出”的基本特性，如下图所示：

顺序存储的队列：循环队列

与其他的逻辑结构类似，队列可以采用顺序存储形成循环队列，也可以采用链式存储形成链式队 列。顺序存储的队列之所以被称为循环队列，是因为可以利用更新队头队尾的下标信息，来循环地 利用整个数组，出队入队时也不必移动当中的数据。循环队列示意图如下所示：

从上述动图中可以观察到，需要牺牲至少数组中的一个存储位置，来区分循环队列中的满队和空 队。满队和空队的约定如下：

• 当head（队头元素下标）与tail（队尾元素下标）相等时，队列为空
• 当tail循环加一与head相等时，队列为满

与其他数据结构一样，管理循环队列除了需要一块连续的内存之外，还需要记录队列的总容量、当 前队列的元素个数、当前队头、队尾元素位置，如果有多线程还需要配互斥锁和信号量等信息，为 了便于管理，通常将这些信息统一于在一个管理结构体之中：

 typedef   int   DATA;
typedef  struct
 {
 DATA      *pData; // 队列入口
int         size;  // 队列总容量
int        head;   // 队列队头元素下标
int        tail;    // 队列队尾元素下标
  
}SQueue;

• 循环队列的基本操作

分析

squeue.h

#ifndef __SQUEUE_H
#define __SQUEUE_H
 typedef   int   DATA;
 typedef  struct
 {
   DATA      *pData; // 队列入口
   int         size;   // 队列总容量
   int         head;   // 队列队头元素下标
   int         tail;   // 队列队尾元素下标
}SQueue;
 // 初始化队列
int SQ_init(SQueue *q, int num);
 // 判断队列是否已满
int SQ_isfull(SQueue *q);
 // 判断队列是否为空
int SQ_isempty(SQueue *q);
 // 入队
int SQ_push(SQueue *q,DATA data);
 // 出队
int SQ_pop(SQueue *q,DATA *data);
 // 回收队
int SQ_free(SQueue *q);
 #endif

这段代码定义了一个带有以下功能的队列数据结构SQueue：

数据类型DATA为int类型
结构体SQueue包含了队列的基本信息，包括指向队列数据的指针pData、队列总容量size、队头元素下标head和队尾元素下标tail
函数SQ_init用于初始化队列，传入参数为队列指针和队列容量，返回值为int类型
函数SQ_isfull用于判断队列是否已满，传入参数为队列指针，返回值为int类型
函数SQ_isempty用于判断队列是否为空，传入参数为队列指针，返回值为int类型
函数SQ_push用于将元素入队，传入参数为队列指针和要入队的元素，返回值为int类型
函数SQ_pop用于将元素出队，传入参数为队列指针和接收出队元素的指针，返回值为int类型
函数SQ_free用于回收队列内存，传入参数为队列指针，返回值为int类型
此外，代码使用了条件编译，防止头文件被重复包含。

squeue.c

 #include <stdlib.h>
 #include "squeue.h"
 // 初始化队列
int SQ_init(SQueue* q,int num)
 {
    q -> pData = (DATA*)calloc(sizeof(DATA),num);
    if(q -> pData == NULL)
       return -1;
    q -> size  = num ;
    q -> head  = q -> tail = 0;
    return 0;
 }
 // 判断队列是否已满
int SQ_isfull(SQueue *q)
 {
    return (q -> tail + 1) % q -> size  == q -> head;
 }
// 判断队列是否为空
int SQ_isempty(SQueue *q)
 {
    return q -> tail  == q -> head;
 }
 // 出队
int SQ_push(SQueue *st,DATA data)
 {
    if(SQ_isfull(st))
       return -1;
    st -> pData[st -> tail] = data;
    st -> tail =  (st -> tail+1) % st -> size;
    return 0;
 }
 // 入队
int SQ_pop(SQueue *st,DATA *data)
 {
    if(SQ_isempty(st))
       return -1;
    *data = st -> pData[st -> head];
    st -> head =  (st -> head+1) % st -> size;
    return 0;
 }
 // 回收队列
int SQ_free(SQueue *st)
 {
    if(st -> pData)
    {
         free(st->pData);
         st -> pData = NULL;
    }
    st -> head = st -> tail  = 0;  
}

这段代码实现了一个顺序队列（squeue），包括初始化队列、判断队列是否已满、判断队列是否为空、入队、出队和回收队列的操作。

SQ_init函数用于初始化队列，参数包括队列指针和队列的最大容量。函数中使用calloc函数动态分配了一块内存作为队列的数据存储空间，如果分配失败则返回-1，否则将队列的大小和队列头尾指针初始化为0，并返回0表示初始化成功。

SQ_isfull函数用于判断队列是否已满。当队列的尾指针加1取模队列大小等于队列的头指针时，表示队列已满，返回1；否则返回0。

SQ_isempty函数用于判断队列是否为空。当队列的头指针等于尾指针时，表示队列为空，返回1；否则返回0。

SQ_push函数用于入队操作，将给定的数据data插入队列中。首先判断队列是否已满，如果已满则返回-1表示入队失败；否则将data插入队列的尾部，并更新尾指针，然后返回0表示入队成功。

SQ_pop函数用于出队操作，将队列中的数据弹出并赋值给给定的data。首先判断队列是否为空，如果为空则返回-1表示出队失败；否则将队列头部的数据赋值给data，并更新头指针，然后返回0表示出队成功。

SQ_free函数用于回收队列，释放队列的数据存储空间。首先判断队列的数据存储空间是否已分配，如果已分配则使用free函数释放内存，并将指针置为NULL；然后将队列的头尾指针重置为0。

注意：

循环队列中，需要牺牲一个存储位置来区分空队和满队

练习 3 」

构建一个顺序存储的循环队列，当用户输入数字时，将数字入队，当用户输入字母时，将队头元素 出队。每次操作队列之后，将队列中的元素显示出来。

解析： 构建循环队列要注意空队和满队的区别，比如可以让head和tail相等的时候代表空队，当tail+1再对 队列容量求余后等于head时代表满队。当然，这些逻辑都是人为规定的，我们完全可以将上述空队 和满队的判断条件对调。 使用顺序存储来实现循环队列，可以这么设计队列的管理结构体：

typedef struct
 {
    int *data; // 顺序存储内存空间
    int size;  // 循环队列总容量
    int head;  // 循环队列的头元素所在位置
    int tail;  // 循环队列的尾元素所在位置
}circular_queue;

参考代码：

 #include <stdio.h>
 #include <unistd.h>
 #include <stdlib.h>
 #include <stdbool.h>
 typedef struct
 {
    int *data; // 顺序存储内存空间
    int size;  // 循环队列总容量
    int head;  // 循环队列的头元素所在位置
    int tail;  // 循环队列的尾元素所在位置
}circular_queue;
 circular_queue * init_queue(int size)
 {
    circular_queue *q = malloc(sizeof(circular_queue));
    if(q != NULL)
    {
        q->data = malloc(sizeof(int) * size);
        if(q->data == NULL)
        {
            free(q);
            return NULL;
        }
        q->size = size;
        q->head = q->tail = 0;
    }
    printf("初始化完毕\n");
    return q;
 }
 bool is_empty(circular_queue *q)
 {
    return q->head == q->tail;
 }
 bool is_full(circular_queue *q)
 {
     return (q->tail+1)%q->size == q->head;
 }
 bool out_queue(circular_queue *q, int *loc)
 {
    if(is_empty(q))
        return false;
    *loc = q->data[q->head];
    q->head = (q->head + 1) % q->size;
    return true;
 }
 bool en_queue(circular_queue *q, int data)
 {
    if(is_full(q))    
        return false;
    q->data[q->tail] = data;
    q->tail = (q->tail + 1) % q->size;
    return true;
 }
 void show(circular_queue *q)
 {
    if(is_empty(q))
        return;
    int i;
    for(i=q->head; i!=q->tail; i=(i+1)%q->size)
    {
        if(i==q->head)
            printf("【队头】");
        printf("%d", q->data[i]);
        if((i+1)%q->size == q->tail)
            printf("【队尾】");
        printf("\t");
    }
    printf("\n");
 }
 int main(void)
 {
    circular_queue *q = init_queue(10);
     int n, data;
    while(1)
    {
        // 如果输入数字，则入队
        if(scanf("%d", &n) == 1)
        {
            if(!en_queue(q, n))
            {
                printf("队列已满，入队失败.\n");
                continue;
            }
        }
        // 如果输入非数字，则出队并清空缓冲区
        else
        {
            while(getchar() != '\n');
            if(!out_queue(q, &data))
            {
                printf("队列已空，出队失败.\n");
                continue;
            }
            printf("【%d】已出队\n", data);
        }
        show(q);
    }
    return 0;
 }

这段代码是用C语言实现循环队列的操作，包括初始化队列、判断队列是否为空或满、入队和出队操作以及展示队列元素。 首先，定义了一个循环队列的结构体circular_queue，包含顺序存储内存空间data、循环队列总容量size、头元素所在位置head和尾元素所在位置tail。 接着，通过init_queue函数进行队列的初始化操作，包括动态分配内存空间和设置头尾位置。 is_empty函数和is_full函数分别判断队列是否为空和满，为空时头尾相等，满时尾的下一个位置为头。 out_queue函数实现出队操作，将头位置的元素赋值给指定变量，并将头位置后移一位。 en_queue函数实现入队操作，将元素存储在尾位置，并将尾位置后移一位。 最后，通过show函数展示队列中的元素。在循环中，如果输入是数字，则将其入队；如果是非数字，则将队列中的元素依次出队并打印。每次操作后，通过show函数展示队列当前的元素。 需要注意的是，代码中没有进行内存的释放操作，应该在程序结束时释放动态分配的内存空间。