使用数组实现环形队列

整体思路解析

上次我们演示了使用数组实现队列的方式，在结尾处提出了一个问题，因为我们使用双指针后移的方式，被弹出队列的元素依然存在数组中，空间不能被重复利用。
这次我们提出了使用数组和双指针实现环形队列的方案。完成资源的利用。
基本思路：
1. 初始化的双指针head 和tail 的初始值为0，在添加和弹出的时候分别将指针后移。那么实际的tail指针是指向了最后一个数字的下一位。因此环形队列的实际存储长度为 数组长度-1
2. 利用tail 和head 对数组长度取模的方式，完成在前面的资源位置利用
3. 判断队列满的条件是 (tail +1) % arrSize == head ,因为tail有可能大于head 因此需要取模
4. 注意，在显示队列的内容时候，分为了 tail>head 正常存储方式 和tail < head 利用空间 的两种展示方式

代码

package com.xipenhui.cn

import scala.io.StdIn

object CircleArrayTest {



  def main(args: Array[String]): Unit = {

    val queue = new CirccleArrayQueue(3)
    while (true){
      println("show 显示当前队列数据")
      println("pop 弹出队列头元素")
      println("add 添加元素")
      println("head 显示队列头元素")
      println("size 查看队列长度")
      println("exit 退出")
      val input = StdIn.readLine()
      input match {
        case "add" =>{
          println("请输入一个数")
          val num = StdIn.readInt()
          queue.addQueue(num)
        }
        case "show" =>queue.showQueue()
        case "pop" => println(s"出队列元素为：${queue.popQueue()}")
        case "size" =>println(s"队列长度为${queue.size()}")
        case "head" =>println(s"队列头为${queue.headElement()}")
        case "exit" => System.exit(0)
      }

    }
  }
}

class CirccleArrayQueue(arrMaxSize:Int){
  val maxSiza = arrMaxSize
  var head = 0  //head 和 tail维持在 0至maxsize之间，获取值的时候与maxSiza取模
  var tail = 0
  val arr  = new Array[Int](maxSiza)  //有效存储长度为maxsize-1

  //判断是否满
  def isFull() ={
    (tail + maxSiza+1  ) % maxSiza == head
  }

  //判断是否为空
  def isEmpty()={
    head == tail
  }

  //添加数据
  def addQueue(num:Int): Unit ={
    if(isFull){
      throw new RuntimeException("queue is full,can't add elem ")
    }
    arr(tail) = num
    tail = (tail + 1) % maxSiza
  }

  //弹出元素
  def popQueue(): Int ={
    if(isEmpty()){
      throw  new RuntimeException("queue is empty,can't pop element ")
    }
    val res = arr(head)
    arr(head) = 0
    head = (head +  1) % maxSiza
    res
  }

  //显示队列，增加遍历的长度，对i取模求值
  def showQueue()={
    if(isEmpty()){
      throw new RuntimeException("queue is empty ,no element ")
    }
    if(tail > head){
      for(i <- head until tail){
        println(s"arr(${i }) = ${arr(i)}")
      }
    }else{
      for(i <- head until tail + maxSiza){
        println(s"arr(${i % maxSiza}) = ${arr(i % maxSiza)}")
      }
    }

  }
  //查看队列头
  def headElement() ={
    if(isEmpty()){
      throw new RuntimeException("queue is empty, no head")
    }
    arr(head)
  }
  //队列长度,补齐位
  def size() ={
    (tail + maxSiza - head) % maxSiza
  }
}