数据结构-----队列

顺序队列（Queue）

一、队列核心概念

1. 基本特性

• 先进先出（FIFO）：最早入队的元素最先出队
• 操作限制：
  • 队尾（Rear）：唯一允许插入的位置
  • 队头（Front）：唯一允许删除的位置

2. 顺序队列结构

typedef int DATATYPE;

typedef struct queue {
    DATATYPE *ptr;  // 存储空间基地址
    int tlen;       // 队列总容量
    int head;       // 队头索引
    int tail;       // 队尾索引（下一个插入位置）
} SeqQueue;

二、核心操作实现

1. 创建队列

SeqQueue *CreateSeqQueue(int len)
{
    SeqQueue *sq = malloc(sizeof(SeqQueue));
    if (NULL == sq)
    {
        perror("CreateSeqQueue malloc error\n");
        return NULL;
    }
    sq->array = malloc(sizeof(DATATYPE) * len);
    if (NULL == sq->array)
    {
        perror("CreateSeqQueue malloc2 error\n");
        return NULL;
    }
    sq->head = 0;
    sq->tail = 0;
    sq->tlen = len;
    return sq;
}

2. 销毁队列

int DestroySeqQueue(SeqQueue *queue)
{
    if (NULL == queue)
    {
        fprintf(stderr, "DestroySeqQueue paramter error\n");
        return 1;
    }
    free(queue->array);
    free(queue);
    return 0;
}

三、关键操作实现

1. 入队操作

int EnterSeqQueue(SeqQueue *queue, DATATYPE *data)
{
    if (NULL == queue || NULL == data)
    {
        fprintf(stderr, "EnterSeqQueue paramter error\n");
        return 1;
    }
    if (IsFullSeqQueue(queue))
    {
        fprintf(stderr, "queue full\n");
        return 1;
    }
    memcpy(&queue->array[queue->tail], data, sizeof(DATATYPE));
    queue->tail = (queue->tail + 1) % queue->tlen;
    return 0;
}

2. 出队操作

int QuitSeqQueue(SeqQueue *queue)
{
    if (NULL == queue)
    {
        fprintf(stderr, "QuitSeqQueue paramter error\n");
        return 1;
    }
    if (IsEmptySeqQueue(queue))
    {
        fprintf(stderr, "queue empty\n");
        return 1;
    }
    queue->head = (queue->head + 1) % queue->tlen;
    return 0;
}

四、状态判断函数

1. 队列判空

int IsEmptySeqQueue(SeqQueue *queue)
{
    return queue->head == queue->tail;
}

2. 队列判满（循环队列实现）

int IsFullSeqQueue(SeqQueue *queue)
{
    return (queue->tail + 1) % queue->tlen == queue->head;
}

五、循环队列工作原理

1. 索引计算

• 队尾前进：tail = (tail + 1) % size
• 队头前进：head = (head + 1) % size

2. 空间利用

• 牺牲一个存储单元区分空/满状态
• 实际可用容量为tlen-1

六、性能与应用分析

1. 时间复杂度

2. 应用场景

• 数据缓冲：网络数据包接收缓冲
• 任务调度：打印机任务队列
• 系统通信：进程间消息传递
• 算法应用：广度优先搜索（BFS）

七、应用：

1.生产者-消费者模型

#include <stdio.h>
#include "./Seqque.h"
#include <pthread.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <semaphore.h>


sem_t sem_task;
void * th(void* arg)
{
    SeqQueue* sq  = (SeqQueue*)arg;
    DATATYPE data;
    while(1)
    {
        sem_wait(&sem_task);  //阻塞等待
        DATATYPE* tmp = GetHeadSeqQue(sq);
        memcpy(&data,tmp,sizeof(DATATYPE));
        if(0==strcmp(tmp->task_name,"over"))
        {
            break;
        }
        QuitSeqQueue(sq);

        while(data.task_time--)
        {
            printf("i'm %s\n",data.task_name);
            sleep(1);
        }
    }

    return NULL;
}

