实验三 队列

实验三 队列

实验目的和要求

  1. 理解队列的特点
  2. 掌握队列这种结构的算法设计
  3. 学会运用队列来储存数据和求解相关问题

实验环境

  1. Visual Studio 2017 Community
  2. Windows 10 Pro

实验内容

  1. 设计出一个模板队列,测试队列的各种运算
  2. 利用模板队列打印出杨辉三角形

实验过程

任务一

设计

根据队列的特点,队列应具有以下属性和功能:

属性:

  • 队列的最大容量
  • 队列头的指针
  • 队列尾的指针
  • 队列中元素的数量

功能:

  • 进队列
  • 出队列
  • 获取队列头元素
  • 判断队列是否为空或是否已满

本次实验采用 C++ 作为编程语言,可用 C++ 中的模板类来封装队列,以实现储存不同类型的数据。

编码实现

通过 C++ 的模板知识来编写模板类的代码。

测试

测试队列结果

任务二

设计

根据杨辉三角形的特点:

  1. 第 N 行有 N 个数字
  2. 每一行的开头和结尾均为 “1”
  3. 除了数字 “1” 以外的数字都等于其上方两个数字之和。也就是说,除了 “1” 以外的每一个数字都是由之前的数字计算而来,这样,只需将打印出的数字储存起来,根据由上往下打印的规律,应将数字储存在队列中

编码实现

通过已有的模板队列和以上设计思路进行编写代码。

测试

测试杨辉三角结果

实验收获

通过本次实验,掌握了队列的设计方法,体会到了队列的先进先出的特点。利用这一特点来储存数据,打印出了杨辉三角形。实际上,在解决实际问题时,若某种现象满足先进先出的规律,都可以考虑到使用队列来作为管理数据的方式,在本次实验中,打印数据时,每个被打印的数据都应该被储存起来用于之后计算数字,明显符合队列的特点,故可以采用队列来解决问题。