Scala 集合：Seq API

发表于2018-05-17字数统计5.3k阅读时长28分

Seq 是一个特质类型（定义如下），用于表示按照一定顺序排列的元素序列，Seq 继承了偏函数 PartialFunction 特质，所以一个序列本质上也是一个偏函数，对应的函数类型是 Int => A，其中 A 是对应 Seq 的元素类型，而输入参数是 Seq 的下标。

trait Seq[+A] extends PartialFunction[Int, A]
                      with Iterable[A]
                      with GenSeq[A]
                      with GenericTraversableTemplate[A, Seq]
                      with SeqLike[A, Seq[A]]

Seq 同样分为可变和不可变两大类，此外还派生出 IndexedSeq 和 LinearSeq 两个重要的子特质：

IndexedSeq ：代表索引序列，对于基于索引的操作来说效率较高，一般底层依赖于数组实现。
LinearSeq ：代表线性序列，对于 head、tail，以及 isEmpty 一类的方法效率较高，一般底层依赖于链表实现。

IndexedSeq 特质典型的实现类有 ArraySeq、Vector，以及 Range 等，其中 Vector 基于 Trie 树实现，在随机读和随机更新方面进行了权衡，虽然随机读的时间相对于数组略长，但是随机更新性能要优于数组和链表，是 iimmutable IndexedSeq 的默认实现。

LinearSeq 特质的典型实现类就是 List 类型，不过 List 是一个抽象类，默认基于 ListBuffer 构建。ListBuffer 的父特质 Buffer 也是 Seq 派生的一个重要子特质，Buffer 特质声明为 mutable，用于定义可变的 Seq 集合，除了 ListBuffer 实现类，Scala 主要还提供了基于数组的 ArrayBuffer 实现。

本文我们主要介绍 Seq 系的集合，包括 Seq、Buffer、List、Stack，以及 Queue。

一. Seq

1.1 获取集合索引

1.1.1 indexOf & lastIndexOf

函数 indexOf 和 lastIndexOf 均用于从给定 Seq 对象中检索指定元素的下标值（如果不存在则返回 -1），区别在于 indexOf 从左至右开始检索，而 lastIndexOf 则从右至左开始检索，同时这两个方法均允许指定检索的起始下标。函数定义如下：

def indexOf[B >: A](elem: B): Int
def indexOf[B >: A](elem: B, from: Int): Int

def lastIndexOf[B >: A](elem: B): Int
def lastIndexOf[B >: A](elem: B, end: Int): Int

示例：

1
2
3

val seq = Seq('a' to 'z': _*)
seq.indexOf('c') // 输出：2
seq.lastIndexOf('h') // 输出：7

1.1.2 indexWhere & lastIndexWhere

函数 indexWhere 和 lastIndexWhere 相对于 indexOf 和 lastIndexOf 更加灵活一些，这两个函数均允许指定谓词 A => Boolean 来对集合中的元素进行筛选，并返回满足条件的第 1 个元素对应的下标。函数定义如下：

def indexWhere(p: A => Boolean, from: Int): Int
def indexWhere(p: A => Boolean): Int

def lastIndexWhere(p: A => Boolean): Int
def lastIndexWhere(p: A => Boolean, end: Int): Int

示例：

1
2
3

val seq = Seq(1 to 9: _*)
seq.indexWhere(x => x % 2 == 0 && x > 5) // 输出：5
seq.lastIndexWhere(x => x % 2 == 1 && x < 5) // 输出：2

实际上 indexOf 和 lastIndexOf 底层分别使用 indexWhere 和 lastIndexWhere 进行实现。

1.1.3 indexOfSlice & lastIndexOfSlice

函数 indexOfSlice 和 lastIndexOfSlice 用于检索给定的子序列在 Seq 对象中的位置，并返回子序列第 1 个元素对应的下标，如果不存在则返回 -1。函数定义如下：

def indexOfSlice[B >: A](that: GenSeq[B]): Int
def indexOfSlice[B >: A](that: GenSeq[B], from: Int): Int

