【初阶数据结构篇】队列的实现(赋源码)

简介: 首先队列和栈一样,不能进行遍历和随机访问,必须将队头出数据才能访问下一个,这样遍历求个数是不规范的。


队列


1 代码位置

gitee


2 概念与结构


1.1概念


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


⼊队列:进⾏插⼊操作的⼀端称为队尾


出队列:进⾏删除操作的⼀端称为队头



1.2结构


队列也可以数组和链表的结构实现,使⽤链表的结构实现更优⼀些,因为如果使⽤数组的结构,出队列在数组头上出数据,效率会⽐较低。


**数组头删时间复杂度:O(N) ** 数组尾插时间复杂度:O(1)

单链表头删时间复杂度:O(1) 单链表尾插时间复杂度:O(N)


  • 乍一看二者难分伯仲,但如果我们在单链表的结构里再定义一个指向尾结点的指针,那么单链表就可以实现O(1)的尾插时间复杂度,而数组没有什么特别好的办法实现这种转变。


2 队列的实现


Queue.h


#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDataType;
typedef struct QueueNode//队列节点的结构,即单链表节点的结构
{
  QDataType data;
  struct QueueNode* next;
}QNode;
typedef struct Queue//队列的结构,定义指向队列头尾的指针,以及队列节点的个数
{
  QNode* phead;
  QNode* ptail;
  QDataType size;
}Q;

void QueueInit(Q*);

//入队列,队尾
void QueuePush(Q*, QDataType);

//出队列,队头
void QueuePop(Q*);

//队列判空
bool QueueEmpty(Q*);

//取队头数据
QDataType QueueFront(Q*);

//取队尾数据
QDataType QueueBack(Q*);

//队列有效元素个数
int QueueSize(Q*);

void QueueDestroy(Q*);

test.c


  • 用来测试我们写的函数(函数的调用)
  • 这一部分就是自己写的时候用的测试用例,随便什么都行


最好是写一个方法测试一次,不然找错误的时候会很痛苦😜

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void QueueTest01()
{
  Q q;//定义队列
  QueueInit(&q);
  QueuePush(&q, 1);
  QueuePush(&q, 2);
  QueuePush(&q, 3);
  QueuePush(&q, 4);
  ///
  printf("head:%d\n", QueueFront(&q));
  printf("tail:%d\n", QueueBack(&q));
  printf("size:%d\n", QueueSize(&q));
  QueuePop(&q);
  QueueDestroy(&q);
}

int main()
{
  QueueTest01();
  return 0;
}

Queue.c


函数方法的实现,重点重点!!!


在每一个方法的第一排都使用assert宏来判断形参是否为空(避免使用时传入空指针,后续解引用都会报错)


2.1 队列的初始化和销毁


2.1.1 初始化


前面提到,我们在定义队列时,一个结构体用来定义队列,其中有指向队列头尾的指针(其中还有一个size,用来保存链表长度,后面会讲到为什么),另一个就是队列结点的结构,和单链表一样


#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void QueueInit(Q* pq)
{
  assert(pq);
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
}
  • 和单链表一样,初始化只需让指向队列的指针置为空即可,只不过这里多了一个尾指针,同时队列为空,size=0
  • 链表空间都是按需申请,所以入数据都是通过之后的插入方法一个一个实现的

