数据结构-----队列
顺序队列（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. 时间复杂度
| 操作 | 时间复杂度 |
|---|---|
| 入队 | O(1) |
| 出队 | O(1) |
| 判空/满 | O(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\nchoose = 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/linuxif(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;
}七、队列变体扩展
1. 双端队列（Deque）
// 扩展结构
typedef struct deque {DATATYPE *ptr;int tlen;int front;int rear;
} SeqDeque;// 支持操作：
// - 前端入队/出队
// - 后端入队/出队
2. 优先队列（Priority Queue）
- 元素按优先级出队
- 可用堆结构实现
八、顺序队列 VS 链式队列
| 特性 | 顺序队列 | 链式队列 |
|---|---|---|
| 存储方式 | 连续内存空间 | 离散节点链接 |
| 容量限制 | 固定大小 | 动态扩展 |
| 内存开销 | 无额外指针 | 每个节点含指针 |
| 缓存友好性 | 优秀 | 较差 |
| 实现复杂度 | 需要处理循环逻辑 | 指针操作简单 |