C语言使用非循环双向链表实现队列
程序员文章站
2022-06-24 23:41:26
在前面两篇博客中,我分别使用了静态数组和动态数组来模拟循环队列。但是线性表中和队列最神似的莫过于链表了。我在前面也使用了大量的篇幅来讲述了链表的各种操作。今天我们使用一种比较特殊的链表—...
在前面两篇博客中,我分别使用了静态数组和动态数组来模拟循环队列。但是线性表中和队列最神似的莫过于链表了。我在前面也使用了大量的篇幅来讲述了链表的各种操作。今天我们使用一种比较特殊的链表——非循环双向链表来实现队列。首先这里的说明的是构建的是普通的队列,而不是循环队列。当我们使用数组的时候创建循环队列是为了节省存储空间,而来到链表中时,每一个节点都是动态申请和释放的,不会造成空间的浪费,所以就不需要采用循环队列了。第二,大家在很多书上看到的是使用单链表实现队列,我这里将会使用带头结点尾结点的非循环双链表实现,虽然多维护了两个节点和指针域,但是在链表头尾进行插入删除的时候不需要遍历链表了,队列操作变得非常的方便。真正实现了只在头尾操作。
核心代码如下:
(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__); } }
(2)入队,在尾结点插入元素
//入队,也就是在链表的尾部插入节点 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; }
(3)出队,在头结点处删除节点
//出队,在队列头部删除元素 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"); }
(5)判断队列是否为空
//判断队列是否为空,为空返回1,否则返回0 int isempty(queue *head,queue *tail){ if (head->prior == tail) { return 1; } return 0; }
(6)测试代码
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; }