整體思路解析

上次我們演示了使用數(shù)組實現(xiàn)隊列的方式，在結尾處提出了一個問題，因為我們使用雙指針后移的方式，被彈出隊列的元素依然存在數(shù)組中衅码，空間不能被重復利用。
這次我們提出了使用數(shù)組和雙指針實現(xiàn)環(huán)形隊列的方案脊岳。完成資源的利用逝段。
基本思路：
1. 初始化的雙指針head 和tail 的初始值為0，在添加和彈出的時候分別將指針后移割捅。那么實際的tail指針是指向了最后一個數(shù)字的下一位奶躯。因此環(huán)形隊列的實際存儲長度為 數(shù)組長度-1
2. 利用tail 和head 對數(shù)組長度取模的方式，完成在前面的資源位置利用
3. 判斷隊列滿的條件是 (tail +1) % arrSize == head ,因為tail有可能大于head 因此需要取模
4. 注意亿驾，在顯示隊列的內(nèi)容時候嘹黔，分為了 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 顯示當前隊列數(shù)據(jù)")
      println("pop 彈出隊列頭元素")
      println("add 添加元素")
      println("head 顯示隊列頭元素")
      println("size 查看隊列長度")
      println("exit 退出")
      val input = StdIn.readLine()
      input match {
        case "add" =>{
          println("請輸入一個數(shù)")
          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
  }

  //添加數(shù)據(jù)
  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
  }
}