4.4 Scala集合：Queue和Stack

Queue

队列（queue）是一种“先进先出”的数据结构。这一节我们学习如何使用Scala的不可变队列，以及执行一些常见的操作，如初始化，添加或删除元素，在队列中通过键找到元素，入队和出队。Queue的元素是先进先出顺序(FIFO)的。

【示例】使用不可变队列的示例。

import scala.collection.immutable.Queue
​
object QueueDemo {
  def main(args: Array[String]): Unit = {
    println("1: 初始化一个有3个元素的队列")
    val queue1: Queue[String] = Queue("苹果", "香蕉", "葡萄干")
    println(s"queue1的元素 = $queue1")
​
    println("\n2: 访问一个队列中特定索引的元素")
    println(s"索引0处的元素 = ${queue1(0)}")
    println(s"索引0处的元素 = ${queue1.head}")
    println(s"索引1处的元素 = ${queue1(1)}")
    println(s"索引2处的元素 = ${queue1(2)}")
​
    println("\n3: 使用 :+ 在队列中添加元素")
    val queue2: Queue[String] = queue1 :+ "Glazed Donut"
    println(s"queue2的元素 = $queue2")
​
    println("\n4: 使用 enqueue函数向队列中添加元素")
    val enqueue: Queue[String] = queue1.enqueue("火龙果")
    println(s"enqueue的元素 = $enqueue")
​
    println("\n5: 使用dequeue函数从队列中获取第一个元素")
    val dequeue: (String, Queue[String]) = queue1.dequeue
    // 调用dequeue返回Tuple2，其中包含插入到Queue的第一个元素和队列的其余元素
    println(s"dequeue的第一个元素 = ${dequeue._1}")
    println(s"dequeue后的剩余元素 = ${dequeue._2}")
​
    println("\n6: 使用 ++ 将两个队列添加到一起")
    val queue3: Queue[String] = queue1 ++ Queue[String]("草莓", "菠萝")
    println(s"queue3中的元素 = $queue3")
​
    println("\n7: 初始化一个空队列")
    val emptyQueue: Queue[String] = Queue.empty[String]
    println(s"Empty Queue = $emptyQueue")
  }
}

Stack

栈(又叫堆栈)是一种遵循后进先出语义的数据结构。它通常提供一个push()方法在栈顶添加元素，以及一个pop()方法从栈顶获取最近添加的元素。

在本节，我们将学习如何使用Scala的不可变Stack栈来执行一些常见的操作，比如将新元素推入栈顶，从栈中移除或弹出元素。值得注意的是，从Scala 2.13.0开始，Immutable Stack类已经被弃用，可以使用Immutable List来实现类似堆栈的操作。

【示例】使用Immutable List来实现类似堆栈的操作。

import scala.collection.immutable.Stack
​
object StackDemo {
  def main(args: Array[String]): Unit = {
    println("1: 初始化堆栈")
    val stack1: Stack[String] = Stack("苹果", "香蕉", "葡萄干")
    println(s"stack1的元素 = $stack1")
​
    println("\n2: 使用不可变列表List初始化堆栈")
    val stack2: List[String] = List("苹果", "香蕉", "葡萄干")
    println(s"使用不可变列表的堆栈，元素是 = $stack2")
​
    println("\n3: 使用Immutable List的::将一个元素压入栈顶")
    val stack3: List[String] = "火龙果" :: stack2
    println(s"使用不可变列表的堆栈，push后的元素 = $stack3")
​
    println("\n4: 使用Immutable List的::将N个元素推入栈顶")
    val stack4: List[String] = "草莓" :: "荔枝" :: stack2
    println(s"使用不可变列表的堆栈，phsh N个元素后 = $stack4")
​
    println("\n5: 使用Immutable List的tail函数从Stack中弹出元素")
    val stack5: List[String] = stack2.tail
    println(s"使用不可变列表进行堆栈，tail函数模拟堆栈弹出后的元素 = $stack5")
​
    println("\n6: 使用不可变列表初始化一个空堆栈")
    val emptyStack: List[String] = List.empty[String]
    println(s"使用不可变列表的堆栈，空堆栈 = $emptyStack")
  }
}