从零开始的敲代码生活--数据结构篇（队列）

一、队列基础概念队列一种允许从一端插入数据另外一端删除数据的线性存储结构称为队列。 把数据插入的这端称为队列的队尾数据删除这端称为队列的队头。 插入操作称为入队删除操作称为出队。特点先进先出、后进后出(FIFO)应用数据缓存队列的 API创建队列入队遍历判空(循环队列还需判满)出队获取队头元素销毁队列分类链式队列链式存储结构实现利用链表结点动态分配内存不存在假溢出问题循环队列顺序结构(数组)实现为避免假溢出使顺序队列成为一种尾首相接的存储方式判空head tail判满(tail 1) % 容量 head牺牲一个存储单元区分空与满文件说明文件说明linkqueue.h头文件链式队列结构体定义 函数声明linkqueue.c源文件链式队列所有功能实现文件说明main.c链式队列测试 main 函数cyclequeue.h头文件循环队列结构体定义 函数声明cyclequeue.c源文件循环队列所有功能实现main.c循环队列测试 main 函数二、链式队列1. 头文件 linkqueue.h#ifndef _LINKQUEUE_H #define _LINKQUEUE_H #include stdio.h #include stdlib.h typedef int Data_t; /* 队列结点结构体:数据域 指针域 */ typedef struct node { Data_t data; // 数据域:保存的数据 struct node *pnext; // 指针域:下一个结点的地址 }Node_t; /* 队列对象结构体:队头指针 队尾指针 结点计数 */ typedef struct lqueue { Node_t *phead; // 队头指针 Node_t *ptail; // 队尾指针 int clen; // 队列当前结点个数 }LQue_t; extern LQue_t *create_link_queue(); extern int en_link_queue(LQue_t *pqlink,Data_t data); extern int show_link_queue(LQue_t *pqlink); extern int de_link_queue(LQue_t *pqlink,Data_t *data); extern int free_link_queue(LQue_t *pqlink); extern int get_link_queue_head(LQue_t *pqlink,Data_t *data); #endif2. 功能实现 linkqueue.ccreate_link_queue 创建队列功能分配队列管理结构体初始化队头指针 phead 置 NULL、队尾指针 ptail 置 NULL、结点计数clen 为 0。返回队列指针malloc 失败返回 NULL。LQue_t *create_link_queue() { LQue_t *pqlink malloc(sizeof(LQue_t)); if(pqlink NULL) { printf(malloc error\n); return NULL; } pqlink-clen 0; pqlink-phead NULL; pqlink-ptail NULL; return pqlink; }en_link_queue 入队功能在队尾插入新结点(尾插法)。队列为空时队头、队尾都指向新结点队列非空时原队尾结点指向新结点更新队尾指针计数自增。返回0 成功-1 失败(malloc 失败)。int en_link_queue(LQue_t *pqlink,Data_t data) { Node_t *pnode malloc(sizeof(Node_t)); if(pnode NULL) { printf(malloc error\n); return -1; } pnode-data data; pnode-pnext NULL; if(pqlink-clen 0) { pqlink-phead pnode; pqlink-ptail pnode; pqlink-clen; } else { pqlink-ptail-pnext pnode; pqlink-ptail pnode; pqlink-clen; } return 0; }de_link_queue 出队功能删除队头结点并带回其数据。结点数 ≥ 2 时队头指针后移一位后释放旧队头结点数 1 时释放后队头、队尾都置 NULL。返回0 成功-1 失败(空队列)。int de_link_queue(LQue_t *pqlink,Data_t *data) { Node_t *pfree pqlink-phead; if(pfree NULL) { return -1; } if(pqlink-clen 2) { pqlink-phead pfree-pnext; *data pfree-data; free(pfree); pqlink-clen--; return 0; } else if(pqlink-clen 1) { *data pfree-data; free(pfree); pqlink-phead NULL; pqlink-ptail NULL; pqlink-clen 0; return 0; } }get_link_queue_head 获取队头元素功能读取队头结点的 data 数据不删除结点。返回0 成功-1 失败(空队列)。int get_link_queue_head(LQue_t *pqlink,Data_t *data) { Node_t *ptemp pqlink-phead; if(ptemp ! NULL) { *data ptemp-data; return 0; } return -1; }show_link_queue 遍历打印队列功能从队头开始循环遍历打印队列中所有 data 数据。返回0 成功-1 失败(空队列)。int show_link_queue(LQue_t *pqlink) { Node_t *pnode pqlink-phead; if(pnode NULL) { return -1; } while(pnode ! NULL) { printf(%d ,pnode-data); pnode pnode-pnext; } printf(\n); return 0; }free_link_queue 销毁队列功能循环释放全部数据结点最后释放队列管理结构体。返回0 成功-1 失败(空队列/入参错误)。int free_link_queue(LQue_t *pqlink) { Node_t *pfree pqlink-phead; Node_t *ptemp NULL; if(pfree NULL) return -1; while(pfree ! NULL) { ptemp pfree-pnext; free(pfree); pfree ptemp; } pqlink-clen 0; pqlink-phead NULL; pqlink-ptail NULL; free(pqlink); return 0; }3. 测试 main 函数 main.c#include linkqueue.h int main(void) { LQue_t *pqlink NULL; Data_t data 0; pqlink create_link_queue(); if(pqlink NULL) { return -1; } en_link_queue(pqlink,1); en_link_queue(pqlink,2); en_link_queue(pqlink,3); en_link_queue(pqlink,4); en_link_queue(pqlink,5); show_link_queue(pqlink); printf(----------\n); de_link_queue(pqlink,data); show_link_queue(pqlink); printf(----------\n); free_link_queue(pqlink); return 0; }4. 编译运行 内存检测编译gcc main.c linkqueue.c -o linkqueue_demo运行程序./linkqueue_demovalgrind 检测内存泄漏写队列务必检测内存泄漏保证每一块 malloc 都有对应的 freevalgrind --leak-checkfull ./linkqueue_demo运行输出结果1 2 3 4 5 2 3 4 5三、循环队列1. 头文件 cyclequeue.h#ifndef _CYCLEQUEUE_H #define _CYCLEQUEUE_H #include stdio.h #include stdlib.h #define CYCQUE 10 //循环队列容量(最多存储 CYCQUE-1 个元素) typedef int Data_t; /* 循环队列对象结构体:数组空间首地址 队头下标 队尾下标 */ typedef struct cycle_queue { Data_t *pbase; // 存储数据的一维数组首地址 int head; // 队头下标 int tail; // 队尾下标 }CQue_t; extern CQue_t *create_cyclequeue(); extern int is_empty_cycle_queue(CQue_t *pcque); extern int is_full_cycle_queue(CQue_t *pcque); extern int en_cycle_queue(CQue_t *pcque,Data_t data); extern int de_cycle_queue(CQue_t *pcque,Data_t *data); extern int show_cycle_queue(CQue_t *pcque); extern int get_cyclequeue_head(CQue_t *pcque,Data_t *data); extern void free_cycqueue(CQue_t *pcque); #endif2. 功能实现 cyclequeue.ccreate_cyclequeue 创建队列功能分配队列管理结构体并分配容量为 CYCQUE 的数组空间初始化队头下标 head 为 0、队尾下标 tail 为 0。返回队列指针malloc 失败返回 NULL。CQue_t *create_cyclequeue() { CQue_t *pcque malloc(sizeof(CQue_t)); if(pcque NULL) { printf(malloc fail\n); return NULL; } pcque-pbase malloc(sizeof(Data_t)*CYCQUE); if(pcque-pbase NULL) { printf(malloc fail\n); free(pcque); return NULL; } pcque-head 0; pcque-tail 0; return pcque; }is_empty_cycle_queue 判空功能队头下标等于队尾下标即为空队列。返回1 空0 非空-1 入参为 NULL。int is_empty_cycle_queue(CQue_t *pcque) { if(pcque NULL) { return -1; } else { return pcque-head pcque-tail; } }is_full_cycle_queue 判满功能队尾下标再走一步就追上队头下标即为满队列(牺牲一个存储单元区分空与满)。返回1 满0 未满-1 入参为 NULL。int is_full_cycle_queue(CQue_t *pcque) { if(pcque NULL) { return -1; } else { return (pcque-tail1) % CYCQUE pcque-head; } }en_cycle_queue 入队功能在队尾下标处写入数据队尾下标按(tail1)%CYCQUE循环后移。队列满时入队失败。返回0 成功-1 失败(队列满或入参为 NULL)。int en_cycle_queue(CQue_t *pcque,Data_t data) { if(pcque NULL) { return -1; } if(is_full_cycle_queue(pcque) ! 0) { return -1; } pcque-pbase[pcque-tail] data; pcque-tail (pcque-tail1) % CYCQUE; return 0; }de_cycle_queue 出队功能读取队头下标处的数据队头下标按(head1)%CYCQUE循环后移。空队列时出队失败。返回0 成功-1 失败(空队列或入参为 NULL)。int de_cycle_queue(CQue_t *pcque,Data_t *data) { if(pcque NULL) { return -1; } if(is_empty_cycle_queue(pcque) ! 0) { return -1; } *data pcque-pbase[pcque-head]; pcque-head (pcque-head1) % CYCQUE; return 0; }get_cyclequeue_head 获取队头元素功能读取队头下标的元素但不删除。返回0 成功-1 失败(空队列或入参为 NULL)。int get_cyclequeue_head(CQue_t *pcque,Data_t *data) { if(pcque NULL) { return -1; } if(is_empty_cycle_queue(pcque) ! 0) { return -1; } *data pcque-pbase[pcque-head]; return 0; }show_cycle_queue 遍历打印队列功能从队头下标开始按循环方式依次遍历到队尾下标打印所有数据。返回0 成功-1 失败(入参为 NULL)。int show_cycle_queue(CQue_t *pcque) { if(pcque NULL) { return -1; } int ptemp pcque-head; while(ptemp ! pcque-tail) { printf(%d ,pcque-pbase[ptemp]); ptemp (ptemp1) % CYCQUE; } printf(\n); return 0; }free_cycqueue 销毁队列功能先释放数组空间再释放队列管理结构体。void free_cycqueue(CQue_t *pcque) { if(pcque NULL) { return; } free(pcque-pbase); free(pcque); return; }3. 测试 main 函数 main.c#include cyclequeue.h int main(void) { CQue_t *pcque create_cyclequeue(); Data_t data; en_cycle_queue(pcque,1); en_cycle_queue(pcque,2); en_cycle_queue(pcque,3); en_cycle_queue(pcque,4); en_cycle_queue(pcque,5); show_cycle_queue(pcque); printf(----------\n); de_cycle_queue(pcque,data); printf(----------\n); show_cycle_queue(pcque); free_cycqueue(pcque); return 0; }4. 编译运行 内存检测编译gcc main.c cyclequeue.c -o cyclequeue_demo运行程序./cyclequeue_demovalgrind 检测内存泄漏写队列务必检测内存泄漏保证每一块 malloc 都有对应的 freevalgrind --leak-checkfull ./cyclequeue_demo运行输出结果1 2 3 4 5 2 3 4 5四、链式队列与循环队列对比对比项链式队列循环队列存储结构链式存储(链表结点)顺序存储(数组)空间动态分配按需申请需要预分配固定容量判空clen 0 / phead NULLhead tail判满一般无需判满(tail1) % CYCQUE head假溢出不存在通过取模循环解决缺点指针域额外占用内存容量固定扩容不便