2.1.2 销毁
void QueueDestroy(Q* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  QNode* pcur = pq->phead;
  while (pcur)
  {
    QNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
}

同单链表


2.2 队列插入和删除数据

2.2.1 队尾插入数据(入队列)


同样的我们先写一个申请结点空间的函数


QNode* BuyNode(QDataType x)
{
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail!");
    exit(1);
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}
  • 根据链表是否为空分两种情况
  • 别忘了size++
void QueuePush(Q* pq, QDataType x)
{
  assert(pq);
  if (pq->phead == NULL)
    pq->phead = pq->ptail = BuyNode(x);
  else
  {
    pq->ptail->next = BuyNode(x);
    pq->ptail = pq->ptail->next;
  }
  pq->size++;
}
2.2.2 队头删除数据(出队列)


删除数据的时候一定要判断队列是否为空!(也可以通过size来判断)

bool QueueEmpty(Q* pq)
{
  assert(pq);
  return pq->phead == NULL && pq->ptail == NULL;
}
  • 根据队列结点个数是否大于一个分两种情况讨论
  • 别忘了size–
void QueuePop(Q* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));

  //只有一个节点的情况,避免ptail变成野指针
  if (pq->ptail == pq->phead)
  {
    free(pq->phead);
    pq->phead = pq->ptail = NULL;
  }
  else
  {
    QNode* next = pq->phead->next;
    free(pq->phead);
    pq->phead = next;
  }
  pq->size--;
}

2.3 返回队头/队尾数据

QDataType QueueFront(Q* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->phead->data;
}

QDataType QueueBack(Q* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->ptail->data;
}

2.4 返回队列的有效数据个数


  • size作用
  • 首先队列和栈一样,不能进行遍历和随机访问,必须将队头出数据才能访问下一个,这样遍历求个数是不规范的
  • 其次时间复杂度O(N),程序效率低


所以我们在队列结构里多定义了一个size,很好地解决了这个问题

int QueueSize(Q* pq)
{
  assert(pq);

  //不规范且时间复杂度O(n)
  //int size = 0;
  //QNode* pcur = pq->phead;
  //while (pcur)
  //{
  //  size++;
  //  pcur = pcur->next;
  //}
  //return size;


  return pq->size;

}

Queue.c(完整版)

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void QueueInit(Q* pq)
{
  assert(pq);
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
}


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


void QueuePush(Q* pq, QDataType x)
{
  assert(pq);
  if (pq->phead == NULL)
    pq->phead = pq->ptail = BuyNode(x);
  else
  {
    pq->ptail->next = BuyNode(x);
    pq->ptail = pq->ptail->next;
  }
  pq->size++;
}



bool QueueEmpty(Q* pq)
{
  assert(pq);
  return pq->phead == NULL && pq->ptail == NULL;
}
void QueuePop(Q* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));

  //只有一个节点的情况,避免ptail变成野指针
  if (pq->ptail == pq->phead)
  {
    free(pq->phead);
    pq->phead = pq->ptail = NULL;
  }
  else
  {
    QNode* next = pq->phead->next;
    free(pq->phead);
    pq->phead = next;
  }
  pq->size--;
}



QDataType QueueFront(Q* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->phead->data;
}


QDataType QueueBack(Q* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->ptail->data;
}


int QueueSize(Q* pq)
{
  assert(pq);

  //不规范且时间复杂度O(n)
  //int size = 0;
  //QNode* pcur = pq->phead;
  //while (pcur)
  //{
  //  size++;
  //  pcur = pcur->next;
  //}
  //return size;


  return pq->size;

}



void QueueDestroy(Q* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  QNode* pcur = pq->phead;
  while (pcur)
  {
    QNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
}

对于队列这一种结构的实现,因为和单链表差异也不大,更细节的内容就没有过多赘述,对以单链表的实现方法有什么疑问的话,推荐先去看这一篇哦->单链表的实现方法

目录
相关文章
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
218 9
|
29天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
55 5
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
94 16
|
1月前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
135 8
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
100 4
|
1月前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
82 3
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
初步认识栈和队列
初步认识栈和队列
65 10
|
2月前
|
Java C++ 索引
让星星⭐月亮告诉你,LinkedList和ArrayList底层数据结构及方法源码说明
`LinkedList` 和 `ArrayList` 是 Java 中两种常见的列表实现。`LinkedList` 基于双向链表,适合频繁的插入和删除操作,但按索引访问元素效率较低。`ArrayList` 基于动态数组,支持快速随机访问,但在中间位置插入或删除元素时性能较差。两者均实现了 `List` 接口,`LinkedList` 还额外实现了 `Deque` 接口,提供了更多队列操作。
30 3
|
1月前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
72 0