数据结构-----队列

顺序队列（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;
}

---

链式队列（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 链式队列

特性	顺序队列	链式队列
存储方式	连续内存空间	离散节点链接
容量限制	固定大小	动态扩展
内存开销	无额外指针	每个节点含指针
缓存友好性	优秀	较差
实现复杂度	需要处理循环逻辑	指针操作简单