【奇妙的数据结构世界】用图像和代码对队列的使用进行透彻学习 | 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;
  }
}

总结

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


目录
相关文章
|
3天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
1月前
|
存储 人工智能 算法
【C++数据结构——图】最短路径(头歌教学实验平台习题) 【合集】
任务描述 本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。 相关知识 为了完成本关任务,你需要掌握:Dijkst本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。为了完成本关任务,你需要掌握:Dijkstra算法。带权有向图:该图对应的二维数组如下所示:Dijkstra算法:Dijkstra算法是指给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径。Dijkstra算法的具体步骤如下:(1)初始时,S只包含源点,即S={v},v的距离为0。
61 15
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
46 10
|
1月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
61 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
48 12
|
1月前
|
算法 C++
【C++数据结构——图】最小生成树(头歌实践教学平台习题) 【合集】
【数据结构——图】最小生成树(头歌实践教学平台习题)目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:【合集】任务描述 本关任务:编写一个程序求图的最小生成树。相关知识 为了完成本关任务,你需要掌握:1.建立邻接矩阵,2.Prim算法。建立邻接矩阵 上述带权无向图对应的二维数组,根据它建立邻接矩阵,如图1建立下列邻接矩阵。注意:INF表示无穷大,表示整数:32767 intA[MAXV][MAXV];Prim算法 普里姆(Prim)算法是一种构造性算法,从候选边中挑
44 10
|
1月前
|
存储 算法 C++
【C++数据结构——图】图的邻接矩阵和邻接表的存储(头歌实践教学平台习题)【合集】
本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系,邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵,预期输出为Prim算法求解结果。通关代码提供了完整的C++实现,包括输入、构建和打印邻接矩阵与邻接表的功能。
49 10
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
38 7
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
44 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】