2020-11-10-数据结构与算法-14(队列scala版)

1.队列 非环形实现

package Arithmetic

import scala.io.StdIn

object Queue {
  val queue = new ArrayQueue(20)

  def main(args: Array[String]): Unit = {
    //初始化一个队列

    while (true) {
      println("请输入命令 \n\t" +
        "1.判断是否为空 \n\t" +
        "2.判断是否已满 \n\t " +
        "3.添加数据\n\t" +
        "4.展示内容\n\t" +
        "5.获取数据 \n\t" +
        "6.获取头节点\t\n")
      val str = StdIn.readLine()
      str match {
        case "1" => queue.isNull()
        case "2" => queue.isFull()
        case "3" => addData()
        case "4" => queue.show()
        case "5" =>
          val value = queue.getData()
          if (!value.isInstanceOf[Exception]) {
            println(value)
          }
        case "6" =>
          val value = queue.peek()
          if (!value.isInstanceOf[Exception]) {
            println(value)
          }
      }
    }
  }

  def addData() = {
    println("请输入数字")
    val i = StdIn.readInt()
    queue.addData(i)
  }
}

//用数组来模拟队列
class ArrayQueue(maxCapacity: Int) {
  //初始化一个数组
  val queue = new Array[Int](maxCapacity-1)
  //-1是不包含数组数据的(队列的头)
  var first: Int = -1
  //表示队列添加到哪的索引
  var rear: Int = -1

  //判断是否满了
  def isFull(): Boolean = {
    if (first == maxCapacity) {
      println("已经满了")
      return true
    }
    else {
      println("队列没有满可以添加元素")
      false
    }

  }

  //判断队列是否为空
  def isNull(): Boolean = {
    if (first == rear) {
      println("队列是空的")
      return true

    }
    else {
      println("可添加元素")
      false
    }
  }

  //添加到队列
  def addData(number: Int) = {
    //首先rear要后移一个单位
    rear += 1
    //往数组添加数据
    queue(rear) = number
    //返回值
    true
  }

  //获取队列的元素,是first加1 但是原来的数据还是存在的,只是访问不到了,需要判断是否有异常
  def getData(): Any = {
    //首先判断队列是否为空
    if (isNull()) {
      throw new  Exception("空")
    }
    else {
      first += 1
      return queue(first)
    }
  }

  //peek方法获取头节点,但是不改变first的值
  def peek(): Any = {
    if (isNull()) {
      throw new Exception("空")
    }
    else {
      return queue(first + 1)
    }
  }


  //展示队列的内容
  def show() = {
    for (i <- first + 1 to rear) {
      printf("队列%s 内容%d \t\n", i, queue(i))
    }
  }
}

2.队列环形版

核心思想: 用%来模拟循环(rear +1) /maxsize = first 时为满
核心思想2:遍历元素时,假设rear节点在first节点之前采用(rear- first)就无法获取数据,采用取模的方法来获取队列到底用多少数据 (rear - first + maxCapacity) % maxCapacity

package Arithmetic

import scala.io.StdIn

object CircleQueue {
  val queue = new ArrayCircleQueue(5)

  def main(args: Array[String]): Unit = {
    while (true) {
      println("请输入命令 \n\t" +
        "1.判断是否为空 \n\t" +
        "2.判断是否已满 \n\t " +
        "3.添加数据\n\t" +
        "4.展示内容\n\t" +
        "5.获取数据 \n\t" +
        "6.获取头节点\t\n")
      val str = StdIn.readLine()
      str match {
        case "1" => queue.isNull()
        case "2" => queue.isFull()
        case "3" => addData()
        case "4" => queue.show()
        case "5" =>
          val value = queue.getData()
          if (!value.isInstanceOf[Exception]) {
            println(value)
          }
        case "6" =>
          val value = queue.peek()
          if (!value.isInstanceOf[Exception]) {
            println(value)
          }
      }
    }
  }

  def addData() = {
    println("请输入数字")
    val i = StdIn.readInt()
    queue.addData(i)
  }


}

class ArrayCircleQueue(maxCapacity: Int) {
  //数组模拟队列
  val queue = new Array[Int](maxCapacity)
  //两个指针分别代表存取,初始化为0
  var first: Int = 0
  var rear: Int = 0

  //判断是否为空
  def isNull(): Boolean = {
    first == rear
  }

  //判断是否已满
  def isFull(): Boolean = {
    //最后一个节点不存储数据,%取余与first比较
    (rear + 1) % maxCapacity == first
  }

  //添加元素
  def addData(number: Int): Any = {
    //首尔判断是否为满
    if (isFull()) {
      println("队列已经满了")
      return
    }
    queue(rear) = number
    //rear指针后移
    rear = (rear + 1) % maxCapacity

  }

  //获取元素
  def getData(): Any = {
    //首先判断队列是否为空
    if (isNull()) {
      println("该队列为空请添加元素")
      return
    }
    //使用临时节点存储要返回的数据
    var result = queue(first)
    //后移first节点
    first = (first + 1) % maxCapacity
    //返回要get的队列数据
    return result

  }

  //获取头节点
  def peek(): Any = {
    //和非循环的写法一致
    return queue(first)
  }

  //遍历队列
  def show(): Any = {
    //这是一个难点,我要保证我能获取之后添加的数据
    if (isNull()) {
      println("队列为空")
      return
    }
    //遍历队列
    for (i <- first until first + size) {
      printf("array(%d)=%s \t\n", i % maxCapacity, queue(i % maxCapacity))
    }

  }

  //获取队列的长度
  def size(): Int = {
    (rear - first + maxCapacity) % maxCapacity
  }

}