网站做百度口碑,北京杰诚 做网站,百度广告电话号码,wordpress文章来源文章目录 有关队列的概念队列的结点设计及初始化队列的销毁判空和计数入队操作出队操作 有关队列的概念
队列:只允许在一端进行插入数据操作#xff0c;在另一端进行删除数据操作的特殊线性表#xff0c;队列具有先进先出FIFO(First In First Out)入队列:进行插入操作的一端… 文章目录 有关队列的概念队列的结点设计及初始化队列的销毁判空和计数入队操作出队操作 有关队列的概念
队列:只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out)入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头 联想一下链表在单链表中只能对表尾进行插入对表头进行结点的删除这样强限制性的链表就是所说的队列。也就是说队列是限定在表的一端进行插入表的另一端进行删除的数据结构。 如图去买票排队每一列队伍都有一个队尾和队首先来的先买票后来的后买买好的就从队首出去新来买票的就需要从队尾继续排队。
1.结构 队列由两部分组成——队头front和队尾rear。队头是队列中允许删除元素的一端而队尾是允许添加元素的一端。 队列是一个线性的数据结构并且这个数据结构只允许在一端进行插入另一端进行删除禁止直接访问除这两端以外的一切数据且队列是一个先进先出的数据结构。 就比如下图 队列存储结构的实现有以下两种方式 ①顺序队列在顺序表的基础上实现的队列结构。 ②链队列在链表的基础上实现的队列结构。
两者的区别仅是顺序表和链表的区别即在实际的物理空间中数据集中存储的队列是顺序队列分散存储的队列是链队列。
队列的结点设计及初始化
队列只有链式的设计方法其本身分为多种队列如顺序队列和循环队列还有衍生的优先队列等等以顺序队列的设计为例。
结点设计 首先是队列的结点设计可以设计出两个结构体一个结构体 Node 表示结点其中包含有 data 域和 next 指针如图
其中 data 表示数据其可以是简单的类型也可以是复杂的结构体。next 指针表示下一个的指针其指向下一个结点通过 next 指针将各个结点链接。
结构体设计 然后再添加一个结构体其包括了两个分别永远指向队列的队尾和队首的指针看到这里是不是觉得和栈很像
主要的操作只对这两个指针进行操作。为使后续操作更加方便我们不妨再多设置一个用来计数的成员如图所示 其结构体设计的代码可以表示为
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;队列的销毁判空和计数
这块区域较简单仅销毁区域需要注意将每个节点依次释放避免内存泄漏
这部分代码可以表示为
//销毁
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;
}
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}入队操作 进行入队操作的时候同样的首先需要判断队列是否为空如果队列为空的话需要将头指针和尾指针一同指向第一个结点代码如下
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc newnode fail);}newnode-val x;newnode-next NULL;if (pq-ptail NULL){pq-phead newnode;pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}出队操作 出队(pop)操作是指在队列不为空的情况下进行的一个判断当然在此也一定要进行队列判空的操。
如图如果队列只有一个元素了也就是说头尾指针均指向了同一个结点那么直接将头尾两指针置空并释放这一个结点即可代码如下
// 队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq-size ! 0);if (pq-size 1){free(pq-phead);pq-phead pq-ptail NULL;}else{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}