def lastIndexOfSlice[B >: A](that: GenSeq[B]): Int
def lastIndexOfSlice[B >: A](that: GenSeq[B], end: Int): Int

示例：

val seq = Seq(1 to 9: _*)
seq.indexOfSlice(Seq(7, 8)) // 输出：6
seq.lastIndexOfSlice(Seq(7, 8)) // 输出：6
seq.indexOfSlice(Seq(1, 8)) // 输出：-1
seq.lastIndexOfSlice(Seq(1, 8)) // 输出：-1

1.1.4 indices

函数 indices 用于获取 Seq 对象的索引集合，返回一个 Range 对象，示例：

1 2	val seq = Seq("A", "B", "C") seq.indices // 输出：Range 0 until 3

1.2 获取集合长度

1.2.1 length & size

函数 length 和 size 都可以返回当前 Seq 对象的长度，区别在于 size 是 Traversable 中定义的方法，而 length 是 Seq 中定义的方法，二者在功能上是等价的。示例：

1
2
3

val seq = Seq(1 to 9: _*)
seq.size // 输出：9
seq.length // 输出：9

1.2.2 lengthCompare

函数 lengthCompare 接收一个参数 n，用于将当前 Seq 对象的长度 l 与该参数进行比较，如果 l > n 则返回 1，如果 l == n 则返回 0，如果 l < n 则返回 l - n。示例：

val seq = Seq(1 to 9: _*)
seq.lengthCompare(8) // 输出：1
seq.lengthCompare(9) // 输出：0
seq.lengthCompare(18) // 输出：-1

为什么 seq.lengthCompare(18) 的结果是 -1，而不是 -9 呢，这是因为这里实际使用的实现类 List 覆盖实现了该方法，强制返回 -1。

1.2.3 segmentLength & prefixLength

函数 segmentLength 接收一个谓词 A => Boolean，用于从指定下标 from 开始往右检索连续满足条件的子序列的最大长度，函数定义如下：

1	def segmentLength(p: A => Boolean, from: Int): Int

而函数 prefixLength 是 segmentLength 的特殊版本，其 from 参数设置为 0，表示从头开始检索，即检索集合满足给定条件的最长前缀子序列，并返回其长度。示例：

1
2
3

val seq = Seq(1 to 9: _*)
seq.segmentLength(_ < 5, 2) // 输出：2
seq.prefixLength(_ < 5) // 输出：4

1.3 查询操作

1.3.1 apply

函数 apply 用于从 Seq 对象中获取指定下标的元素，例如 seq.apply(2) 用于获取下标为 2 的元素，也可以简写为 seq(2)，示例：

1
2
3

val seq = Seq("A", "B", "C")
seq.apply(2) // 输出：C
seq(2) // 输出：C

1.4 插入操作

1.4.1 +: & :+

函数 +: 和 :+ 均用于往 Seq 对象中追加元素，并返回一个新的集合对象，区别在于 +: 是前置追加，而 :+ 是后置追加，示例：

1
2
3

val seq = Seq(2, 3, 4)
1 +: seq // 输出：List(1, 2, 3, 4)
seq :+ 5 // 输出：List(2, 3, 4, 5)

1.4.2 padTo

函数 padTo 用于将当前 Seq 对象中的前 len 个元素复制到新集合中，并在集合元素不够时使用给定的 elem 默认值填充。函数定义如下：

1	def padTo[B >: A, That](len: Int, elem: B)(implicit bf: CanBuildFrom[Repr, B, That]): That

示例：

1
2
3

val seq = Seq(2, 3, 4)
seq.padTo(5, 0) // 输出：List(2, 3, 4, 0, 0)
seq.padTo(2, 0) // 输出：List(2, 3, 4)

1.5 更新操作

1.5.1 updated

函数 updated 用于更新 Seq 对象中指定下标位置的元素值，对于不可变集合的修改会创建出一个新的集合，而对于可变集合来说则是原地修改，所以对于可变集合可以简写为 () 操作符。示例：

