【数据结构】队列的实现

简介: 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)的特点。

本篇总结队列是如何实现的,以及各方面的细节问题,比较链表与队列之间的不同,注意到不同的类型,要按照不同需求来定义结构,不能一成不变,印象刻板。


【队列】


⏰.队列的概念及结构


队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)的特点。


入队列:进行插入操作的一端叫做队尾


出队列:进行删除操作的一端叫队头


c63da82e7d8f4288ae1a11ff98267d43.png


⏰.队列的实现


队列可以用数组和链表来实现。但使用链表的结构更优一些,因为如果使用数组结构,删除数据需要挪动大量数据,效率比较低。


f2821d83b3fb47a58770336477ac4493.png


队列我们使用链表来实现


首先使用链表定义一个结点


我们都知道结点是由一个结构体定义的,这个给结构体里有个指向下一个结点地址的next和数据data。


但想一下,队列需要对链表进行尾删,也就是每次都要找到尾结点,将链表的头结点和尾结点传给出队列函数,然后进行出队列操作,这样传参数就传好几个,不如让我们将头结点的地址和尾结点的地址分装成一个新的结构体


想一想为什么这里要给个尾指针过去呢?


如果在实现单链表操作中也给尾指针呢?


单链表中给尾指针能完成操作吗?尾插操作需要尾指针,这个操作可以完成,但尾删呢?尾删操作你给个尾指针就能完成吗?当然不能,还需要尾指针前面的结点地址。传个尾指针过去只能完成部分操作,不能完成全部操作还不如不传,代码挫的一批。


但这里不一样,这里队列有它自己的规则:那就是只在一端进行入队,那就是队尾,也就是说在队尾只进行尾插,不进行尾删,所以这里传尾指针过去是可以完成队列所需要的操作的,


要区别单链表中只传一个头指针,而队列这里要传头指针和尾指针的不同,我们要按照需要来定义不同结构。


#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDatatype;
typedef struct QNode//定义结点结构
{
  struct QNode* next;
  QDatatype data;
}QNode;
typedef struct Queue//将头指针和尾指针分装起来,传给队列操作函数
{
  QNode* head;//链表头指针
  QNode* tail;//链表尾指针
  int size;//大小想一想传过去有什么好处?
}Queue;
//初始化队列
void  QueueInit(Queue* pq);
//销毁队列
void  QueueDestroy(Queue* pq);
//队尾入队列
void  QueuePush(Queue* pq,QDatatype x);
//队头出队列
void  QueuePop(Queue* pq);
//获取队列的有效数据的大小
void  QueueSize(Queue* pq);
//判断队列是否为空,如果为空返回非0,如果为非空返回0
bool  QueueEmpty(Queue* pq);
//获取队列头部元素
QDatatype  QueueFront(Queue* pq);
//获取队尾元素
QDatatype  QueueBack(Queue* pq);


🕐1.初始化队列


首先对传入的数据进行初始化,我们知道传过来的是个分装好的结构体,里面有链表头指针,尾指针,大小。


所以一开始我们需要将头指针尾指针和大小都置0;


//初始化队列
void  QueueInit(Queue* pq)
{
  assert(pq);//首先断言判断是否传错
  pq->head = pq->tail = NULL;
  pq->size = 0;
}


🕑2.队尾入队列


队尾入队列,实际上就是链表的尾插。


而这正是这操作我们将链表的尾指针也传过去,就是为了每次尾插不需要找尾,每次插入时更新下尾指针位置即可。


//入队列
void  QueuePush(Queue* pq, QDatatype x)
{
  assert(pq);//断言是否传错
  //入队,就是尾插一个结点,首先生成一个新结点
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  newnode->next = NULL;//需要置空,不然会出现野指针
  newnode->data = x;//将数据赋值
  if (newnode == NULL)//判断是否开辟成功
  {
    perror("malloc");
  }
  //因为为单链表,不带哨兵头,所以一开始head和tail都为空,第一步直接将结点赋值过去,然后后面才是真正的尾插
  if (pq->head == NULL)
  {
    pq->head = pq->tail = newnode;//将结点赋值过去
  }
  else
  {
    //尾插
    pq->tail->next = newnode;
    pq->tail = newnode;//找尾--更新
  }
  pq->size++;//插入一个数据size就要++
}


