使用数组模拟队列Scala

这次使用数组模拟队列

基本思路是使用head 和tail的双指针，当添加时候 tail指针向后移动。弹出队列头的时候 head指针向后移动。两个指针范围内的值就是队列的内容

这次的队列有缺陷，就是无法重复利用已经被使用过的位置。下次我们使用数组模拟环形队列

代码

package cn.xipenhui.chapter1

import scala.io.StdIn

object ArrayQueueDemo {


  def main(args: Array[String]): Unit = {
    val queue = new ArrayQueue(3)

    //控制台输出的代码
    var key = ""
    while (true){
      println("show : 显示队列")
      println("exit 退出队列")
      println("add 添加元素")
      println("get 取出元素")
      println("head 查看队列头")

      key = StdIn.readLine()
      key match {
        case "show"=> queue.showQueue()
        case "add" =>{
          println("请输入一个数字")
          val num = StdIn.readInt()
          queue.addQueue(num)
        }
        case "get"=>{
          val res = queue.getQueue()
            println(s"取出的数据是${res}")
        }
        case "head" =>{
          val res = queue.showHeadQueue()

            println(s"头部的数据是${res}")

        }
        case "exit" => System.exit(0)
      }
    }
  }

}

/**
 * 创建一个队列需要有判断队列是否满，队列是否空，队列添加元素，
 * 初始化，弹出元素，查看队列内容，查看队列头
 *
 * 思路是：
 *   使用双指针，初始化为-1
 *   添加元素时候，先移动尾部指针，再复制
 *   弹出元素的时候，先移动指针，再弹出元素 因为 head指向的是当前头的前一位，需要移动到当前，再弹出
 */
class ArrayQueue(arrMaxSize:Int){

  val maxSize = arrMaxSize
  val arr = new Array[Int](maxSize)
  var head = -1
  var tail = -1

  def isFull():Boolean ={
    tail == maxSize -1
  }

  def isEmpty={
    head == tail
  }

  def addQueue(num:Int)={
    if(isFull()){
      throw  new RuntimeException("queue is full, cann't add element")
    }
    tail += 1
    arr(tail) = num
  }

  def getQueue() ={
    if(isEmpty){
      throw  new RuntimeException("queue is empty, cann't get element")
    }
    head += 1
    arr(head)
  }

  def showQueue(): Unit ={
    if(isEmpty){
      throw  new RuntimeException("queue is empty, cann't get element")
    }
    for (i <- head+1 to tail){
      println(s"arr(${i}) = ${arr(i)}")
    }
  }

  def showHeadQueue() ={
    if(isEmpty){
      throw  new RuntimeException("queue is empty, cann't get element")
    }
    arr(head+1)
  }
}

结束