val seq = Seq(1, 2, 3)
seq.updated(2, 8) // 输出：List(1, 2, 8)
val mseq = mutable.Seq(1, 2, 3)
mseq(2) = 8
mseq // 输出：ArrayBuffer(1, 2, 8)

1.5.2 patch

函数 patch 使用给定的元素序列 patch 替换 Seq 对象中 [from, from + replaced) 下标的元素。函数定义如下：

1	def patch[B >: A, That](from: Int, patch: GenSeq[B], replaced: Int)(implicit bf: CanBuildFrom[Repr, B, That]): That

示例：

1 2	val seq = Seq(1 to 9: _*) seq.patch(3, Seq(8, 8, 8, 8, 8), 2) // 输出：List(1, 2, 3, 8, 8, 8, 8, 8, 6, 7, 8, 9)

1.6 排序操作

1.6.1 sorted & sortBy & sortWith

函数 sorted、sortBy 和 sortWith 均用于对 Seq 对象中的元素进行排序操作，区别在于：

sorted ：按照元素的值从小到大进行排序。
sortBy ：按照指定的因子从小到大对集合中的元素进行排序。
sortWith ：接收一个比较函数 (A, A) => Boolean，已该函数对集合中的元素进行排序。

示例：

val seq = Seq.fill(10)(Random.nextInt(100))
seq.sorted // 输出：List(28, 36, 42, 43, 63, 66, 69, 84, 85, 88)
seq.sortBy(_ % 10) // 输出：List(42, 63, 43, 84, 85, 66, 36, 88, 28, 69)
seq.sortWith((x, y) => y < x) // 输出：List(88, 85, 84, 69, 66, 63, 43, 42, 36, 28)

1.7 反转操作

1.7.1 reverse & reverseIterator & reverseMap

函数 reverse 用于对 Seq 对象中的元素执行反转操作，而函数 reverseIterator 同样执行反转操作，只是返回的是一个迭代器对象，示例：

1
2
3

val seq = Seq(1 to 5: _*)
seq.reverse // 输出：List(5, 4, 3, 2, 1)
seq.reverseIterator // 输出：<iterator>

函数 reverseMap 相当于 reverse 和 map 的组合，不过执行效率更高，用于对反转的集合执行 map 操作，示例：

1 2	val seq = Seq(1 to 5: _*) seq.reverseMap(_ - 5) // 输出：List(0, -1, -2, -3, -4)

1.8 包含检查

1.8.1 contains & containsSlice

函数 contains 用于检查 Seq 对象是否包含指定单个元素，而函数 containsSlice 用于检查是否包含给定的元素序列，示例：

val seq = Seq(1 to 5: _*)
seq.contains(3) // 输出：true
seq.containsSlice(Seq(1, 2)) // 输出：true
seq.containsSlice(Seq(2, 1)) // 输出：false

1.9 转换操作

1.9.1 transform

对于集合来说一般使用 map 函数执行转换操作，但是对于可变 Seq 对象来说，Scala 还提供了 transform 函数，用于原地转换，示例：

1
2
3

val seq = mutable.Seq(1, 2, 3)
seq.transform(_ * 10)
seq // 输出：ArrayBuffer(10, 20, 30)

1.10 集合运算

1.10.1 intersect

函数 intersect 用于求解两个集合的交集，示例：

1
2
3

val seq1 = Seq(1, 2, 3, 3)
val seq2 = Seq(2, 3, 4, 5)
seq1.intersect(seq2) // 输出：List(2, 3)

注意：如果两个集合包含重复元素，假设该元素在集合 A 中出现 x 次，在集合 B 中出现 y 次，则该元素在交集结果中出现 min(x, y) 次。

1.10.2 union

函数 union 用于求解两个集合的并集，示例：

1
2
3

val seq1 = Seq(1, 2, 3, 3)
val seq2 = Seq(2, 3, 4, 5)
seq1.union(seq2) // 输出：List(1, 2, 3, 3, 2, 3, 4, 5)

并集等价于 ++ 操作。

1.10.3 diff

