数据结构——队列

简介: 队列是一种特殊的线性结构只允许在一端进行插入操作,在另一端进行删除操作,队列具有先进先出FIFO(First In First Out)入队:进行插入操作,进行插入的一端称为队尾出队:进行删除操作,进行删除的一端称为队头

队列的概念

队列是一种特殊的线性结构

只允许在一端进行插入操作,在另一端进行删除操作,队列具有先进先出FIFO(First In First Out)

入队:进行插入操作,进行插入的一端称为队尾

出队:进行删除操作,进行删除的一端称为队头


a9f6dd5b5bed4ac58306d1633a2d70c7.png


队列的实现

因为队列在尾进在头出,如果用顺序表实现,那么出队就需要挪动顺序表的数据,效率低

所以队列用链表实现更好


我们先写一个链表的结构体:

typedef int QueueDataType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QueueDataType data;
}QNode;


在主函数中,为了方便,我们定义一个头指针head指向队头和尾指针tail指向队尾


QNode* head = NULL;
QNode* tail = NULL;

1

2

如果这么写的话,在设计函数时,就要至少传2个指针,并且为二级指针,这是否的麻烦


所以我们可以再定义一个结构体,将head和tail都放到这个结构体中,那么设计函数时只需要传一个指针就可以了


typedef struct Queue
{
  QNode* head;
  QNode* tail;
  int size;
}Queue;


这样设计的话,函数中传这个结构体的参数,通过结构体指针就可以改变结构体了,所以也不用传二级指针了


这里在结构体内还定义了一个int size,这是表示队列的长度,这个设计并非多余,在后面的实现中就会发现这个size能提高效率


这里的队列实现需要定义2个结构体,这是在之前的数据结构中没有出现的


初始化

void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
  pq->size = 0;
}


将head和tail都初始化为空,size为0


销毁

void QueueDestroy(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
  QNode* nex = cur->next;
  free(cur);
  cur = nex;
  }
  pq->head = NULL;
  pq->tail = NULL;
  pq->size = 0;
}
1


入队

入队,首先就是开辟一个新节点


QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
  perror("malloc fail");
  return;
  }
  newnode->data = x;
  newnode->next = NULL;
1


然后就是入队了,在队尾入队

这里如果head==NULL,就说明当前队列还没有元素head和tail都为空

所以让head指向这个第一个节点,同时这个节点也是自己的尾,tail也应指向这个节点


pq->head = pq->tail = newnode;

1

如果head不为空,就说明当前队列中有元素,直接在tail后面插入新节点即可


void QueuePush(Queue* pq, QueueDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
  perror("malloc fail");
  return;
  }
  newnode->data = x;
  newnode->next = NULL;
  if (pq->head == NULL)
  {
  pq->head = pq->tail = newnode;
  }
  else
  {
  pq->tail->next = newnode;
  pq->tail = pq->tail->next;
  }
  pq->size++;
}
1
2


出队

出队,首先应用断言判断一下队列是否为空


assert(!QueueEmpty(pq));

1

在队头出队


首先用next指针保存head->next,然后就可以free掉head了,然后再将head指向新的头next


QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
1
2

3

在这里会发现,如果队列只要一个节点,next为空,然后虽然能够让head为空,但tail不会被改变,所以我们需要改一下:


if (pq->head->next==NULL)
  {
  free(pq->head);
  pq->head = pq->tail = NULL;
  }
  else
  {
  QNode* next = pq->head->next;
  free(pq->head);
  pq->head = next;
  }
1


11

所以最终代码:


void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  if (pq->head->next==NULL)
  {
  free(pq->head);
  pq->head = pq->tail = NULL;
  }
  else
  {
  QNode* next = pq->head->next;
  free(pq->head);
  pq->head = next;
  }
  pq->size--;
}



判空

bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->size == 0;
}


队列长度

int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}


这里就最能看出在结构体中定义size的好处了

如果不去定义,那么在这里求长度就会遍历一遍队列,导致效率低


而之前定义了size,这里直接返回size即可,效率高


返回队头元素

QueueDataType QueueFront(Queue* pq)
{
  assert(pq);
  return pq->head->data;


一般通过QueueFront和QueuePop2个函数来得到队列中的数据


打印队列中数据:


while (!QueueEmpty(&q))
  {
  printf("%d ", QueueFront(&q));
  QueuePop(&q);
  }
1


返回队尾元素

QueueDataType QueueBack(Queue* pq)
{
  assert(pq);
  return pq->tail->data;
}


目录
相关文章
|
27天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
123 9
|
2月前
|
缓存 算法 调度
数据结构之 - 双端队列数据结构详解: 从基础到实现
数据结构之 - 双端队列数据结构详解: 从基础到实现
71 5
|
2月前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
109 64
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
初步认识栈和队列
初步认识栈和队列
61 10
|
2月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
23 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
2月前
|
存储 安全 Java
【用Java学习数据结构系列】探索栈和队列的无尽秘密
【用Java学习数据结构系列】探索栈和队列的无尽秘密
32 2
【数据结构】--- 栈和队列
【数据结构】--- 栈和队列
|
2月前
|
消息中间件 存储 Java
数据结构之 - 深入探析队列数据结构: 助你理解其原理与应用
数据结构之 - 深入探析队列数据结构: 助你理解其原理与应用
36 4
|
2月前
【初阶数据结构】深入解析队列:探索底层逻辑
【初阶数据结构】深入解析队列:探索底层逻辑