程野,司马张良,张颖涵
在前面两篇博客中，我分别使用了静态数组和动态数组来模拟循环队列。但是线性表中和队列最神似的莫过于链表了。我在前面也使用了大量的篇幅来讲述了链表的各种操作。今天我们使用一种比较特殊的链表——非循环双向链表来实现队列。首先这里的说明的是构建的是普通的队列，而不是循环队列。当我们使用数组的时候创建循环队列是为了节省存储空间，而来到链表中时，每一个节点都是动态申请和释放的，不会造成空间的浪费，所以就不需要采用循环队列了。第二，大家在很多书上看到的是使用单链表实现队列，我这里将会使用带头结点尾结点的非循环双链表实现，虽然多维护了两个节点和指针域，但是在链表头尾进行插入删除的时候不需要遍历链表了，队列操作变得非常的方便。真正实现了只在头尾操作。
核心代码如下：
（1）初始化队列
我要评论
//初始化带头结点和尾结点的非循环双向链表
void initialqueue(queue **phead,queue **ptail){
*phead = (queue *)malloc(sizeof(queue));
*ptail = (queue *)malloc(sizeof(queue));
if (*phead == null || *ptail == null) {
printf("%s函数执行，内存分配失败，初始化双链表失败\n",__function__);
}else{
//这个里面是关键，也是判空的重要条件
(*phead)->next = null;
(*ptail)->prior = null;
//链表为空的时候把头结点和尾结点连起来
(*phead)->prior = *ptail;
(*ptail)->next = *phead;
printf("%s函数执行，带头结点和尾节点的双向非循环链表初始化成功\n",__function__);
}
}
//入队,也就是在链表的尾部插入节点
void enqueue(queue *head,queue *tail,int x){
queue *pinsert;
pinsert = (queue *)malloc(sizeof(queue));
memset(pinsert, 0, sizeof(queue));
pinsert->next = null;
pinsert->prior = null;
pinsert->element = x;
tail->next->prior = pinsert;
pinsert->next = tail->next;
tail->next = pinsert;
pinsert->prior = tail;
}
//出队,在队列头部删除元素
void dequeue(queue *head,queue *tail){
if (isempty(head,tail)) {
printf("队列为空，出队列失败\n");
}else{
queue *pfreenode;
pfreenode = head->prior;
head->prior->prior->next = head;
head->prior = head->prior->prior;
free(pfreenode);
pfreenode = null;
}
}
（4）打印所有节点
//打印出从队列头部到尾部的所有元素
void printqueue(queue *head,queue *tail){
queue *pmove;
pmove = head->prior;
printf("当前队列中的元素为(从头部开始):");
while (pmove != tail) {
printf("%d ",pmove->element);
pmove = pmove->prior;
}
printf("\n");
}
//判断队列是否为空,为空返回1，否则返回0
int isempty(queue *head,queue *tail){
if (head->prior == tail) {
return 1;
}
return 0;
}
int main(int argc, const char * argv[]) {
queue *phead;//头结点
queue *ptail;//尾结点
initialqueue(&phead, &ptail);
enqueue(phead, ptail, 2);enqueue(phead, ptail, 1);
enqueue(phead, ptail, 9);enqueue(phead, ptail, 3);enqueue(phead, ptail, 4);
printqueue(phead, ptail);
dequeue(phead,ptail);dequeue(phead,ptail);dequeue(phead,ptail);
printqueue(phead, ptail);
return 0;
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论