函数 diff 用于求解两个集合的差集，示例：

1
2
3

val seq1 = Seq(1, 2, 3, 3)
val seq2 = Seq(2, 3, 4, 5)
seq1.diff(seq2) // 输出：List(1, 3)

注意：如果两个集合包含重复元素，假设该元素在集合 A 中出现 x 次，在集合 B 中出现 y 次，则该元素在差集结果中出现 max(0, x - y) 次。

1.11 排列组合

1.11.1 permutations

函数 permutations 用于获取一个 Seq 对象中元素的全排列，示例：

1 2	val seq = Seq(1, 1, 3) seq.permutations.foreach(println)

输出：

1
2
3

List(1, 1, 3)
List(1, 3, 1)
List(3, 1, 1)

注意：如果输入集合中包含重复元素，则在全排列时会出现重复的排列，函数 permutations 会对结果去重。

1.11.2 combinations

函数 combinations 按照顺序从 Seq 对象中选取指定个数的元素进行组合，下面的示例按照顺序每次选择 3 个元素构建组合：

1 2	val seq = Seq(1, 2, 3, 4) seq.combinations(3).foreach(println)

输出：

List(1, 2, 3)
List(1, 2, 4)
List(1, 3, 4)
List(2, 3, 4)

1.12 检查两个序列对应的元素是否满足给定条件

1.12.1 corresponds

函数 corresponds 用于接收一个序列 that 作为参数，并接收一个谓词 (A,B) => Boolean，函数会按照下标对两个集合中的元素逐一比对是否满足给定条件，如果全部满足则返回 true，函数定义如下：

1	def corresponds[B](that: GenSeq[B])(p: (A,B) => Boolean): Boolean

示例：

1
2
3

val seq1 = Seq(1, 2, 3)
val seq2 = Seq.range(2, 7, 2)
seq1.corresponds(seq2)(_ * 2 == _) // 输出：true

二. Buffer

Buffer 是一个可变的序列类（继承自 Seq 特质），其定义如下：

trait Buffer[A] extends Seq[A]
                   with GenericTraversableTemplate[A, Buffer]
                   with BufferLike[A, Buffer[A]]
                   with scala.Cloneable {
  override def companion: GenericCompanion[Buffer] = Buffer
}

Buffer 的子类中最重要的两个类分别是 ListBuffer 和 ArrayBuffer：

ListBuffer ：底层依赖于 immutable.List，以链表的形式实现，对于头部和尾部的操作的时间复杂度是 O(1)，因为内部使用变量保存了长度，所以 length 和 size 操作的时间复杂度也是 O(1)，对于其它操作基本上都是 O(n) 的时间复杂度。
ArrayBuffer ：底层依赖于 ResizableArray 实现，对于尾部操作、更新，以及随机访问操作的时间复杂度都是 O(1)，对于头部和移除操作因为涉及到元素的移动，时间复杂度为 O(n)。

2.1 查询操作

函数 apply 用于从 Buffer 对象中获取指定下标对应的元素值，示例：

1
2
3

val buf = mutable.Buffer(1 to 9: _*)
buf.apply(3) // 输出：4
buf(3) // 输出：4

函数 apply 可以简写为 () 表达式。

2.2 插入操作

2.2.1 +: & :+

函数 +: 和 :+ 用于往 Buffer 对象中添加单个元素，区别在于一个是前置添加，一个是后置添加，示例：

1
2
3

val buf = mutable.Buffer(1, 2, 3)
0 +: buf // 输出：ArrayBuffer(0, 1, 2, 3)
buf :+ 4 // 输出：ArrayBuffer(1, 2, 3, 4)

注意：虽然 Buffer 本身是可变集合，但是考虑一致性，函数 +: 和 :+ 均会返回一个新的集合，而非原地修改。

2.2.2 ++ & ++:

函数 ++ 和 ++: 用于往 Buffer 对象中添加一个集合元素，区别在于一个是前置添加，一个是后置添加，示例：

1
2
3

