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
}
}
网友评论