【数据结构】队列

简介: 【数据结构】队列

😜前言


🍎栈和队列可以说是一对好兄弟,前面学习了栈,那队列当然也少不了。对于栈而言,队列可以说具有与他相反的性质,本章就给大家领悟一下队列的魅力。

🍒队列是一种简单的数据结构,它的主要性质,就是数据先进先出(FIFO),我们可以利用这一性质,在做某些算法题时,以此为切入点,如:单调队列等等。所以说,我们要熟练其性质。


队列初始化


  • 队列的性质是先进先出(相当于一根管道),出是出一个队列的队头,进是在一个队列的队尾进,当然还可以访问队列的队头元素和队尾元素。


图示


404bf23689664d18873e04e0720bbfa4.png


d0ba768768794436b7a74d84dc4e774d.gif


那么根据列队的性质,我们该如何来选择队列的底层结构呢?是顺序表的数组还是链表呢?


假如我们选择顺序表的数组,对于入队操作是很简单的,时间复杂度为O(1),但是,出队操作效率就比较低了,需要挪动数据。并且,当入队的数据多了,数组还需要扩容,这样看来,顺序表的数组结构不是很完美,所以我们在看看链表怎么样。


如果底层是链表结构,很明显,对于出队操作就相当于链表的头删,时间复杂度为O(1),效率不错,但如果是入队操作呢?我们是否需要遍历一遍链表找到队尾,然后再进行入队呢? 这里是不需要的。我们可以定义一个指针指向链表的尾节点 (由于没有尾删的操作,所以这个指针定义的很合理),通过这个指针来进行入队操作,这样以来,入队操作也变成O(1)了。因此,总的看来,链表结构是最适合于作为队列的底层结构了。


有了对队列的认识和对队列的底层结构的断定,接下来就开始实现一个简单的队列咯。


首先是对一个队列整个框架的初始操作。


同样的,需要三个文件:queue.h queue.c test.c。queue.h用来存放所需头文件,队列相关的结构体以及功能函数接口声明。queue.c用来实现功能函数接口。test.c用来测试。


整个队列所需的头文件:

#include <stdio.h>
// assert 断言所需
#include <assert.h>
// malloc 所需
#include <stdlib.h>
// 布尔类型所需
#include <stdbool.h>


有了头文件之后,定义一个结构体,来表示每一个节点的结构:

// 队列的数据的类型
typedef int QDataType;
// 节点结构 
typedef struct QueueNode
{
  // 起连接作用的节点指针
  struct QueueNode* next;
  // 存放数据
  QDataType data;
}QNode;


上面说到,需要两个指针,一个指向链表的头,一个指向链表的尾,如果我们在测试的时候定义这两个指针,然后通过传递这两个指针来对链表进行操作,那未免非常的麻烦。并且,如果要改变这两个指针的指向,还需用到二级指针,这想想就可怕。因此,这里也用一个结构体对这两个指针进行封装,通过对这个结构体的操作,间接操控整个链表。定义如下:

// 队列结构
typedef struct Queue
{
  // QNode* 表示它是一个节点指针,head表示他是指向链表头的那个指针
  QNode* head;
  // QNode* 表示它是一个节点指针,tail表示它是指向链表尾的那个指针
  QNode* tail;
  // 统计队列的数据个数
  int size;
}Que; // typedef 重命名为 Que


  • 可以看到,上面这个结构体还多了一个size成员,它是用来统计队列的数据个数的,在判空,获取数据个数等函数接口里都要用到。
  • Que这个结构体,就可以看作一个队列,通过两个指针,对整个队列进行操作,所以每个函数接口的参数,都要包含Que结构体的指针参数:



3ccb03e87589445ab82c5f6941fa02f2.png


  • 一个队列的基本框架形成之后,接下来就要开始逐一实现队列的功能模块了。

所需功能函数接口的声明:

// 初始化队列
void QInit(Que* pq);
// 队列判空
bool QEmpty(Que* pq);
// 数据入队列
void QPush(Que* pq, QDataType x);
// 数据出队列
void QPop(Que* pq);
// 取队头数据
QDataType QFront(Que* pq);
// 取队尾数据
QDataType QBack(Que* pq);
// 获取队列中有效元素个数
int QSize(Que* pq);
// 销毁队列
void QDestroy(Que* pq);


  • 首先是对队列的初始化,简单来说,就是对一个Que结构体变量初始化,具体的操作:
Que q;  // 创建一个 Que 结构体变量
  QInit(&q);   // 对 q 调用初始化函数来初始化


  • 而初始化函数,就是将Que的结构体变量里边的两个指针置为空,size置为零。

相关函数接口实现:

// 初始化队列
void QInit(Que* pq)
{
  //  防止传递一个NULL过来
  assert(pq);
  // 初始化
  // pq为Que结构体指针,通过->操作符访问其成员
  pq->head = NULL;
  pq->tail = NULL;
  pq->size = 0;
}


队列的判空


  • 由于Que结构体里面含有一个size成员用来统计队列数据个数的,因此,队列的判空就很简单了,只需要判断一下size是不是0即可。


相关函数接口实现:

// 队列判空
bool QEmpty(Que* pq)
{
  // 防止pq为NULL
  assert(pq);
  // 如果size为0,说明判断为true,返回true
  return pq->size == 0;
}


数据入队列


  • 入队列简单来说就是插入数据,在队列的尾部插入数据,由于我们定义了一个指针指向队列的尾部,因此这里插入数据就显得很简单了。
  • 首先是使用malloc得到一个QNode节点,每次得到的节点都需要将其里面的next指针置为NULL,data存放所需数据。
  • 接着通过指向尾的指针将尾节点与新节点连接。如果此时队列为空,将两个指针都指向这个新节点即可。
  • 最后将size加一即可。
  • 注意,每次对尾指针进行操作后,都要更新一下尾指针。


相关函数接口实现:

// 数据入队列
void QPush(Que* pq, QDataType x)
{
  assert(pq);
  // 开辟一个节点
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  assert(newnode);
  newnode->data = x;
  newnode->next = NULL;
  // 如果此时队列为空,将两个指针指向这个新节点即可
  if (pq->size == 0) pq->head = pq->tail = newnode;
  else
  {
    // 连接
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
  // 入一个数据,size要加一
  pq->size++;
}


数据出队列


数据出队列就相当于头删,由于我们定义了一个指针指向队列的头,因此这里也是很好操作的。


我们先要存放头节点的下一个节点的地址,然后再将头节点删除,最后指向头节点的指针更新一下即可。


如果此时队列为空,就不能删了,直接assert暴打。


如果此时队列只有一个元素,删除过后,指向队列头的那个指针此时指向NULL,而那个指向队列尾的指针还指向刚才被删的节点的位置,因此,为了以防万一(防止通过该指针继续使用那个被删的节点),这里需要将指向队列尾的那个指针置为NULL。


当然最后记得size要减一。


相关函数接口实现:

// 数据出队列 
void QPop(Que* pq)
{
  // 需要判空
  assert(pq && !QEmpty(pq));
  // 这是只有一个节点的操作
  if (pq->head == pq->tail)
  {
    free(pq->head);
    pq->head = NULL;
    pq->tail = NULL;
  }
  else
  {
    // 正常删除
    QNode* tmp = pq->head->next;
    free(pq->head);
    pq->head = tmp;
  }
  // 删除完后size要减一
  pq->size--;
}


取队头数据


  • 取队头数据就是第一个节点的数据,我们通过指向队头的指针可以直接拿出数据。
  • 注意,如果队列为空,就不能取数据。


相关函数接口实现:

// 取队头数据
QDataType QFront(Que* pq)
{
  assert(pq && !QEmpty(pq));
  // 直接返回队头的数据
  return pq->head->data;
}


取队尾数据


  • 这里通过指向队尾的指针也可以直接获取队尾数据。
  • 注意,队列不能为空。

相关函数接口实现:

// 取队尾数据
QDataType QBack(Que* pq)
{
  assert(pq && !QEmpty(pq));
  return pq->tail->data;
}


数据的个数


  • 由于我们再Que结构体里定义了一个size来统计队列的数据个数,因此这里直接返回这个size即可。

相关函数接口实现:

// 获取队列中有效元素个数
int QSize(Que* pq)
{
  assert(pq);
  return pq->size;
}


队列的销毁


  • 队列的销毁需要我们将每一个节点依次释放,因此,我们只需要运用指向头节点的指针遍历一遍队列,一边遍历一边删除即可。
  • 当然最后需要将操作队列的两个指针都指向NULLsize也要置为0

相关函数接口实现:

// 队列销毁
void QDestroy(Que* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  // 遍历队列(链表)
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  // 最后操作
  pq->head = NULL;
  pq->tail = NULL;
  pq->size = 0;
}


整体的代码

queue.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
// 队列的数据的类型
typedef int QDataType;
// 节点结构 
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QNode;
// 队列结构
typedef struct Queue
{
  QNode* head;
  QNode* tail;
  int size;
}Que;
// 初始化队列
void QInit(Que* pq);
// 销毁队列
void QDestroy(Que* pq);
// 数据入队列
void QPush(Que* pq, QDataType x);
// 数据出队列
void QPop(Que* pq);
// 获取队列中有效元素个数
int QSize(Que* pq);
// 队列判空
bool QEmpty(Que* pq);
// 取队头数据
QDataType QFront(Que* pq);
// 取队尾数据
QDataType QBack(Que* pq);


queue.c

#include "queue.h"
// 初始化队列
void QInit(Que* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
  pq->size = 0;
}
// 队列销毁
void QDestroy(Que* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = NULL;
  pq->tail = NULL;
  pq->size = 0;
}
// 数据入队列
void QPush(Que* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  assert(newnode);
  newnode->data = x;
  newnode->next = NULL;
  if (pq->size == 0) pq->head = pq->tail = newnode;
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
  pq->size++;
}
// 数据出队列 
void QPop(Que* pq)
{
  assert(pq && !QEmpty(pq));
  if (pq->head == pq->tail)
  {
    free(pq->head);
    pq->head = NULL;
    pq->tail = NULL;
  }
  else
  {
    QNode* tmp = pq->head->next;
    free(pq->head);
    pq->head = tmp;
  }
  pq->size--;
}
// 获取队列中有效元素个数
int QSize(Que* pq)
{
  assert(pq);
  return pq->size;
}
// 队列判空
bool QEmpty(Que* pq)
{
  assert(pq);
  return pq->size == 0;
}
// 取队头数据
QDataType QFront(Que* pq)
{
  assert(pq && !QEmpty(pq));
  return pq->head->data;
}
// 取队尾数据
QDataType QBack(Que* pq)
{
  assert(pq && !QEmpty(pq));
  return pq->tail->data;
}


test.c

#include "queue.h"
void test()
{
  Que q;
  QInit(&q);
  QPush(&q, 1);
  printf("%d %d %d\n", q.size, QBack(&q), QFront(&q));
  QPush(&q, 2);
  printf("%d %d %d\n", q.size, QBack(&q), QFront(&q));
  QPush(&q, 3);
  printf("%d %d %d\n", q.size, QBack(&q), QFront(&q));
  QPush(&q, 4);
  printf("%d %d %d\n", q.size, QBack(&q), QFront(&q));
  QPush(&q, 5);
  printf("%d %d %d\n", q.size, QBack(&q), QFront(&q));
  printf("%d\n", QSize(&q));
  while (!QEmpty(&q))
  {
    printf("%d ", QFront(&q));
    QPop(&q);
  }
  printf("\n");
  printf("%d\n", q.size);
  QDestroy(&q);
}
int main()
{
  test();
  return 0;
}


🤪写在最后


💝队列还是比较简单呢,只要能够实现前面的数据结构,队列也可以说是洒洒水嘞。

❤️‍🔥后续将会持续输出有关数据结构的文章,你们的支持就是我写作的最大动力!


感谢阅读本小白的博客,错误的地方请严厉指出噢~

相关文章
|
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月前
【初阶数据结构】深入解析队列:探索底层逻辑
【初阶数据结构】深入解析队列:探索底层逻辑