DS:链式结构实现队列

简介: DS:链式结构实现队列

                                        创作不易,友友们来个三连支持吧!

一、队列的概念

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

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

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

二、单链表实现队列

      队列可以用数组实现,也可以用链表实现,但是链表会稍微优势一点,因为涉及到出队列的时候是在队列头出的,如果是数组实现的话,需要把后面所有数据都往前挪一位,效率会相对低一点,所以以下博主会优先讲解单链表实现队列,数组实现队列会在下一篇博客中进行讲解。

2.1 相关结构体的创建

      因为使用单链表的方式去实现队列,所以我们应该构造一个节点指针结构体

typedef int QDatatype;//方便后面修改存储数据的数据类型
typedef struct QueueNode//队列结点的数据结构
{
  QDatatype data;//存储数据
  struct QueueNode* next;
}QNode;

      但是这远远不够,因为我们只是使用单链表的方式去实现队列,并不代表可以完全照抄单链表的模式,由于队列队头出数据和队尾入数据的特性,我们需要构造两个节点结构体指针,一个指向队列头,一个指向队列尾,这样我们可以再封装一个队列结构体。

typedef struct Queue
{
  QNode* phead;//指向队头,用于出队(头删)
  QNode* ptail;//指向队尾,用于入队(尾插)
  int size;//记录有效元素个数
}Queue;//创建一个队列相关结构体

2.1.1 为什么这里要构造两个结构体,构造一个不行吗??

写一个其实也是可以的,比如:

typedef int QDatatype;//方便后面修改存储数据的数据类型
typedef struct QueueNode//队列结点的数据结构
{
  QDatatype data;//存储数据
  struct QueueNode* next,*phead,*ptail;
    int size;
}QNode;

这种写法不仅在使用上有很大的劣势,而且不易和单链表区分开来,原因如下:

1、队列的管理更加严格,单链表的管理更加松散。

       单链表可以实现尾插、头插、指定位置插入、尾删、头删、指定位置删除……管理上很松散,而队列由于其一端进,一端出的特点,不能随意的去遍历,所以我们才会需要存储队列头和队列尾的结构体节点指针,方便我们进行入队和出队的操作,同时我们需要队列头和队列尾能对所有节点起到一个管理作用(即操作队列需要经过队列头或者队列尾的同意),严格管理,而构造两个结构体就能体现出这种作用,相当于用第二个结构体中的phead和ptail去管理第一个结构体中的next和data。在写代码的时候,可以体现出来

     也就是说pq想指向链表的元素只能通过phead和ptail去指向,不能越级,一越级就会报错,总来来说就像是一级一级去管理链队,pq管理phead和ptail,而phead和ptail管理data和next

2、方便参数的传递。

     调用函数会方便很多,比如不构造两个结构体的话,那么调用函数就需要传两个参数,即phead和ptail,但如果有一个结构体Queue将phead和ptail指针封装起来了,那么只要传一个参数就可以了,通过访问这个参数的成员就可以找到这两个指针了。

3、不需要使用二级指针了

     以往我们在单链表的实现中,使用的是二级指针,因为单链表中的phead就是结构体指针类型,而单链表的头删以及头插都需要改变phead,所以我们需要传的是该结构体指针的地址,也就是需要用二级指针来接受,但是在这里我们实现队列时又多封装了一个Queue的结构体,虽然我们有些时候也需要改变phead和ptail,但是这两个结构体指针都是Quene的成员,所以我们只需要取Quene结构体的地址即可,只需要一级指针就可以接受了!!

2、为什么我要在队列结构体里设置一个size,不设置可以吗??

   其实不设置size也是可以的,有些书上也没有设置size,我设置size也是考虑到2个原因:

1、栈有结构体成员top,而队列没有

栈中的top其实跟顺序表中的有效数据个数基本上差异不大,虽然名字是不一样的,但是通过top是可以得到栈的有效数据个数的,而队列是没有的。