int	main(int argc, char **argv)
{
    DATATYPE task_data[]={
        {"washing",3},
        {"cooking",5},
        {"homeworking ",2},
        {"over",5},
    };
    sem_init(&sem_task,0,0);
    SeqQueue* sq = CreateSeqQueue(10);
    pthread_t tid;
    pthread_create(&tid,NULL,th,sq);
    for(int i = 0 ;i<4;i++)
    {
        printf("%d %s\n",i,task_data[i].task_name);
    }
    DATATYPE data;
    int run_flag = 1;
    while(run_flag)
    {
        bzero(&data,sizeof(data));
        int choose =-1;
        char buf[5]={0};
        fgets(buf,sizeof(buf),stdin);// 1\n
        choose = atoi(buf);
        switch (choose)
         {
            case 0:
            memcpy(&data,&task_data[0],sizeof(DATATYPE));
            EnterSeqQueue(sq, &data);
            sem_post(&sem_task);
            break;
             case 1:
            memcpy(&data,&task_data[1],sizeof(DATATYPE));
            EnterSeqQueue(sq, &data);
            sem_post(&sem_task);
            break;
             case 2:
            memcpy(&data,&task_data[2],sizeof(DATATYPE));
            EnterSeqQueue(sq, &data);
            sem_post(&sem_task);
            break;
             case 3:
            memcpy(&data,&task_data[3],sizeof(DATATYPE));
            EnterSeqQueue(sq, &data);
            sem_post(&sem_task);
            run_flag=0;
            break;
            default:
            break;

        }

    }

    pthread_join(tid,NULL);
    sem_destroy(&sem_task);
    DestroySeqQueue(sq);

    //system("pause");
    return 0;
}

2.把指定目录下所有.h文件遍历，把#define找出来。写入文件

#include <stdio.h>
#include "./Seqque.h"
#include <pthread.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <semaphore.h>
#include <dirent.h>
#define PATH "/home/linux/pute/linux2025/data_structure"

sem_t sem_task;
pthread_t main_th;

int do_check(char *filename, FILE *dstfp)
{
    if (strlen(filename) < 3 && 0 == strcmp(&filename[strlen(filename) - 2], ".h"))
    {
        return 1;
    }
    int num = 1;
    FILE *fp = fopen(filename, "r");
    if (NULL == fp)
    {
        perror("do_check fopen");
        return 1;
    }

    while (1)
    {
        char buf[512];
        if (NULL == fgets(buf, sizeof(buf), fp))
        {
            break;
        }
        if (strstr(buf, "#define"))
        {
            fprintf(dstfp, "%s %d %s", filename, num, buf);
        }
        num++;
    }
    fclose(fp);
}

// 目录入队,文件找目标
int FileEnterSeqQueue(SeqQueue *sq, const char *filepath, FILE *dstfp)
{
     DIR* dir = opendir(filepath); //home/linux
    if(NULL == dir)
    {
        perror("do_ls opendir error\n");
        return 1;
    }
    DATATYPE data;
    char newpath[512]={0};
    while(1)
    {
        bzero(&data,sizeof(data));
        bzero(newpath,sizeof(filepath));
        struct dirent *info = readdir(dir);
        if(NULL == info)
        {
            break;
        }
         sprintf(newpath,"%s/%s",filepath,info->d_name);
         printf("processing : %s \n",newpath);
        if(  DT_DIR ==info->d_type)
        {
            if(0==strcmp(info->d_name,".") || 0==strcmp(info->d_name,".."))
            {
                continue;
            }

           if(main_th==pthread_self()) // main
           {

            strcpy(data.dirpath,newpath); //home/linux/1/
            EnterSeqQueue(sq, &data);    
            sem_post(&sem_task);        
           }
           else  
           {

            FileEnterSeqQueue(sq,newpath,dstfp);
           }
           
            
        }
        else   //home/linux/1
        {
            if( DT_FIFO ==info->d_type || DT_LNK == info->d_type)
            {
                continue;
            }
            do_check(newpath,dstfp);
        }

    }
    
    closedir(dir);
}

typedef struct
{
    SeqQueue *sq;
    FILE *fp;
} TH_ARG;

void *thread_funk(void *arg)
{
    TH_ARG *tmp = (TH_ARG *)arg;

    while (1)
    {
        char path[512] = {0};
        sem_wait(&sem_task);
        DATATYPE *data = GetHeadSeqQue(tmp->sq);
        strcpy(path, data->dirpath);
        QuitSeqQueue(tmp->sq);
        if (0 == strcmp(path, "over"))
        {
            break;
        }
        FileEnterSeqQueue(tmp->sq, path, tmp->fp);
    }

    return NULL;
}

int main(int argc, char const *argv[])
{
    SeqQueue *sq = CreateSeqQueue(10000);
    main_th = pthread_self();
    sem_init(&sem_task, 0, 0);

    pthread_t tid[3];

    FILE *fp = fopen("log", "w");

    TH_ARG arg;
    arg.fp = fp;
    arg.sq = sq;

    for (int i = 0; i < 3; i++)
    {
        pthread_create(&tid[i], NULL, thread_funk, (void *)&arg);
    }

    FileEnterSeqQueue(sq, PATH, fp);

    for (int i = 0; i < 3; i++)
    {
        DATATYPE data = {0};
        strcpy(data.dirpath, "over");
        EnterSeqQueue(sq, &data);
        sem_post(&sem_task);
    }
    for (int i = 0; i < 3; i++)
    {
        pthread_join(tid[i], NULL);
    }

    DestroySeqQueue(sq);
    fclose(fp);

    return 0;
}