val buf = mutable.Buffer(1, 2, 3)
buf ++ Seq(4, 5, 6) // 输出：ArrayBuffer(1, 2, 3, 4, 5, 6)
Seq(-2, -1, 0) ++: buf // 输出：ArrayBuffer(-2, -1, 0, 1, 2, 3)

注意：虽然 Buffer 本身是可变集合，但是考虑一致性，函数 ++ 和 ++: 均会返回一个新的集合，而非原地修改。

2.2.3 += & +=: & ++= & ++=:

函数 += 和 +=: 均用于对 Buffer 对象执行原地修改，其中 += 对标 +，而 +=: 对标 +:；函数 ++= 和 ++=: 同样用于对 Buffer 对象执行原地修改，其中 ++= 对标 ++，而 ++=: 对标 ++:。示例：

val buf = mutable.Buffer(1, 2, 3)
buf += 4
0 +=: buf
buf // 输出：ArrayBuffer(0, 1, 2, 3, 4)
buf ++= Seq(6, 7)
Seq(-2, -1) ++=: buf
buf // 输出：ArrayBuffer(-2, -1, 0, 1, 2, 3, 4, 6, 7)

2.2.4 append & appendAll & prepend & prependAll

函数 append 对标 +=，函数 appendAll 对标 ++=；函数 prepend 对标 +=:，函数 prependAll 对标 ++=:，示例：

val buf = mutable.Buffer(1, 2, 3)
buf.append(4, 5)
buf.appendAll(Seq(7, 8))
buf // 输出：ArrayBuffer(1, 2, 3, 4, 5, 7, 8)
buf.prepend(-1, 0)
buf.prependAll(Seq(-3, -2))
buf // 输出：ArrayBuffer(-3, -2, -1, 0, 1, 2, 3, 4, 5, 7, 8)

2.2.5 insert & insertAll

函数 insert 用于将一个或多个元素插入到 Buffer 对象的指定位置，而函数 insertAll 用于将一个集合中的元素插入到 Buffer 的指定位置，示例：

val buf = mutable.Buffer(1, 2, 3)
buf.insert(0, -1, 0)
buf.insertAll(0, mutable.Seq(-3, -2))
buf // 输出：ArrayBuffer(-3, -2, -1, 0, 1, 2, 3)

2.3 更新操作

2.3.1 update

函数 update 用于对 Buffer 对象执行原地修改，示例：

val buf = mutable.Buffer(1 to 9: _*)
buf.update(0, -1)
buf // 输出：ArrayBuffer(-1, 2, 3, 4, 5, 6, 7, 8, 9)
buf(0) = 1
buf // 输出：ArrayBuffer(1, 2, 3, 4, 5, 6, 7, 8, 9)

函数 update 可以使用 () 表达式简写。

2.4 删除操作

2.4.1 - & --

函数 - 用于从 Buffer 对象中移除一个或多个元素，而函数 -- 则接收一个 GenTraversableOnce 类型参数，任何实现了该特质的集合都可以作为参数使用，并从 Buffer 对象中移除集合中给定的所有元素。示例：

val buf = mutable.Buffer(1 to 9: _*)
buf - 1 // 输出：ArrayBuffer(2, 3, 4, 5, 6, 7, 8, 9)
buf - (1, 2) // 输出：ArrayBuffer(3, 4, 5, 6, 7, 8, 9)
buf -- Seq(1, 2, 3) // 输出：ArrayBuffer(4, 5, 6, 7, 8, 9)

注意：

如果 Buffer 包含重复元素，则移除第一个匹配的元素。
虽然 Buffer 本身是可变集合，但是考虑一致性，函数 - 和 -- 均会返回一个新的集合，而非原地修改。

2.4.2 -= & --=

函数 -= 用于从 Buffer 对象中原地移除一个或多个元素，而函数 --= 接收一个 TraversableOnce 类型参数，任何实现了该特质的集合都可以作为参数使用，并从 Buffer 对象中原地移除集合中给定的所有元素。示例：

