数据结构-----队列

embedded/2025/3/26 21:23:48/

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

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


http://www.ppmy.cn/embedded/174616.html

相关文章

SAP 附件增删改查与文件服务器交互应用

SAP 附件增删改查与文件服务器交互应用

【需求背景】 非SAP标准附件应用&#xff0c;自定义一套&#xff0c;跟公司内部文档服务器交互&#xff0c;支持各个应用场景的附件增删改查等。 每个附件在文件服务器上都有一个文件唯一ID作为关键字。 应用分两块&#xff1a;SAP GUI端&#xff0c;跟WDA Portal端应用 GU…
阅读更多...
华为终端销售模式转型变革项目总体汇报方案（183页PPT）（文末有下载方式）

华为终端销售模式转型变革项目总体汇报方案（183页PPT）（文末有下载方式）

资料解读&#xff1a;华为终端销售模式转型变革项目总体汇报方案 详细资料请看本解读文章的最后内容。 华为终端销售模式转型变革项目总体汇报方案&#xff0c;是一份详尽阐述华为终端销售模式转型的综合性文件。该方案旨在通过构建未来整体架构、识别关键变革点及痛点的解决…
阅读更多...
STM32 - 在机器人领域，LL库相比HAL优势明显

STM32 - 在机器人领域，LL库相比HAL优势明显

在机器人控制器、电机控制器等领域的开发&#xff0c;需要高实时性、精细化控制或者对代码执行效率、占用空间有较高要求。所以&#xff0c;大家常用的HAL库明显不符合要求。再加上&#xff0c;我们学习一门技术&#xff0c;一定要学会掌握底层的原理。MCU开发的底层就是寄存器…
阅读更多...
LabVIEW软件长时间运行导致蓝屏问题排查与优化

LabVIEW软件长时间运行导致蓝屏问题排查与优化

计算机在长时间运行LabVIEW或其他软件后出现蓝屏&#xff08;BSOD&#xff09;&#xff0c;通常由硬件资源耗尽、驱动冲突或软件内存泄漏引发。本文提供从日志分析到根本性优化的全流程解决方案&#xff0c;确保系统稳定运行。 一、蓝屏记录查询方法 1. 查看Windows事件日志 操…
阅读更多...
蓝桥杯备赛-DFS-全排列

蓝桥杯备赛-DFS-全排列

题目描述 按照字典序输出自然数 1 到 n 所有不重复的排列&#xff0c;即 n 的全排列&#xff0c;要求所产生的任一数字序列中不允许出现重复的数字。 输入格式 一个整数 n。 输出格式 由 1∼n 组成的所有不重复的数字序列&#xff0c;每行一个序列。 每个数字保留 5 个场…
阅读更多...
Spring常用注解汇总

Spring常用注解汇总

1. IOC容器与Bean管理 注解说明示例Component通用注解&#xff0c;标记类为Spring Bean Component public class MyService { ... } Controller标记Web控制器&#xff08;应用在MVC的控制层&#xff09; Controller public class UserController { ... } Service标记业务逻辑层…
阅读更多...
Java学习------初识JVM体系结构

Java学习------初识JVM体系结构

1. 介绍 JVM对应的是一套规范&#xff0c;然后不同公司根据这个规范有着不同的实现。例如: HotSpot: 这个是由Oracle公司开发的&#xff0c;也是目前最常用的虚拟机实现&#xff0c;是默认的Java虚拟机&#xff0c;包含在Oracle JDK和OpenJDK中JRockit: 同样也是由Oracle公司…
阅读更多...
SSL 和 TLS 认证

SSL 和 TLS 认证

SSL&#xff08;Secure Sockets Layer&#xff0c;安全套接层&#xff09;认证是一种用于加密网络通信和验证服务器身份的安全技术。它是TLS&#xff08;Transport Layer Security&#xff0c;传输层安全协议&#xff09;的前身&#xff0c;虽然现在大多数应用使用的是TLS&…
阅读更多...
最新文章

Copyright @ 2022~2023