2、队列管理较为严格,不能随便遍历

   首先,队列并不具备栈那样和size类似的成员,并且由于队列只能队头出列队尾入列,不能随意去遍历,如果要遍历需要边出队列才能边遍历,代价比较大,所以我们给了一个size,帮助我们在入队列和出队列的时候及时修改存储的size成员,这样可以方便我们获得队列中有效数据的个数

2.2 初始化队列

void QueueInit(Queue* pq)
{
  assert(pq);//判断传的是不是空指针
  pq->phead = pq->ptail = NULL;
  pq->size = 0;//因为队列不像栈一样,有一个top表示栈顶元素的下标
  //所以如果我们想知道这个队列的有效数据个数,就必须遍历队列
  //由于其先进先出的特性,我们默认只能访问到头元素和尾元素
  //所以必须访问一个头元素,就出队列一次,这样才能实现遍历
  //但是这样的代价太大了,为了方便,我们直接用size
}

2.3 队尾入队列

void QueuePush(Queue* pq, QDatatype x)
{
  assert(pq);
    //入队必须从队尾入!
  QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建一个新节点
  if (newnode==NULL)//如果新节点申请失败,退出程序
  {
    perror("malloc fail");
  }
  //新节点创建成功,给新节点初始化一下
  newnode->data = x;
  newnode->next = NULL;
  //开始入队
  //如果直接尾插的话,由于会用到ptail->next,所以得考虑队列为空的情况
  if (pq->ptail== NULL)//如果为空,直接把让新节点成为phead和ptail
  {
    //按道理来说,如果ptail为空,phead也应该为空
    // 但是有可能会因为我们的误操作使得phead不为空,这个时候一般是我们写错的问题
    //所以使用assert来判断一下,有问题的话会及时返回错误信息
    assert(pq->phead == NULL);
    pq->phead = pq->ptail = newnode;
  }
  else//尾插
  {
    pq->ptail->next = newnode;
    pq->ptail = newnode;
  }
  pq->size++;
}

2.3.1 为什么不单独封装一个扩容函数?

      因为队列并不像链表一样,链表的头插、尾插、指定位置插入都需要创建新节点,如果设置一个扩容函数的话复用性很高,而队列只有在队尾入数据需要创建新节点,只会用到一次,所以没有必要去封装一个这样的函数。

2.3.2 如何思考边界情况

     进行尾插的时候,我们先不考虑边界情况去做一遍,比如上述代码的else部分就是实现尾插,而我们观察发现尾插的过程中需要用到ptail的成员next的指针,所以ptail必须不能是NULL,因此要分开讨论ptail为NULL的情况

2.3.3 为什么assert(pq->phead == NULL)

    因为我们考虑ptail为空的时候,不能用成员next,但是因为按道理来说一般情况下,ptail如果是NULL,phead肯定也是NULL,没必要单独搞这一出,但是这里也有可能我们前面操作有失误,phead不是NULL,这边的assert就是为了避免我们代码写错的情况,万一写错了,可以帮我们更快找出bug

2.4 队头出队列

void QueuePop(Queue* pq)
{
  assert(pq);
  //如果队列为空,没有删除的必要
  assert(!QueueEmpty(pq));
  //队列中的出队列相当于链表的头删
  //如果直接头删,那么如果队列只有一个有效数据的话,那么我们将phead的空间释放掉,但是没有将ptail给置空
  //这样会导致ptail成为一个野指针,所以我们需要考虑只有一个节点多个节点的情况
  if (pq->phead->next == NULL)//一个节点的情况,直接将这个节点释放并置空即可
  {
    free(pq->phead);
    pq->phead = pq->ptail = NULL;//置空,防止野指针
  }
  else//多个节点的情况,直接头删
  {
    QNode* next = pq->phead->next;//临时指针记住下一个节点
    free(pq->phead);
    pq->phead = next;//让下一个节点成为新的头
  }
  pq->size--;
}

