网站后台模板 下载,项目建议书,提供网站建设的公司,备案号放网站下面居中目录
1.队列的概念及结构
2.队列的实现
2.1队列结构定义
2.2队列的初始化及销毁
2.3数据入队
2.4数据出队
2.5访问队头数据
2.6访问队尾数据
2.6判断队列是否为空
2.7求队列的大小
2.7打印队列 1.队列的概念及结构 队列#xff1a;只允许在一端进行插入数据操作只允许在一端进行插入数据操作另一端进行删除数据操作的特殊线性表 队列中先进先出FIFOFirst In First Out 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头 2.队列的实现 队列结构可以使用数组和链表结构实现但一般采用的是链表因为对于数组结构队头出数据的效率较低 2.1队列结构定义 使用链表实现队列队列中的每个元素都是节点的形式所以需要定义节点的结构 对于队列其具有队尾入数据队头出数据的特性所以其结构定义需要两个指针分别指向队头和队尾 typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;
}Queue;
2.2队列的初始化及销毁 初始化即队列为空队列队头指针和队尾指针都指向空 销毁队列即释放队列中所有节点的空间队头指针和队尾指针重新指向空 //队列初始化
void QueueInit(Queue* pq)
{assert(pq);pq-head pq-tail NULL;
}
//队列销毁
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* del cur;cur cur-next;free(del);}pq-head pq-tail NULL;
}2.3数据入队 队列结构中数据入队从队尾入需要考虑空队列和非空队列两种情况 1️⃣空队列 2️⃣非空队列 空队列和非空队列不同的是空队列插入数据时需要更新队头指针 //数据入队
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}else{newnode-data x;newnode-next NULL;}//空队列时插入if (pq-tail NULL){pq-head pq-tail newnode;}//非空队列时插入else{pq-tail-next newnode;//链接新元素pq-tail newnode;//更新队尾}
}2.4数据出队 队列结构中数据出队从队头出对于空队列出队操作非法 出队操作后需要更新队头指针并释放已出队节点的空间 特殊情况队列中只有一个节点 //数据出队
void QueuePop(Queue* pq)
{assert(pq);//空队列不能进行出队操作assert(!QueueEmpty(pq));//队列中只有一个元素if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* del pq-head;pq-head pq-head-next;free(del);del NULL;}
}2.5访问队头数据 队头数据的访问操作在队列为空时非法所以需要先断言非空链表才可以进行队头数据的访问操作通过队头指针访问即可 //访问队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;}2.6访问队尾数据 队尾数据的访问操作在队列为空时非法所以需要先断言非空链表才可以进行队尾数据的访问操作通过队尾指针访问即可 //访问队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}2.6判断队列是否为空 队列为空则队头指针和队尾指针都指向空可以使用if-else语句进行返回 也可以参考以下代码直接返回pq-head NULL pq-tail NULL只有当pq-head和pq-tail同时为NULL是才返回真即队列为空 Note 判空函数的返回类型为bool但是C语言标准中没有bool类型所以需要我们自己定义 #define bool int //判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);/*if (pq-tail pq-head NULL){return true;}else{return false;}*/return pq-head NULL pq-tail NULL;
}2.7求队列的大小 求队列的大小遍历统计节点个数并返回即可 //求队列的大小
int QueueSize(Queue* pq)
{assert(pq);int size 0;QNode* cur pq-head;while (cur){size;cur cur-next;}return size;
}
2.7打印队列 为了便于观察入队与出队操作可以编写一个打印函数便于调试 //打印队列
void QueuePrint(Queue* pq)
{assert(pq);QNode* cur pq-head;while (cur){printf(%d , cur-data);cur cur-next;}printf(\n);
}