val buf = mutable.Buffer(1 to 9: _*)
buf -= 1
buf -= (2, 3)
buf --= Seq(4, 5, 6)
buf // 输出：ArrayBuffer(7, 8, 9)

2.4.3 remove

函数 remove 用于从 Buffer 对象中移除给定下标 n 的元素，相应的重载版本允许指定参数 count，用于对指定下标 n 的位置重复执行 count 次删除操作，函数定义如下：

1 2	def remove(n: Int): A def remove(n: Int, count: Int)

示例：

val buf = mutable.Buffer(1 to 9: _*)
buf.remove(0)
buf // 输出：ArrayBuffer(2, 3, 4, 5, 6, 7, 8, 9)
buf.remove(0, 3)
buf // 输出：ArrayBuffer(5, 6, 7, 8, 9)

2.5 剥离（trim）操作

2.5.1 trimStart & trimEnd

函数 trimStart 和 trimEnd 均接收一个参数 n，分别用于从 Buffer 对象的前部移除 n 个元素和从 Buffer 对象的后部移除 n 个元素，示例：

val buf = mutable.Buffer(1 to 9: _*)
buf.trimStart(2)
buf // 输出：ArrayBuffer(3, 4, 5, 6, 7, 8, 9)
buf.trimEnd(2)
buf // 输出：ArrayBuffer(3, 4, 5, 6, 7)

三. List

List 表示具备固定的 不可变链表 结构，同样继承自 Seq 特质，定义如下：

sealed abstract class List[+A] extends AbstractSeq[A]
                                  with LinearSeq[A]
                                  with Product
                                  with GenericTraversableTemplate[A, List]
                                  with LinearSeqOptimized[A, List[A]]
                                  with scala.Serializable

List 中定义了两个样例类 Nil 和 ::，注意不要和 :: 函数混淆，其中 Nil 表示一个空的 List 对象，而 :: 类则用来建立一种链表结构。这两个类的定义如下：

case object Nil extends List[Nothing] {
  override def isEmpty = true
  override def head: Nothing = throw new NoSuchElementException("head of empty list")
  override def tail: List[Nothing] = throw new UnsupportedOperationException("tail of empty list")
  // Removal of equals method here might lead to an infinite recursion similar to IntMap.equals.
  override def equals(that: Any) = that match {
    case that1: scala.collection.GenSeq[_] => that1.isEmpty
    case _ => false
  }
}

final case class ::[B](override val head: B, private[scala] var tl: List[B]) extends List[B] {
  override def tail : List[B] = tl
  override def isEmpty: Boolean = false
}

之所以定义 :: 类，是为了支持模式匹配中的中缀操作模式，从而与 :: 操作符实现统一，示例：

val list = List(1, 2, 3, 4, 5)
list match {
    case a :: b :: c :: tails => println(s"a=$a, b=$b, c=$c, tails=$tails")
    case Nil => println("empty list")
}

输出：

1	a=1, b=2, c=3, tails=List(4, 5)

3.1 插入操作

3.1.1 :: & :::

函数 :: 用于往 List 对象的前部追加元素，而函数 ::: 则用于将两个 List 对象进行连接，示例：

val list = List(3, 4, 5)
1 :: 2 :: list // 输出：List(1, 2, 3, 4, 5)
val list2 = List(6, 7, 8)
list ::: list2 // 输出：List(3, 4, 5, 6, 7, 8)

3.1.2 reverse_:::

函数 reverse_::: 用于对左边的集合反转之后，再与右边的集合执行连接操作，示例：

val list = List(3, 4, 5)
val list2 = List(6, 7, 8)
list reverse_::: list2 // 输出：List(5, 4, 3, 6, 7, 8)
list.reverse_:::(list2) // 输出：List(8, 7, 6, 3, 4, 5)

注意：list reverse_::: list2 等价于 list2.reverse_:::(list)，而不是 list.reverse_:::(list2)。

虽然 list reverse_::: list2 在结果上等价于 list.reverse ::: list2，但是前者效率更高。

四. Stack