2.4.1 如何思考边界情况

       进行头删的时候,我们先不考虑边界情况去做一遍,比如上述代码的else部分就是实现头删,其实一开始发现不了什么问题,因为我们assert已经判断了,此时链表肯定不是空,而有一个节点的时候,phead的next指向NULL也很合理,不会有问题,但是我们要考虑到虽然我们释放了phead的空间,但是我们只给phead置NULL,而没有给ptail置NULL,这样ptail就变成一个野指针了!!

2.5 获取队列头部元素

QDatatype QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));//队列如果为空,则不可能找得到队列头元素
  //队列不为空的时候,直接返回phead指向的数据
  return pq->phead->data;
}

2.6 获取队列队尾元素

QDatatype QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));//队列如果为空,则不可能找得到队尾元素
  //队列不为空的时候,直接返回ptail指向的数据
  return pq->ptail->data;
}

2.7 获取队列中有效元素个数

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

    在这个函数可以充分体现处我们构造一个size成员的好处,代码量很小,如果我们用size成员的话,那么需要遍历队列,会很麻烦。

2.8 检测队列是否为空

bool QueueEmpty(Queue* pq)//链表为空的情况,可以根据容量,也可以根据ptail==NULL&&phead==NULL
{
  assert(pq);
  return pq->ptail == NULL && pq->phead == NULL;//也可以pq->size==0
}

    因为我们设置了一个size成员,其实用size成员也是可以的,通过判断是否等于0的返回值真假来决定是否是空,这边两张写法没啥区别,只要前面的没有出错就行。

2.9 销毁队列

