数据结构队列的实现

简介: 数据结构队列的实现

本章介绍数据结构队列的内容,我们会从队列的定义以及使用和OJ题来了解队列,话不多说,我们来实现吧

队列

1。队列的概念及结构

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出

FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头。

我们来看一下下面的这张图,让我们更好的理解它

我们从队尾入,队头出,只能是这样入栈和出栈

2。队列的实现

队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数

组头上出数据,效率会比较低。

那队列的实现我们是用链式结构来实现的,因为用数组下标的话,出栈的时候要往前挪动数据,会更麻烦,这样队列的意义就下降了,所以我们这里用的方法是链式结构。

typedef int QueueDataType;
typedef struct QueueNode
{
  QueueDataType* next;
  QueueDataType data;
}QueueNode;
typedef struct Queue
{
  QueueDataType* head;
  QueueDataType* tail;
}Queue;

这里我们定义的结构体Queue有很大的作用,因为队列不是像单链表那样,队列是有它的特点的,其中最大的一个特点就是入栈只能从尾入,出栈就是头出,所以我们在这里定义head和tail有很大的作用,定义在结构体当中会方便不少,那我们现在继续往下看我们的接口函数吧。

给大家看一下下面实现队列的接口函数,然后我们一步一步的来实现他们

// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QueueDataType QueueFront(Queue* q);
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

队列的初始化

void QueueInit(Queue* q);

初始化我们初始的是结构体Queue中的内容

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

首先要判断传过来的指针是否是为空,然后将头指针和尾指针都置为NULL。

销毁队列

void QueuePush(Queue* q, QueueDataType data)

首先我们要创造一个节点将它放入,创造节点的结构体就是QueueNode,然后我们要更新后面节点中的head和tail,这里大家肯定有疑问,我们竟然是更新指针,那我们应该传指针的地址才能起到作用,一级指针只能改变结构体的内容,那我们在这里传的话,难道不会产生问题吗?答案是不会,我们的结构体中放的就是指针,那我们只需要改变结构体的内容,就是head和tail就行,竟然是这样的话,我们传一个一级指针就可以起到我们的作用,所以传的是一级,那现在我们在插入函数中先创造一个节点,因为只能从队列的尾插入,而且有了这个指针,我们就不需要像单链表那样再去找尾,我们每次插入都会更新尾。

void QueuePush(Queue* q, QueueDataType data)
{
  assert(q);
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->data = data;
  newnode->next = NULL;
  if (q->head == NULL)
  {
    q->head = q->tail = newnode;
  }
  else
  {
    q->tail->next = newnode;
    q->tail = newnode;
  }
}

有了入栈就有出栈,出栈的话是从我们的队列最开始的地方出队,我们来实现一下吧!

void QueuePop(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  QueueNode* headnext = q->head->next;
  free(q->head);
  q->head = headnext;
}
/

这里的空是因为如果我们的队列都是空的话,我们哪里还有数据进行删除呢

所以要先检查一下是不是为空,那接着我们把这个函数也实现一下吧

bool QueueEmpty(Queue* q)
{
  assert(q);
  return q->head == NULL;
}

这个很好理解,如果为空就代表一个数也没有,那我们就不能再对队列进行操作了,那再来看我们下面的接口函数吧。

// 获取队列头部元素
QueueDataType QueueFront(Queue* q)
{
  assert(q);
  return q->head->data;
}

有头就有尾,希望我们的人生也是

那我再来实现一下取尾的接口吧

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

我们继续往下走,实现一下我们后面的接口函数,这些基本上都很简单,我就也不再解释了,看代码就能理解的

int QueueSize(Queue* q)
{
  assert(q);
  int count = 0;
  QueueNode* cur = q->head;
  while (cur)
  {
    count++;
    cur = cur->next;
  }
  return count;
}

销毁队列

void QueueDestroy(Queue* q)
{
  while (!QueueEmpty(q))
  {
    QueueNode* headnext = q->head->next;
    free(q->head);
    q->head = headnext;
  }
}

统计我们队列节点的数量我们遍历一遍就可以实现了,定义一个cur指针进行遍历,那其他的我们也都讲完了,后面分享栈和队列的OJ题给大家,看完之后对队列有了更深的理解

完整代码

#include"Queue.h"
// 初始化队列
void QueueInit(Queue* q)
{
  assert(q);
  q->head = q->tail = NULL;
}
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data)
{
  assert(q);
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->data = data;
  newnode->next = NULL;
  if (q->head == NULL)
  {
    q->head = q->tail = newnode;
  }
  else
  {
    q->tail->next = newnode;
    q->tail = newnode;
  }
}
// 队头出队列
void QueuePop(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  QueueNode* headnext = q->head->next;
  free(q->head);
  q->head = headnext;
}
// 获取队列头部元素
QueueDataType QueueFront(Queue* q)
{
  return q->head->data;
}
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q)
{
  return q->tail->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
  assert(q);
  int count = 0;
  QueueNode* cur = q->head;
  while (cur)
  {
    count++;
    cur = cur->next;
  }
  return count;
}
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
bool QueueEmpty(Queue* q)
{
  assert(q);
  return q->head == NULL;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
  while (!QueueEmpty(q))
  {
    QueueNode* headnext = q->head->next;
    free(q->head);
    q->head = headnext;
  }
}
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QueueDataType;
typedef struct QueueNode
{
  QueueDataType* next;
  QueueDataType data;
}QueueNode;
typedef struct Queue
{
  QueueDataType* head;
  QueueDataType* tail;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QueueDataType QueueFront(Queue* q);
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

今天的分享就到这里了,我们下次再见

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