栈（stack）是一种后进先出的数据结构，Scala 的 Stack 类在实现上同样继承自 Seq 特质，本质上是一种序列类型，默认采用链表实现。虽然 Stack 也区分可变和不可变，但是常用的还是可变的栈类型（不可变的栈定义已被标记为 @deprecated，因为栈的特性需要频繁被修改，而每次都创建一个新对象的设计，效率较低），定义如下：

class Stack[A] private (var elems: List[A]) extends AbstractSeq[A]
   with Seq[A]
   with SeqLike[A, Stack[A]]
   with GenericTraversableTemplate[A, Stack]
   with Cloneable[Stack[A]]
   with Serializable

4.1 出栈操作

4.1.1 top & pop

函数 top 和 pop 均可用于获取栈顶操作，区别在于 pop 在获取栈顶元素的同时会移除对应的元素，示例：

val stack = mutable.Stack(1, 2, 3)
stack.top // 输出：1
stack // 输出：Stack(1, 2, 3)
stack.pop() // 输出：1
stack // 输出：Stack(2, 3)

如果栈为空，则会抛出 NoSuchElementException 异常。

4.2 入栈操作

4.2.1 push & pushAll

函数 push 用于将一个或多个元素压入栈顶，而函数 pushAll 接收一个 TraversableOnce 类型的集合参数，用于将集合中的所有元素逐一压栈，示例：

val stack = mutable.Stack[Int]()
stack.push(1)
stack.push(2, 3)
stack.pushAll(Seq(4, 5, 6))
stack // 输出：Stack(6, 5, 4, 3, 2, 1)

4.3 更新操作

4.3.1 update

函数 update 用于更新栈指定位置的元素，下标计数从栈顶开始，示例：

1
2
3

val stack = mutable.Stack(1, 2, 3)
stack.update(0, -1)
stack // 输出：Stack(-1, 2, 3)

五. Queue

队列（queue）是一种先进先出的数据结构，Scala 的 Queue 类在实现上同样继承自 Seq 特质，本质上是一种序列类型。虽然 Queue 也区分可变和不可变，但是常用的还是可变的队列类型（不可变队列虽然没有被标记为 @deprecated，但是因为不可变的设计在这种频繁修改的场景下效率较低，所以不建议使用），定义如下：

class Queue[A] extends MutableList[A]
   with LinearSeqOptimized[A, Queue[A]]
   with GenericTraversableTemplate[A, Queue]
   with Cloneable[Queue[A]]
   with Serializable

5.1 出队列操作

5.1.1 front

函数 front 用于从队列中获取头部元素，但是不移除该元素，示例：

1
2
3

val queue = mutable.Queue(1 to 9: _*)
queue.front // 输出：1
queue // 输出：Queue(1, 2, 3, 4, 5, 6, 7, 8, 9)

5.1.2 dequeue & dequeueFirst & dequeueAll

函数 dequeue、dequeueFirst 和 dequeueAll 均用于从队列中获取并移除满足条件的元素，其中 dequeue 用于获取并移除队头元素，而函数 dequeueFirst 和 dequeueAll 均接收一个谓词 A => Boolean 参数，其中 dequeueFirst 用于获取并满足条件的第一个元素，而 dequeueAll 则用于获取并移除满足条件的所有元素。示例：

val queue = mutable.Queue(1 to 9: _*)
queue.dequeue() // 输出：1
queue // 输出：Queue(2, 3, 4, 5, 6, 7, 8, 9)
queue.dequeueFirst(_ % 2 == 1) // 输出：Some(3)
queue // 输出：Queue(2, 4, 5, 6, 7, 8, 9)
queue.dequeueAll(_ % 2 == 0) // 输出：ArrayBuffer(2, 4, 6, 8)
queue // 输出：Queue(5, 7, 9)

5.2 入队列操作

5.2.1 enqueue

函数 enqueue 用于执行入队列操作，可以将一个或多个元素追加到队列尾部，示例：

val queue = mutable.Queue[Int]()
queue.enqueue(1)
queue.enqueue(2, 3)
queue // 输出：Queue(1, 2, 3)