void QueueDestory(Queue* pq)
{
  assert(pq);//判断传的是不是空指针
  //要逐个节点释放
  QNode* pcur = pq->phead;
  while (pcur)
  {
    QNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
}

和单链表差不多,逐个节点释放就行。

2.10 遍历打印队列

其实严格意义来说队列是不适合被打印的,因为打印需要遍历队列,而由于队列一端进一端出的特点,要遍历里面的元素就需要一边在队列头获取元素,一般在队列头出队列,知道队列为空才能访问完所有数据,而且这样做会导致队列的数据丢失,没有复用性,因此也不适合封装这个函数,这里只是告诉大家别忘记了队列访问的特点,不要跟单链表一样,队列的管理是很严格的。一般我们只会在main函数中测试一下

#include"Queue.h"
int main()
{
  Queue q;
  QueueInit(&q);//初始化
  QueuePush(&q, 1);//入队列
  QueuePush(&q, 2);//入队列
  QueuePush(&q, 3);//入队列
  QueuePush(&q, 4);//入队列
  while (!QueueEmpty(&q))//遍历打印队列
  {
    printf("%d ", QueueFront(&q));
    QueuePop(&q);
  }
}

三、链队列实现的全部代码

3.1 Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDatatype;//方便后面修改存储数据的数据类型
typedef struct QueueNode//队列结点的数据结构
{
  QDatatype data;//存储数据
  struct QueueNode* next;
}QNode;
typedef struct Queue
{
  QNode* phead;//指向队头,用于出队(头删)
  QNode* ptail;//指向队尾,用于入队(尾插)
  int size;//记录有效元素个数
}Queue;//创建一个队列相关结构体
void QueueInit(Queue* pq);//队列的初始化
void QueuePush(Queue* pq, QDatatype x);//队列的入队(尾插)
void QueuePop(Queue* pq);//队列的出队(头删)
QDatatype QueueFront(Queue* pq);//获取队列头部元素
QDatatype QueueBack(Queue* pq);//获取队列尾部元素
int QueueSize(Queue* pq);//获取队列中有效元素个数
bool QueueEmpty(Queue* pq);//判断队列是否为空
void QueueDestory(Queue* pq);//队列的销毁

3.2 Queue.c

#include"Queue.h"
void QueueInit(Queue* pq)
{
  assert(pq);//判断传的是不是空指针
  pq->phead = pq->ptail = NULL;
  pq->size = 0;//因为队列不像栈一样,有一个top表示栈顶元素的下标
  //所以如果我们想知道这个队列的有效数据个数,就必须遍历队列
  //由于其先进先出的特性,我们默认只能访问到头元素和尾元素
  //所以必须访问一个头元素,就出队列一次,这样才能实现遍历
  //但是这样的代价太大了,为了方便,我们直接用size
}
void QueuePush(Queue* pq, QDatatype x)
{
  assert(pq);
    //入队必须从队尾入!
  QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建一个新节点
  if (newnode==NULL)//如果新节点申请失败,退出程序
  {
    perror("malloc fail");
  }
  //新节点创建成功,给新节点初始化一下
  newnode->data = x;
  newnode->next = NULL;
  //开始入队
  //如果直接尾插的话,由于会用到ptail->next,所以得考虑队列为空的情况
  if (pq->ptail== NULL)//如果为空,直接把让新节点成为phead和ptail
  {
    //按道理来说,如果ptail为空,phead也应该为空
    // 但是有可能会因为我们的误操作使得phead不为空,这个时候一般是我们写错的问题
    //所以使用assert来判断一下,有问题的话会及时返回错误信息
    assert(pq->phead == NULL);
    pq->phead = pq->ptail = newnode;
  }
  else
  {
    pq->ptail->next = newnode;
    pq->ptail = newnode;
  }
  pq->size++;
}
void QueuePop(Queue* pq)
{
  assert(pq);
  //如果队列为空,没有删除的必要
  assert(!QueueEmpty(pq));
  //队列中的出队列相当于链表的头删
  //如果直接头删,那么如果队列只有一个有效数据的话,那么我们将phead的空间释放掉,但是没有将ptail给置空
  //这样会导致ptail成为一个野指针,所以我们需要考虑只有一个节点多个节点的情况
  if (pq->phead->next == NULL)//一个节点的情况,直接将这个节点释放并置空即可
  {
    free(pq->phead);
    pq->phead = pq->ptail = NULL;//置空,防止野指针
  }
  else//多个节点的情况,直接头删
  {
    QNode* next = pq->phead->next;//临时指针记住下一个节点
    free(pq->phead);
    pq->phead = next;//让下一个节点成为新的头
  }
  pq->size--;
}
QDatatype QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));//队列如果为空,则不可能找得到队列头元素
  //队列不为空的时候,直接返回phead指向的数据
  return pq->phead->data;
}
QDatatype QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));//队列如果为空,则不可能找得到队尾元素
  //队列不为空的时候,直接返回ptail指向的数据
  return pq->ptail->data;
}
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}
bool QueueEmpty(Queue* pq)//链表为空的情况,可以根据容量,也可以根据ptail==NULL&&phead==NULL
{
  assert(pq);
  return pq->ptail == NULL && pq->phead == NULL;
}
void QueueDestory(Queue* pq)
{
  assert(pq);//判断传的是不是空指针
  //要逐个节点释放
  QNode* pcur = pq->phead;
  while (pcur)
  {
    QNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
}

3.3 test.c (测试)

#include"Queue.h"
int main()
{
  Queue q;
  QueueInit(&q);//初始化
  QueuePush(&q, 1);//入队列
  QueuePush(&q, 2);//入队列
  QueuePush(&q, 3);//入队列
  QueuePush(&q, 4);//入队列
  while (!QueueEmpty(&q))//遍历打印队列
  {
    printf("%d ", QueueFront(&q));
    QueuePop(&q);
  }
}

四、队列在实际生活中的作用举例——抽号机

    在生活中,我们经常需要排队,比如在饭堂打饭时,排在前面的因为来得早可以先打到饭,而排在后面的因为来得晚就得后打到饭,这符合我们追求公平的原则(先到先得),这本身也是维持秩序的一种方式。

     排队和队列是一样的原则,先到先得对应的就是队列的先进先出,但是哪怕大家知道这样的原则,但也有可能有人去钻空子,比如:

1、打饭的时候帮室友打饭或者帮室友(女朋友)占位置。

2、趁着人多的时候找一个地方偷偷插队

3、或者一些比较恶霸型的,可能直接插队也没人敢说

4、再或者,你并不是有意插队,只不过由于顾客太多,商家忘记了顺序,误把你排在了别人前面

所以商家为了控制这个局面,使用了抽号机

比如说,第一个同学来了,通过抽号机,拿到了1号,那么领取物品的时候,商家就按照这个序号的优先级来给予服务,避免了一些人钻空子的可能,同时为了避免有的人帮别人占位置,强制要求刷脸抽号。

抽号机的本质就是队列,比如来了一个顾客,抽号机内部就入队列一次,服务完了这个顾客,抽号机内部就出队列一次,而如果我们还想让顾客知道自己前面有多少人,就需要有一个size来统计目前有效数据的个数。

当我们有多个窗口去服务的时候,我们也可以通过抽号机这个平台来叫号,避免现场混乱,比如说目前下一个轮到3号顾客了,那么A窗口一旦空出来,就会让3号顾客过去,而如果B窗口接着空出来了,就喊4号顾客过去,这使得本来混乱的排队场面变得有序了,顾客不需要排在拥挤的收货台前,抽完号码等着叫号就行了,如果你觉得你前面的人有点多,也可以自己转身就走。

相关文章
|
7月前
|
算法 Java 程序员
【算法训练-队列 一】【结构特性】用两个栈实现队列
【算法训练-队列 一】【结构特性】用两个栈实现队列
63 0
|
7月前
|
消息中间件 监控 Go
合并队列的例子
【5月更文挑战第14天】文中探讨了如何跨线程或机器合并两个有序任务队列, 利用队列有序性优化合并效率。任务队列用于工作单元调度,通过消息代理在客户端和工作进程间通信,实现高可用和可扩展系统。队列功能包括监控、调度、工作流程、资源保护、时间和速率限制以及组件定制。合并操作的时间复杂度在最好情况下为O(N),最坏情况为O(N²),其中N为较短队列的长度。
245 0
合并队列的例子
|
6月前
|
存储 算法
数据结构和算法学习记录——特殊线性表之队列-队列的概念、队列结构体类型定义 、基本接口函数、初始化函数、销毁队列函数、入队列函数、判断队列是否为空、出队列函数、读取队头队尾的数据 、计算队列数据个数
数据结构和算法学习记录——特殊线性表之队列-队列的概念、队列结构体类型定义 、基本接口函数、初始化函数、销毁队列函数、入队列函数、判断队列是否为空、出队列函数、读取队头队尾的数据 、计算队列数据个数
42 0
|
7月前
|
机器学习/深度学习 存储
DS:二叉树的链式结构及实现
DS:二叉树的链式结构及实现
|
7月前
DS:栈和队列的相互实现
DS:栈和队列的相互实现
|
测试技术
L2-022 重排链表 (25 分)(map+结构体模拟)
L2-022 重排链表 (25 分)(map+结构体模拟)
69 0
L2-022 重排链表 (25 分)(map+结构体模拟)
|
存储 人工智能 Java
第一个动态结构:链表
大家好,我是王有志。今天我们一起学习线性表中的第二种数据结构:链表,也是真正意义上的第一个动态数据结构。
118 0
第一个动态结构:链表
|
存储
队列的定义及基本操作实现(链式)
队列的定义及基本操作实现(链式)
156 0
|
存储
大话数据结构--初始队列
大话数据结构--初始队列
86 0
|
存储 JavaScript 索引
基础数据结构(二):队列结构 Queue(TS版)
基础数据结构(二):队列结构 Queue(TS版)
基础数据结构(二):队列结构 Queue(TS版)