🕒3.队头出队列


对头出队列,本质上就是链表的头删,头删就是让头指针不断改变,然后让头指针前面的结点释放。


注意点1:


在删除数据之前我们都要对队列进行检查,看是否队列为空。


注意点2:要注意tail是指向最后一个结点的指针。


当head指向最后一个结点后释放,那么tail指向的空间被释放,那tail就变成野指针了,所以最后需要将tail置NULL。


有两中方式:


第一种:只管头删,最后再将tail置NULL

第二种:一开始就考虑二种情况,最后一个结点之前,和最后一个结点,即分为一个结点和多个结点。


//出队列
void  QueuePop(Queue* pq)
{
  assert(pq);
  //在删除数据之前需要考虑队列是否为空;
  assert(!pq->head==NULL);
    QNode* next = pq->head->next;//记录头结点后面的结点
    free(pq->head);//是否头节点
    pq->head = next;//将头指针重新指向后面的结点
    //注意如果最后head和tail指向同一个结点,也就是最后一个结点时,tail会变成野指针。
  //方法1:
  if (pq->head == NULL)
  {
    pq->tail = NULL;
  }
  pq->size--;
}


方法2:


void  QueuePop(Queue* pq)
{
  assert(pq);
  //在删除数据之前需要考虑队列是否为空;
  assert(!pq->head==NULL);
    //注意如果最后head和tail指向同一个结点,也就是最后一个结点时,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;//将头指针重新指向后面的结点
  }
    pq->size--;
}


🕓4.获取队列头部元素


获取队头数据,就直接将头结点的数据拿走即可,不过在拿之前需要进行判断队列是否为空,如果为空,那还拿什么


//获取队头数据
QDatatype  QueueFront(Queue* pq)
{
  assert(pq);//断言判断是否传错
  assert(!QueueEmpty(pq));//判断是否为空
  return pq->head->data;//队头数据
}


🕔5.获取队列尾元素


和获取队头数据一样需要判断队列是否为空


//获取队尾数据
QDatatype  QueueBack(Queue* pq)
{
  assert(pq);//断言判断是否传错
  assert(!QueueEmpty(pq));//判断是否为空
  return pq->tail->data;//队尾数据
}


🕕6.获取队列中有效元素的个数


看,最开始的问题即将揭晓,在分装的结构体中加上size的作用是什么?


加上size后我们就可以快速获取队列中有效元素的个数了,如果没有加上,要获取个数,那必须对链表进行遍历,时间复杂度就是O(N),而现在就是O(1)。同样在单链表中我们如果想快速获得链表中有效数据的个数,也可以将节点与size分装成一新的结构体。那样就可以啦。


有的人想在带有哨兵头的链表中快速获取个数的办法是将size放入哨兵头里,想着反正哨兵头也不存储数据,就想着将size放进去,但是可以吗?


当然不可以,我们定义的链表中数据的类型有时是知道的,有时是不知道的,当数据类型是int类型是哨兵头里面可以放size,但当链表使用的数据类型是char? double 类型时,你放进去一个int类型的size进去?可以吗?


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


🕖7.检查队列是否为空


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


🕗8.销毁队列


与头删类似,就是循环删除。当删除为空时,停止


然后将数据都置0


//销毁队列
void  QueueDestroy(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  //保存下一个释放,保存下一个释放
  pq->head = pq->tail = NULL;
  pq->size = 0;
}


相关文章
|
4月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
393 9
|
2月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
160 77
|
11天前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
26 11
|
24天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
2月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
54 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
2月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
52 9
|
2月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
48 7
|
4月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
107 5
|
4月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
5月前
初步认识栈和队列
初步认识栈和队列
79 10