链式队列（Linked Queue）：

一、链式队列核心结构

1. 节点定义

// 数据元素类型
typedef struct person {
    char name[32];
    char sex;
    int age;
    int score;
} DATATYPE;

// 队列节点结构
typedef struct quenode {
    DATATYPE data;           // 数据域
    struct quenode *next;    // 指针域
} LinkQueNode;

// 队列管理结构
typedef struct {
    LinkQueNode *head;       // 队头指针
    LinkQueNode *tail;       // 队尾指针
    int clen;                // 当前元素个数
} LinkQue;

二、核心操作实现

1. 创建队列

LinkQue *CreateLinkQue()
{
    LinkQue *lq = malloc(sizeof(LinkQue));
    if (NULL == lq)
    {
        perror("CreateLinkQue malloc error\n");
        return NULL;
    }
    lq->head = NULL;
    lq->tail = NULL;
    lq->clen = 0;
    return lq;
}

2. 入队操作

int EnterLinkQue(LinkQue *lq, DATATYPE *data)
{
    LinkQueNode *newnode = malloc(sizeof(LinkQueNode));
    if (NULL == newnode)
    {
        perror("EnterLinkQue malloc error\n");
        return 1;
    }
    memcpy(&newnode->data, data, sizeof(DATATYPE));
    newnode->next = NULL;
    if (IsEmptyLinkQue(lq))
    {
        lq->head = newnode;
        lq->tail = newnode;
    }
    else
    {
        lq->tail->next = newnode;
        lq->tail = newnode;
    }
    lq->clen++;
    return 0;
}

3. 出队操作

int QuitLinkQue(LinkQue *lq)
{
    if (NULL == lq)
    {
        fprintf(stderr, "QuitLinkQue paramter error\n");
        return 1;
    }
    if (IsEmptyLinkQue(lq))
    {
        fprintf(stderr, "queue empty\n");
        return 1;
    }
    LinkQueNode *tmp = lq->head;
    lq->head = lq->head->next;
    free(tmp);

    if (lq->head == NULL)
    {
        lq->tail = NULL;
    }
    lq->clen--;
    return 0;
}

三、辅助操作实现

1. 获取队头元素

DATATYPE *GetHeadLinkQue(LinkQue *lq)
{
    if (NULL == lq)
    {
        fprintf(stderr, "GetHeadLinkQue paramter error\n");
        return NULL;
    }
    if (IsEmptyLinkQue(lq))
    {
        fprintf(stderr, "LinkQue empty\n");
        return NULL;
    }
    return &lq->head->data;
}

2. 队列判空

int IsEmptyLinkQue(LinkQue* lq) {
    return lq->clen == 0;
    // 或 return lq->head == NULL;
}

3. 获取队列长度

int GetSizeLinkQue(LinkQue* lq) {
    return lq->clen;
}

4. 销毁队列

int DestroyLinkQue(LinkQue *lq)
{
    if (NULL == lq)
    {
        fprintf(stderr, "DestroyLinkQue paramter error\n");
        return 1;
    }

    while (!IsEmptyLinkQue(lq))
    {
        QuitLinkQue(lq);
    }
    free(lq);
    return 0;
}

四、典型应用场景

1. 任务调度系统

// 任务处理器伪代码
void TaskHandler(LinkQue* task_queue) {
    while (!IsEmptyLinkQue(task_queue)) {
        DATATYPE *task = GetHeadLinkQue(task_queue);
        ExecuteTask(task);      // 执行任务
        QuitLinkQue(task_queue); // 出队
    }
}

2. 消息队列系统

// 多线程生产者-消费者模型
void* Producer(void* arg) {
    LinkQue* queue = (LinkQue*)arg;
    while(1) {
        DATATYPE msg = GenerateMessage();
        EnterLinkQue(queue, &msg);
    }
}

void* Consumer(void* arg) {
    LinkQue* queue = (LinkQue*)arg;
    while(1) {
        if(!IsEmptyLinkQue(queue)) {
            ProcessMessage(GetHeadLinkQue(queue));
            QuitLinkQue(queue);
        }
    }
}

五、队列变体扩展

1. 双端队列（Deque）

// 扩展结构
typedef struct deque {
    DATATYPE *ptr;
    int tlen;
    int front;
    int rear;
} SeqDeque;

// 支持操作：
// - 前端入队/出队
// - 后端入队/出队

2. 优先队列（Priority Queue）

• 元素按优先级出队
• 可用堆结构实现

六、顺序队列 VS 链式队列