市妇联门户网站平台建设情况,深圳宝安区电子厂,公众号制作模板网站,浙江省建设银行纪检官方网站目录
一、队列的概念和结构
二、队列的实现
2.1队列的初始化QueueInit
2.2队列的摧毁QueueDestroy
2.3插入结点QueuePush 2.4删除结点QueuePop
2.5返回队头QueueFront
2.6返回队尾QueueBack
2.7判断队列为空QueueEmpty
2.8统计队列数目QueueSize 一、队列的概念和…目录
一、队列的概念和结构
二、队列的实现
2.1队列的初始化QueueInit
2.2队列的摧毁QueueDestroy
2.3插入结点QueuePush 2.4删除结点QueuePop
2.5返回队头QueueFront
2.6返回队尾QueueBack
2.7判断队列为空QueueEmpty
2.8统计队列数目QueueSize 一、队列的概念和结构 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出性质。FIFO(First In First Out) 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头 二、队列的实现
队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。
当用链表实现时我们布置的结构体肯定要包含一个val还需要一个next。
typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;但结构体的布置并非到这里就结束了当我们有数据要入队时我们是不是需要让头指针遍历一遍链表找到队尾呢而且要改变队尾前一个结点next的指向是不是要传入二级指针呢同样当我们布置其他函数体时也会遇到类似的问题。那么如何让我们的代码量化到最简呢
我们再设置一个结构体来存储相关的数据这样修改指向时不用再用二级指针而是只需要修改结构体的值即可。我们用phead指向队列的头结点便于出队用ptail指向队列的尾结点便于入队
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;2.1队列的初始化QueueInit
void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}
2.2队列的摧毁QueueDestroy
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;
}
2.3插入结点QueuePush
首先我们要新开结点其次我们要判断链表是否为空如果为空那么ptail和phead都指向新结点如果不为空phead的指向不用改变而ptail的next要只想newnode然后再把ptail向后移
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;if (pq-ptail NULL){pq-ptail pq-phead newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
} 2.4删除结点QueuePop
首先先让队头指向next结点接着我们就要判断删除的是不是整个队列的最后一个结点如果删除的是最后一个结点那么就会影响到我们ptail的指向所以我们通过判断避免ptail变成野指针。
void QueuePop(Queue* pq)
{assert(pq);// assert(pq-phead);QNode* del pq-phead;pq-phead pq-phead-next;free(del);del NULL;if (pq-phead NULL)pq-ptail NULL;pq-size--;
}
2.5返回队头QueueFront
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-phead);return pq-phead-val;
}
2.6返回队尾QueueBack
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-ptail);return pq-ptail-val;
}
2.7判断队列为空QueueEmpty
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;
}
2.8统计队列数目QueueSize
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
