数据结构队列特性与操作

一、 队列1.1. 特性队列是只允许再两端进行插入和删除操作的线性表在队尾插入在队头删除插入的一段被称为“队尾”删除的一端被称为“队头”。队列包括顺序队列(循环队列)、链式队列。特性先进先出 FIFO操作创建、入列、出列、判断是否为满或空、清空注意为了避免假溢出问题即队列前面还有空闲但是队尾已经出现越界所以在实际使用队列时为了使队列空间能重复使用往往对队列的使用方法稍加改进需要引入循环队列。一般顺序队列也指循环循环队列是把顺序队列首尾相连把存储队列元素的表从逻辑上看成一个环成为循环队列。1.2. 循环队列(顺序队列)逻辑结构线性结构存储结构顺序存储操作创建、入列、出列、判满和判空、清空#define N 6 typedef int datatype; typedef struct { datatype data[N];//循环队列的数组 int rear;//存数据端 rear 后面 int front;//取数据端 front 前面 }sequeue_t;i表示front或rear方法一利用if判断if(i1N)i0;elsei;方法二利用模运算 大家习惯用这个方法i(i1)%N1.2.1. 代码实现sequeue.h#ifndef __SEQUEUE_H__ #define __SEQUEUE_H__ #define N 6 typedef int datatype; typedef struct { datatype data[N];//循环队列的数组 int rear;//存数据端 rear 后面 int front;//取数据端 front 前面 }sequeue_t; // 1. 创建一个空的队列 sequeue_t *createEmptySequeue(); // 2. 判断队列是否为满 int isFullSequeue(sequeue_t *p); // 3. 入列 data代表入列的数据 int inSequeue(sequeue_t *p,datatype data); // 4. 判断队列是否为空 int isEmptySequeue(sequeue_t *p); // 5. 出列 datatype outSequeue(sequeue_t *p); // 6. 求队列的长度 int lengthSequeue(sequeue_t *p); // 7. 清空队列函数 void clearSequeue(sequeue_t *p); #endif1创建一个空队列// 1. 创建一个空的队列 sequeue_t *createEmptySequeue() { sequeue_t *p (sequeue_t *)malloc(sizeof(sequeue_t)); if(NULL p) { printf(createEmptySequeue err\n); return NULL; } p-front 0; p-rear 0; return p; }2判断队列是否为满// 2. 判断队列是否为满 int isFullSequeue(sequeue_t *p) { return (p-rear 1) % N p-front; }3入队// 3. 入列 data代表入列的数据 int inSequeue(sequeue_t *p, datatype data) { // 1. 容错判断 if (isFullSequeue(p)) ; { printf(inSequeue err\n); return -1; } p-data[p-rear] data; p-rear (p-rear 1) % N; return 0; }4判断队列是否为空// 4. 判断队列是否为空 int isEmptySequeue(sequeue_t *p) { return p-front p-rear; }5出列// 5. 出列 datatype outSequeue(sequeue_t *p) { if (isEmptySequeue(p)) { printf(outSequeue err\n); return -1; } datatype temp p-data[p-front]; p-front (p-front 1) % N; return temp; }6队列长度// 6. 求队列的长度 int lengthSequeue(sequeue_t *p) { #if 1 return (p-rear - p-front N) % N; #else if (p-rear p-front) return p-rear - p-front; else return p-rear - p-front N; #endif }7清空队列// 7. 清空队列函数 void clearSequeue(sequeue_t *p) { p-front p-rear; // 思想 只要队列不为空就出列 // while(!isEmptySequeue(p)) // outSequeue(p); }循环队列如果数组的元素个数为N那么队列中最多能够存储的数据数的多少 N-1个 为什么答rear 后面 队尾在插入的时候插入之前需要先判断他的下一个为位置是否 等于 front 来判断队列是否为满会造成浪费一个存储位置。1.3. 链式队列逻辑结构线性结构存储结构链式存储操作创建、入队、出队、清空、判空typedef int datatype; typedef struct node_t { datatype data; struct node_t *next; } linkqueue_node_t, *linkqueue_list_t; typedef struct // 将队列头指针和尾指针封装到一个结构体里 { linkqueue_list_t front; // 相当于队列的头指针 linkqueue_list_t rear; // 相当于队列的尾指针 // 有了链表的头指针和尾指针那么我们就可以操作这个链表 } linkqueue_t;创建空队列1.3.1. 代码实现linkqueue.h#ifndef __LINKQUEUE_H__ #define __LINKQUEUE_H__ typedef int datatype; typedef struct node_t { datatype data; struct node_t *next; } linkqueue_node_t, *linkqueue_list_t; typedef struct //将队列头指针和尾指针封装到一个结构体里 { linkqueue_list_t front; //相当于队列的头指针 linkqueue_list_t rear; //相当于队列的尾指针 //有了链表的头指针和尾指针那么我们就可以操作这个链表 } linkqueue_t; //1.创建一个空的队列用有头链表。 linkqueue_t *createEmptyLinkQueue(); //2.入列 data代表入列的数据 int inLinkQueue(linkqueue_t *p, datatype data); //3.出列 //思想每次释放front所指节点然后移动front到后一个节点返回当前节点数据 datatype outLinkQueue(linkqueue_t *p); //4.判断队列是否为空 int isEmptyLinkQueue(linkqueue_t *p); //5.求队列长度的函数 int lengthLinkQueue(linkqueue_t *p); //6.清空队列 void clearLinkQueue(linkqueue_t *p); #endif1创建一个空队列//1.创建一个空的队列用有头链表。 linkqueue_t *createEmptyLinkQueue() { // 1. 申请空间, 存放头尾指针 linkqueue_t *p (linkqueue_t *)malloc(sizeof(linkqueue_t)); if(NULL p){ printf(createEmptyLinkQueue p malloc err\n); return NULL; } // 2. 申请链表的头节点空间让rear和front都指向头节点 p-front p-rear (linkqueue_list_t)malloc(sizeof(linkqueue_node_t)); if(NULL p-front) { printf(createEmptyLinkQueue h malloc err\n); return NULL; } // 初始化头节点 p-rear-next NULL; return p; }2入列// 2.入列 data代表入列的数据 int inLinkQueue(linkqueue_t *p, datatype data) { linkqueue_list_t pnew (linkqueue_list_t)malloc(sizeof(linkqueue_node_t)); if (NULL pnew) { printf(inLinkQueue pnew malloc err\n); return -1; } // 对新节点初始化 pnew-data data; pnew-next NULL; // 将新节点连接到链表的尾部 p-rear-next pnew; p-rear pnew; return 0; }3出列// 3.出列 // 思想每次释放front所指节点然后移动front到后一个节点返回当前节点数据 datatype outLinkQueue(linkqueue_t *p) { linkqueue_list_t pdel NULL; // 1. 容错判断 if (isEmptyLinkQueue(p)) { printf(outLinkQueue err\n); return -1; } // 2. 出列数据 // 1) 定义pdel指向即将被删除的节点就是front指向的节点 pdel p-front; // 2) 将front向后移动一个位置 p-front p-front-next; // 3) 释放被删除节点 free(pdel); pdel NULL; // 4) 将数据出列 return p-front-data; }4判断队列是否为空//4.判断队列是否为空 int isEmptyLinkQueue(linkqueue_t *p) { return p-front p-rear; }5求队列长度// 5.求队列长度的函数 int lengthLinkQueue(linkqueue_t *p) { int len 0; linkqueue_list_t t p-front; while (t-next ! NULL) { t t-next; len; } return len; }6清空队列// 6.清空队列 void clearLinkQueue(linkqueue_t *p) { while(!isEmptyLinkQueue(p)) outLinkQueue(p); }