[C语言实现]数据结构之《关于我转生成队列这档事》

2023-06-16 22:35| 来源: 网络整理| 查看: 265

🥰作者: FlashRider

🌏专栏: 数据结构

🍖知识概要：详解队列的概念、顺序队列和链式队列的优点和缺点，以及代码实现。

什么是队列？

选择什么结构来实现队列？

链式队列的实现

队列的结构体实现

队列需要的函数声明

队列的函数实现

测试代码

什么是队列？

队列其实就是一种操作受限的线性表（即：只能在表头弹出，表尾插入）。我们把数据的删除端称为队头，把数据的插入端称为队尾。生活中，我们在食堂打饭排队的时候，从队尾进入队列，我们前面的人打完饭后从队头离开队列。由此可见，队列这种结构也是非常重要的，在生活中随处可见。

选择什么结构来实现队列？

我们需要对队列进行插入删除操作的时候，都是从队尾插入，队头删除，因此我们选用链式结构来实现队列（链表实现队列），如果我们采用顺序结构（顺序表）来实现队列的话，在删除之后就要进行大量的数据挪动，如果不挪动就会造成一定程度的空间浪费。

那么我们选用单链表，还是双链表来实现队列？如果我们选择双向链表来实现队列，在进行插入删除的时候会非常轻松，但是总有一种大材小用的感觉。如果我们选用单链表实现队列，我们就要实现头删和尾插，但是尾插需要找尾，这对于单链表来说是O(n)的时间复杂度，因此我们新建一个结点tail来存储尾结点，这样尾插就是O(1)了。

链式队列的实现

需要的头文件： stdlib.h stdbool.h assert.h stdio.h

队列的结构体实现 //队列元素类型 typedef int QDataType; //链式队列结点 typedef struct QueueNode { QDataType x; struct QueueNode* next; }QNode; //队列 typedef struct Queue { QNode* front;//队头 QNode* tail;//队尾 }Queue; 队列需要的函数声明

首先是老四样：初始化、插入删除、获取长度、销毁。其次还有：判空、获取队头元素、获取队尾元素。

void QueueInit(Queue* pq);//初始化队列 void QueuePush(Queue* pq, QDataType x);//队尾插入元素 void QueuePop(Queue* pq);//删除队头元素 bool QueueEmpty(Queue* pq);//判断队列是否为空 int QueueSize(Queue* pq);//获取队列长度 QDataType QueueFront(Queue* pq);//获取队头元素 QDataType QueueBack(Queue* pq);//获取队尾元素 void QueueDestroy(Queue* pq);//销毁队列队列的函数实现 //初始化队列 void QueueInit(Queue* pq) { assert(pq); pq->front = pq->tail = NULL; } //队尾插入元素 void QueuePush(Queue* pq, QDataType x) { assert(pq); //如果队列为空 front也会改变所以特判 QNode* newnode = (QNode*)malloc(sizeof(QNode)); newnode->data = x; newnode->next = NULL; if(pq->front == NULL) pq->front = pq->tail = newnode; else { pq->tail->next = newnode; pq->tail = pq->tail->next; } } //删除队头元素 void QueuePop(Queue* pq) { assert(!(QueueEmpty(pq))); //如果只有一个元素 tail也会改变所以特判 QNode* del = pq->front; if(pq->front == pq->tail) pq->front = pq->tail = NULL; else pq->front = pq->front->next; free(del); } //判断队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->front == NULL; } //获取队列长度 int QueueSize(Queue* pq) { assert(pq); int cnt = 0; QNode* cur = pq->front; while(cur) { cnt++; cur = cur->next; } return cnt; } //获取队头元素 QDataType QueueFront(Queue* pq) { assert(!QueueEmpty(pq)); return pq->front->data; } //获取队尾元素 QDataType QueueBack(Queue* pq) { assert(!QueueEmpty(pq)); return pq->tail->data; } //销毁队列 void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->front; while(cur) { QNode* next = cur->next; free(cur); cur = next; } pq->front = pq->tail = NULL; } 测试代码 int main(void) { Queue q; QueueInit(&q); printf("插入前QueueIsEmpty >> %d (1真0假)\n", QueueEmpty(&q)); printf("插入后QueueSize >> %d\n\n", QueueSize(&q)); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); QueuePush(&q, 5); printf("插入后QueueIsEmpty >> %d (1真0假)\n", QueueEmpty(&q)); printf("插入后QueueSize >> %d\n\n", QueueSize(&q)); while(!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } printf("\n"); printf("全部弹出后QueueIsEmpty >> %d (1真0假)\n", QueueEmpty(&q)); printf("全部弹出后QueueSize >> %d\n", QueueSize(&q)); return 0; }

运行结果：

如果这篇博客对您有帮助的话，请记得点个赞或者三连。

【本文地址】

公司简介

联系我们