探索数据结构:队列的的实现与应用

简介: 探索数据结构:队列的的实现与应用

一、队列的概念

队列是一个线性的数据结构,并且这个数据结构只允许在一端进行插入,另一端进行删除,禁止直接访问除这两端以外的一切数据,且队列是一个先进先出的数据结构。

通常,称进数据的一端为队尾,出数据的一端为队首,数据元素进队列的过程称为入队,出队列的过程称为出队

队列与栈类似,实现方式有两种。一种是以数组的方式实现,另一种以单链表来实现。这两种实现方式各有优劣,并且都有细节需要处理。

二、队列的声明与初始化

队列只有链式的设计方法,其本身分为多种队列,如顺序队列和循环队列,还有衍生的优先队列等等,以顺序队列的设计为例。


首先是队列的结点设计,可以设计出两个结构体,一个结构体 Node 表示结点,其中包含有 data 针,如图:

其中 data 表示数据,其可以是简单的类型,也可以是复杂的结构体。next 指针表示,下一个的指针,其指向下一个结点,通过 next 指针将各个结点链接。


然后再添加一个结构体,其包括了两个分别永远指向队列的队尾和队首的指针,看到这里是不是觉得和栈很像?

主要的操作只对这两个指针进行操作,如图所示:


代码实现如下:

typedef int QDataType;
// 链式结构:表示队列 
typedef struct QListNode
{
  struct QListNode* next;
  QDataType val;
}QNode;
 
// 队列的结构 
typedef struct Queue
{
  QNode* phead;
  QNode* ptail;
  int size;
}Queue;


对于初始化需要初始化两个类型,一个是初始化结点,一个是初始化队列。代码中的描述,初始化队列有些不同,当初始化队列的时候,需要将头尾两个结点指向的内容统统置为空,表示是一个空队列,函数代码可以表示为:

void QueueInit(Queue* pq)
{
  assert(pq);
  pq->phead = NULL;
  pq->ptail = NULL;
  pq->size = 0;
}


三、入队

入队操作如图:

进行入队(push)操作的时候,同样的,首先需要判断队列是否为空,如果队列为空的话,需要将头指针和尾指针一同指向第一个结点



如果队列不为空的时候,这时只需要将尾结点向后移动,通过不断移动 next指针指向新的结点构成队列即可。

void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("realloc fail");
  }
  newnode->next = NULL;
  newnode->val = x;
  if (pq->ptail == NULL)
  {
    pq->phead = pq->ptail = newnode;
  }
  else
  {
    pq->ptail->next = newnode;
    pq->ptail = newnode;
  }
  pq->size++;
}


四、出队

出队操作如图:

出队(pop)操作,是指在队列不为空的情况下进行的一个判断,当然在此也一定要进行队列判空的操。


如图,如果队列只有一个元素了,也就是说头尾指针均指向了同一个结点,那么直接将头尾两指针置空,并释放这一个结点即可,如图:

当队列含有以上个元素时,需要将队列的头指针指向头指针当前指向的下一个元素,并释放掉当前元素即可,如图:


代码实现如下:

void QueuePop(Queue* pq)
{
  assert(pq);
  assert(pq->phead);
 
  if (pq->phead == pq->ptail)
  {
    free(pq->phead);
    pq->phead = pq->ptail = NULL;
  } 
  else
  {
    QNode* next = pq->phead;
    pq->phead = pq->phead->next;
    free(next);
  }
  pq->size--;
}


五、获取队头和队尾元素

我们有头尾节点的指针,只需要注意链表和节点元素不能为空即可

// 获取队列头部元素 
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(pq->phead);
 
  return pq->phead->val;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(pq->ptail);
 
  return pq->ptail->val;
}


六、获取队列中有效元素个数

1. int QueueSize(Queue* pq)
2. {
3.  assert(pq);
4.  return pq->size;
5. }


七、检测队列是否为空

1. bool QueueEmpty(Queue* pq)
2. {
3.  assert(pq);
4. 
5.  return pq->size == 0;
6. }


八、销毁队列

void QueueDestroy(Queue* pq)
{
  assert(pq);
  for (int i = 0; i < pq->size; i++)
  {
    QNode* next = pq->phead;
    pq->phead = pq->phead->next;
    free(next);
  }
  pq->phead = pq->ptail = NULL;
}


九、完整代码

9.1 Queue.h

typedef int QDataType;
// 链式结构:表示队列 
typedef struct QListNode
{
  struct QListNode* next;
  QDataType val;
}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 QueueDestroy(Queue* pq);


9.2 Queue.c

// 初始化队列
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->phead = NULL;
  pq->ptail = NULL;
  pq->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("realloc fail");
  }
  newnode->next = NULL;
  newnode->val = x;
  if (pq->ptail == NULL)
  {
    pq->phead = pq->ptail = newnode;
  }
  else
  {
    pq->ptail->next = newnode;
    pq->ptail = newnode;
  }
  pq->size++;
}
// 队头出队列 
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(pq->phead);
 
  if (pq->phead == pq->ptail)
  {
    free(pq->phead);
    pq->phead = pq->ptail = NULL;
  } 
  else
  {
    QNode* next = pq->phead;
    pq->phead = pq->phead->next;
    free(next);
  }
  pq->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(pq->phead);
 
  return pq->phead->val;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(pq->ptail);
 
  return pq->ptail->val;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  
  return pq->size == 0;
}
// 销毁队列 
void QueueDestroy(Queue* pq)
{
  assert(pq);
  for (int i = 0; i < pq->size; i++)
  {
    QNode* next = pq->phead;
    pq->phead = pq->phead->next;
    free(next);
  }
  pq->phead = pq->ptail = NULL;
}
相关文章
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
131 9
|
2月前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
47 1
|
2月前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践,体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案,包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例,帮助读者掌握C语言的基本语法和常用算法,提升编程能力。
72 4
|
2月前
|
机器学习/深度学习 存储 人工智能
数据结构在实际开发中的广泛应用
【10月更文挑战第20天】数据结构是软件开发的基础,它们贯穿于各种应用场景中,为解决实际问题提供了有力的支持。不同的数据结构具有不同的特点和优势,开发者需要根据具体需求选择合适的数据结构,以实现高效、可靠的程序设计。
79 7
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
初步认识栈和队列
初步认识栈和队列
61 10
|
2月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
25 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
2月前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
18 0
|
2月前
|
存储
探索数据结构:单链表的实践和应用
探索数据结构:单链表的实践和应用
|
2月前
|
存储 测试技术
探索数据结构:顺序表的实现与应用
探索数据结构:顺序表的实现与应用