电子工程建设信息网站,lamp网站架构,河南平台网站建设设计,商场建设相关网站1.队列的定义 队列是一种特殊的线性表#xff0c;它遵循先进先出#xff08;FIFO#xff09;的原则。在队列中#xff0c;只允许在表的一端进行插入操作#xff08;队尾#xff09;#xff0c;而在另一端进行删除操作#xff08;队头#xff09;。这种数据结构确保了最… 1.队列的定义 队列是一种特殊的线性表它遵循先进先出FIFO的原则。在队列中只允许在表的一端进行插入操作队尾而在另一端进行删除操作队头。这种数据结构确保了最先进入队列的元素总是最先离开队列。队列中没有元素时被称为空队列。队列的组织和实施训练通常由队列条令予以规定用于规范部队、分队队列及其在各种条件下的运动队形和动作。
出队的是队头入队的为队尾 2.实现队列 对于队列我们知道是一种线性表我们可以使用单链表、双向链表或者数组都可以实现这里我们首先介绍使用单链表实现的。
对于单链表实现队列我们知道队列有队头和队尾所以设置两个指针*phead 和*ptail表示头尾但是如何找到头和尾需要讨论如果只是创建一个单链表那么索引头尾就十分繁琐所以我们可以设计两个链表一个存储数据一个索引头尾这样就很方便的实现了队列。
typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue; 解释创建一个单链表 QueueNode 用来存储队列元素再创建一个单链表 Queue 索引队头和队尾插入数据时 QueueNode 使用动态内存申请开辟空间节点 newnode 尾节点 *ptail 指向新开辟的节点即索引队尾队头保持不变从而实现索引头尾的功能。 3.队列的相关操作 3.1 初始化和销毁
初始化断言传入指针不为NULL将起索引作用的链表头尾均置为NULL链表长度初始化为0。
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}销毁创建一个cur指针保存头结点依次释放最后将整个链表初始化。
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}
3.2 插入和删除
插入队列只有队尾插入所以直接在QueueNode单链表上动态内存开辟一个newnode新节点然后让单链表Queue索引头尾修改Queue中的数据。
// 队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-next NULL;newnode-val x;if (pq-ptail NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}
删除 首先判断删除的链表是否为NULL不为NULL则可以删除所以创建一个新的next 保存待删除节点释放节点置为NULL当然若只有一个节点即*phead就是*ptail将他们置为NULL即可。
// 队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq-size ! 0);/*QNode* next pq-phead-next;free(pq-phead);pq-phead next;if (pq-phead NULL)pq-ptail NULL;*/// 一个节点if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptail NULL;}else // 多个节点{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
} 3.3 取出队头或队尾的数据
取出队头这时两个单链表的作用就体现出来了取队头直接取phead-val的元素即可。
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-phead);return pq-phead-val;
}取出队尾直接返回尾节点ptail-val的数据即可。
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-ptail);return pq-ptail-val;
} 3.4 判空与计算链表长度
计算链表长度直接返回Queue中的size即可
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}判空 判断链表长度是否为0是则为空反之不为空。
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}
