数据结构-----队列

server/2025/3/22 7:10:14/

顺序队列（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/server/176984.html

相关文章

第四周日志-用网络请求理解bp（2）

第四周日志-用网络请求理解bp（2）

python网络请求库实现数据抓取、API调用还是后端服务的交互 以urllib3库为例 请求&#xff1a; import urllib3 http urllib3.PoolManager() # 创建连接池管理对象url1"" r1 http.request(GET,url1) #request print(r1.status) request&…
阅读更多...
鸿蒙NEXT项目实战-百得知识库05

鸿蒙NEXT项目实战-百得知识库05

代码仓地址&#xff0c;大家记得点个star IbestKnowTeach: 百得知识库基于鸿蒙NEXT稳定版实现的一款企业级开发项目案例。 本案例涉及到多个鸿蒙相关技术知识点&#xff1a; 1、布局 2、配置文件 3、组件的封装和使用 4、路由的使用 5、请求响应拦截器的封装 6、位置服务 7、三…
阅读更多...
neo4j-如何让外部设备访问wsl中的neo4j

neo4j-如何让外部设备访问wsl中的neo4j

WSL 运行在一个虚拟网络环境中&#xff0c;它的 IP 只能被宿主 Windows 访问&#xff0c;外部设备无法直接访问 WSL 的端口。你需要在 Windows 上转发端口&#xff0c;让外部设备可以访问 Windows 并映射到 WSL。 1. 获取 WSL 的 IP 地址 在 WSL 中运行以下命令获取其 IP 地址…
阅读更多...
Doris性能优化建议

Doris性能优化建议

1、jdbc连接中添加参数rewriteBatchedStatementstrue,将 JDBC 单条插入优化为批量操作 2、将单条插入攒成批后再插入,可先使用redis的zset存储&#xff0c;&#xff0c;每3秒后取出写入表中&#xff0c;写入失败再写回redis的zset 3、fe.conf中添加 按照机器可用内存的10/7赋…
阅读更多...
第二天 流程控制（if/for/while） - 列表/元组/字典操作

第二天 流程控制（if/for/while） - 列表/元组/字典操作

前言 在IT运维和系统管理领域&#xff0c;资源监控是至关重要的基础技能。本教程将带领Python初学者&#xff0c;通过编写一个实用的系统资源监控脚本&#xff0c;掌握Python基础语法中的流程控制、数据结构操作等核心知识。即使您完全没有编程经验&#xff0c;只要跟着本文一…
阅读更多...
Go 1.24.1 编译错误：`can‘t find export data (bufio: buffer full)` 的解决之旅

Go 1.24.1 编译错误：`can‘t find export data (bufio: buffer full)` 的解决之旅

一、前言 最近在用 Go 1.24.1 开发时&#xff0c;我遇到了一个让人头疼的编译错误。错误信息如下&#xff1a; # internal/runtime/math C:\Program Files\Go\src\internal\runtime\math\math.go:7:8: could not import internal/goarch (cant find export data (bufio: buff…
阅读更多...
⭐算法OJ⭐二叉树的后序遍历【树的遍历】（C++实现）Binary Tree Postorder Traversal

⭐算法OJ⭐二叉树的后序遍历【树的遍历】（C++实现）Binary Tree Postorder Traversal

⭐算法OJ⭐二叉树的中序遍历【树的遍历】&#xff08;C实现&#xff09;Binary Tree Inorder Traversal ⭐算法OJ⭐二叉树的前序遍历【树的遍历】&#xff08;C实现&#xff09;Binary Tree Preorder Traversal Given the root of a binary tree, return the postorder traver…
阅读更多...
【商城实战(39)】Spring Boot 携手微服务，商城架构焕新篇

【商城实战(39)】Spring Boot 携手微服务，商城架构焕新篇

【商城实战】专栏重磅来袭&#xff01;这是一份专为开发者与电商从业者打造的超详细指南。从项目基础搭建&#xff0c;运用 uniapp、Element Plus、SpringBoot 搭建商城框架&#xff0c;到用户、商品、订单等核心模块开发&#xff0c;再到性能优化、安全加固、多端适配&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023