【奇妙的数据结构世界】用图像和代码对队列的使用进行透彻学习 | C++

简介: 简单来说,数据结构是一种辅助程序设计并且进行优化的方法论,它不仅讨论数据的存储与处理的方法,同时也考虑到了数据彼此之间的关系与运算,从而极大程度的提高程序执行的效率,减少对内存空间的占用等。不同种类的数据结构适用于不同的程序应用,选择合适正确的数据结构,可以让算法发挥出更大的性能,给设计的程序带来更高效率的算法。

前言

       简单来说,数据结构是一种辅助程序设计并且进行优化的方法论,它不仅讨论数据的存储与处理的方法,同时也考虑到了数据彼此之间的关系与运算,从而极大程度的提高程序执行的效率,减少对内存空间的占用等。不同种类的数据结构适用于不同的程序应用,选择合适正确的数据结构,可以让算法发挥出更大的性能,给设计的程序带来更高效率的算法。


一、队列是什么?

1.简要介绍

       队列和堆栈都是一种线性有序列表,它们都属于抽象数据类型。在上一节我们讲了堆栈的基本特性和其操作方法,而这一节的队列在一些方面与它存在显著的差异,像队列的加入和删除这些操作都发生在不同的两端,符合一种先进先出,后进后出的特性。并且它使用front与rear两个指针分别指向队头和队尾,用其来对队列进行一系列的操作。


2.具体情况

       在我们的日常生活中,队列这种抽象模型概念是最常见的也是最常用的,像生活中基本涉及到的排队问题都是这种数据模型的直接体现。而作为程序员的我们,如何将它在代码中实现才是我们应该要去考虑的问题。队列在计算机领域的应用非常广泛,例如计算机的模拟、图形遍历的广度优先搜索法、CPU的作业调度、外围设备联机并发处理系统等等领域。像堆栈一样,队列也可以分为顺序队列和链式队列。具体情况如下图所示:


上图 顺序队列

下图 链式队列

二、队列操作的关键代码段

1.类型定义

①顺序队列存储结构的定义

typedef struct {
  qelemtype* base;    //初始化的动态分配存储空间
  int front;    //头指针
  int rear;    //尾指针
}sqqueue;
②链式队列存储结构的定义
typedef struct qnode {
  qelemtype data;   //数据域
  struct qnode* next;  //指针域
}qnode,*queueP;  //链表的基本定义方法
typedef struct {
  queueP front;   //头指针
  queueP rear;    //尾指针
}linkqueue;    //链式指针的定义

2.顺序队列的常用操作

①队列的初始化

84c0f72de59ce19fe510528bf44f1e91_504978ab38ee44b29d9a5bb69b967d36.png


void initqueue(sqqueue& q)
{
  q.base = new qelemtype[maxsize];   //开拓一块新的队列区域,大小自定
  if (!q.base)   //判断队列是否创建成功
  exit(0);
  q.front = q.rear = 0;   //初始化下将头尾指针置为0,即队列为空
}

②求队列的长度

f8e8c36b04a9f6df406c9880d175aaa7_d04e4716d4ce44ff93b6a76523d4f3eb.png


int queuelength(sqqueue& q)
{
  return ((q.rear - q.front + maxsize) % maxsize);   //算法+数据结构去求解队列的长度
}

③队列入队

1c695093d3de5ea6e7d514f1ed3af86a_dd66fdefc2b44a109e4457b9e8ac9026.png


int enqueue(sqqueue& q,qelemtype e)
{
  if ((q.rear + 1) % maxsize == q.front) {
  return 0;   
  }  //判断队列已满
  else {
  q.base[q.rear] = e;    //队列未满,尾指针指向位置为下标,向尾部插入新元素
  q.rear = (q.rear + 1) % maxsize;  //队尾指针加1
  return 1;
  }
}

④队列出队

018293a2659eea0190d287c4b1e0920f_7bad8294f26a4118a7726e4453f5f23d.png


int dequeue(sqqueue& q, qelemtype &e)
{
  if (q.front == q.rear) {
  return 0;
  }//判断队列为空
  else { 
  e=q.base[q.front];   //保存当前队头元素
  q.front = (q.front + 1) % maxsize;   //队头指针加1
  return 1;
  }
}

⑥取队头元素

54b5fc10b0da48faa6f2ee239e2b4254_272e5f080b354e9f8b34c4d2ad1eb4b5.png

qelemtype getheaddata(sqqueue& q)
{
  if (q.front != q.rear) //队列不为空
  return q.base[q.front];   //取队头元素
}

3.链式队列的常用操作

①队列初始化

3a737803b803022952d940def396f07e_43c149b588a64869a629da18a6674ce2.png


void initqueue(linkqueue &q)
{
  q.front = q.rear = new qnode;   //创建链队列初始结点,并且将两个指针指向它
  if (!q.front) {
  exit(0);
  }   //判断该队列是否创建成功
  else {
  q.front->next = NULL;   //创建成功,将该结点指针域置为空
  }
}

②队列入队

5d4c9b1d62683625770f8cc672627bcd_b1e63d6cecb5434b9589429b85998839.png

int enqueue(linkqueue &q,qelemtype e)
{
  qnode* p;  //创建一个新的结点指针
  p = new qnode;  //创建一个新的结点,指针p指向它
  if (!p) {
  return 0;   //判断结点是否创建成功
  }
  else {
  p->data = e;   //将新元素放入新创建的结点中
  p->next = NULL;   //将该结点的指针域置为空,它将作为尾结点
  q.rear->next = p;   //将上一个结点的指针域连向这个新创建的入队结点
  q.rear=p;  //将尾指针指向该新结点
  return 1;
  }
}

③队列出队

bcd298bac32de5c33321d781b3dfa269_3b4c2ff8fa5e42d1a30b0c2576f39695.png

int dequeue(linkqueue& q, qelemtype &e)
{
  qnode* p;
  if (q.front == q.rear) {
  return 0;  //判断队列为空
  }
  else {
  p = q.front->next;    //将指针p指向队头结点后的第一个数据元素
  e=p->data;    //将要出队的结点的数据元素保存
  q.front->next=p->next;    //将链队列头结点的指针域指向要出队的队头结点的下一个结点的位置
  if (q.rear == p) {
    q.rear = q.front;  //判断如果出队的是队列中最后一个元素的话,就需要将头尾指针再同时头结点
  }
  delete p;  //元素结点删除出队
  return 1;
  }
}

④取队头元素

320ab5504d9255ecfb3744700e75f3f5_c6b29f8bdd3341ebbeef3dc67f9c936e.png



int getheaddata(linkqueue& q, qelemtype &e)
{
  if (q.front == q.rear) {
  return 0;   //空队列的判断
  }
  else {
  e = q.front->next->data;   //取得头结点后第一个数据元素
  return 1;
  }
}

总结

       以上就是我们对队列的所有讲解情况,如果你还想对队列进行其他的操作分析,可以将原理和图像结合去编写程序代码即可,并且通过不断的调试去验证你所写的操作是否可以执行。熟悉了上面的关键代码段后,你可以通过一些典型例题去对队列这部分数据结构的知识进行实战练习。如果可以将队列合理地运用到一些程序设计问题中,那么你可能会更好更快的去解决问题。


目录
相关文章
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
140 9
|
13天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
32 5
|
12天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
36 1
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
1月前
|
缓存 安全 C++
C++无锁队列:解锁多线程编程新境界
【10月更文挑战第27天】
40 7
|
1月前
|
消息中间件 存储 安全
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法