# 15.集合：Tuple、Range、Set、Stack和Queue

与前面的集合章节相比，本章介绍的集合类与标准的序列和映射类型略有不同。

_元&#x7EC4;_&#x672C;质上是一个序列，但与类或特质一样，它可以包含任意数量的不同类型的值，如REPL示例所示：

```scala
    scala> (1, 2.2, "a", 'a')
    val res0: (Int, Double, String, Char) = (1, 2.2, a, a)
```

当像这样只需要用一个容器来容纳一系列混合类型的时候，使用元组会十分方便。15.1小节将展示元组的使用方式。

_Rang&#x65;_&#x662F;一个等差的数值或字符序列，通常用于for循环和填充其他集合。15.2小节将介绍它们的用途。

_Se&#x74;_&#x662F;一个仅包含唯一元素的集合，其中唯一性是由集合所包含类型的==方法确定的。由于Set只能包含唯一的元素，所以如果试图向其中添加重复的元素，Set将会忽略这个元素。Scala包含基于Set实现的可变和不可变版本，同时还提供了其他场景的实现类，比如有序的Set。15.3小节到15.5小节将涵盖这些内容。

_Queue_（队列）是一个先进先出的数据结构，_Stack_（栈）是一个后进先出的数据结构。Scala包含每种类型的可变和不可变版本的实现，它们分别在15.6小节和15.7小节中展示。

## 15.1 使用元组创建异构列表

### 问题

你想要创建一个包含异构元素的小集合，并且不想使用**List\[Matchable]**、**List\[Any]**、或者类结构来创建。

### 解决方案

像**Vector**和**ArrayBuffer**这样的集合通常包含一&#x4E2A;_&#x540C;类&#x578B;_&#x5143;素序列，例如 **Vector\[Int]** 或 **ArrayBuffer\[String]**。元组则允许在序列中创建一&#x4E2A;_&#x4E0D;同类&#x578B;_&#x5143;素的集合。

要创建元组，只需将所需的值放在括号内，用逗号分隔。例如，下面的示例展示了如何创建包含两个、三个和四个不同类型值的元组，注释表示所代表的类型:

```scala
    (1, 1.1)           // (Int, Double)
    (1, 1.1, 'a')      // (Int, Double, Char)
    (1, 1.1, 'a', "a") // (Int, Double, Char, String)
```

元组非常适合那些需要少量混杂的异构元素集合的情况。例如，下面是一个返回两个元素元组的方法：

```scala
    // return the user name and age
    def getUserInfo(): (String, Int) =
        // do whatever you need to do to get the data and then
        // return it as a tuple
        ("johndoe", 42)
```

**(String，Int)** 类型展示了如何将元组声明为方法的返回值类型。具体来讲，这个是一个由**String**和**Int**两个元素组成的元组。还可以将该返回类型声明为**Tuple2**，如下所示：

```scala
    def getUserInfo(): Tuple2[String, Int] = ("johndoe", 42)
```

无论使用哪种方法，当调用该方法时，都会创建一个元组变量：

```scala
    val userInfo = getUserInfo() // (String, Int)
```

在Scala 2中，只能使&#x7528;_&#x4E0B;划&#x7EBF;_&#x8BED;法来访问元组元素：

```scala
    userInfo._1 // "johndoe"
    userInfo._2 // 42
```

但在Scala 3中，也可以通过索引号访问元素，就像使用其他序列一样：

```scala
    userInfo(0) // "johndoe"
    userInfo(1) // 42
```

从元组创建变量的另一种常见方法是使用模式匹配将元组值解构为变量。下面示例将“**johndoe**”和**42**分别绑定到变量**name**和**age**：

```scala
    val (name, age) = getUserInfo()
    name // "johndoe"
    age  // 42
```

由于在Scala 3中元组更像列表，所以也有一些常用的集合方法：

```scala
    val t = (1, 2.2, "yo")
    t.size     // 3
    t.head     // Int = 1
    t.tail     // (Double, String) = (2.2,yo)
    t.drop(1)  // (Double, String) = (2.2,yo)
```

还可以连接两个元组：

```scala
    val t = (1, "a") ++ (3.3, 'd') // (Int, String, Double, Char) = (1,a,3.3,d)
```

在两个元素的元组中，还可以使用**swap**方法：

```scala
    val t = (1, 2.2) // (Int, Double) = (1,2.2)
    t.swap           // (Double, Int) = (2.2,1)
```

然而，可以想象，很难在一个元组上实现所有标准的集合方法，因为元组可以包含混合的类型，如**Int**、**Double**和**String**。因此，只有一些有限的方法可以使用。

### 讨论

Scala 3中的元组构建在异构列表（HList）结构之上，该结构最初由Miles Sabin在其shapeless库（ _https://oreil.ly/WGFa3_ ）中基于Scala 2创建。**HList**是一个非常有趣的结构，因为它是序列和类（或至少是record类型）合成的混合物。

#### 元组就像列表

理论上，可以使用隐式或显式类型创建异构元素的序列：

```scala
    val xs = List(1, 2.2, "a", 'b')            // List[Matchable] = List(1, 2.2, a, b)
    val xs: List[Any] = List(1, 2.2, "a", 'b') // List[Any] = List(1, 2.2, a, b)
```

但是，这样会产生丢失类型信息的问题。相反，元组保留了这些细节：

```scala
    (1, 2.2, "a", 'b') // (Int, Double, String, Char) = (1,2.2,a,b)
```

有一个重要的事情是，在Scala 3中，还可以使用以下 **\*:** 语法创建元组：

```scala
    1 *: "a" *: 2.2 *: EmptyTuple // (Int, String, Double) = (1,a,2.2)
```

这有点类似于创建一个列表：

```scala
    1 :: 2 :: Nil // List[Int] = List(1, 2)
```

了解 **\*:** 语法很重要，因为在REPL中使用元组时，会在输出中看到它：

```scala
    scala> val z = (1,2).zip("a", "b")
    val z: (Int, String) *:
      scala.Tuple.Zip[Int *: scala.Tuple$package.EmptyTuple.type, String *:
      scala.Tuple$package.EmptyTuple.type] = ((1,a),(2,b))

    scala> z
    val res0: (Int, String) *: (Int, String) *: EmptyTuple = ((1,a),(2,b))
```

输出的最后一行可以理解为“**res0**是一个元组变量，由一个 **(Int，String)** 元组和另一个 **(Int，String)** 元组组成。”可以看出**res0**是一个元组，因为它由元组类型组成，元组类型用 **\*:** 符号连接在一起，并以**EmptyTuple**结尾。

#### 元组和类

在某些情况下使用元组很方便，因为它们可以替代类，如**getUserInfo**方法所示，该方法返回元组而不是类。与其他Scala功能（如类型推断、并集和交集类型）一样，元组是一种让Scala感觉像一种动态语言的功能。

与类相关的另一个用途是，可以将简单的case类转换为元组，如下所示：

```scala
    // [1] create a case class and instance of it
    case class Stock(symbol: String, price: Double)
    val aapl = Stock("AAPL", 123.45)

    // [2] create a tuple from the case class
    val t = Tuple.fromProductTyped(aapl) // (String, Double) = (AAPL,123.45)
```

将case类转换为元组的好处是，可以编写一个通用的方法来接受任何 **(String, Double)** 类型的元组：

```scala
    def handleTuple(t: (String, Double)): Unit =
        println(s"String: ${t(0)}, Double: ${t(1)}")
```

虽然这是一个简单的例子，但当涉及到泛型编程时，该技术具有显著的优势。请参阅博客文章“Tuples Bring Generic Programming to Scala 3”（ _https://oreil.ly/c2iMJ_ )有关在**case**类和元组之间转换的更多详细信息。

#### 元组和Map

最后，还可以使用两个元素的元组来创建**Map**。这种语法并不常用，但当遇到它时，简单了解下这个可能会有所帮助：

```scala
    val m = Map(
        (1, "a"),
        (2, "b")
    )
```

在相关内容中，还可以使用箭头语法创建两个元素的元组：

```scala
    1 -> "a" // (Int, String) = (1,a)
```

这与创建**Map**时通常使用的箭头语法的作用相同：

```scala
    val m = Map(
        1 -> "a",
        2 -> "b"
    )
```

### 另见

* 博客文章“Tuples Bring Generic Programming to Scala 3”（ _https://oreil.ly/c2iMJ_ )有关在**case**类和元组之间转换的更多详细信息。
* _The Type Astronaut’s Guide to Shapeless_ （ _https://oreil.ly/3qeRJ_ ）以HTML和PDF格式免费提供，描述了由Miles Sabin创建的原始**HList**的使用。

## 15.2 创建Range

### 问题

你需要创建一个值范围，例如在**for**循环中，或者从一个值范围中创建一个数值或字符的序列，通常用于测试目的。

### 解决方案

使用**Int**（或**Char**）类的**to**或**until**方法创建一个包含所需元素的**Range**。然后，如果需要，可以将该**Range**转换为序列。还可以使用序列类（**List**、**Vector**等）的**range**方法来填充创建一个序列。

#### 使用to创建range

使用**to**方法来创建一个**Range**是一个简便的方式：

```scala
    scala> val r = 1 to 5
    r: scala.collection.immutable.Range.Inclusive = Range 1 to 5
```

使用**to**方法时，还可以使用**by**方法设置一个可选的步长（**step**）参数：

```scala
    val r = 1 to 10 by 2 // will contain Range(1, 3, 5, 7, 9)
    val r = 1 to 10 by 3 // will contain Range(1, 4, 7, 10)
```

**Range**通常用于**for**循环：

```scala
    scala> for i <- 1 to 3 do println(i)
    1
    2
    3
```

**Range**是延迟创建的，因此当在REPL中创建一个**Range**时，将看到如下输出：

```scala
    scala> 1 to 10 by 2
    val res0: Range = inexact Range 1 to 10 by 2
```

为了验证**Range**的实际内容，可以使用**toList**、**toVector**等方法将其转换为序列：

```scala
    scala> (1 to 10 by 2).toList
    val res1: List[Int] = List(1, 3, 5, 7, 9)
```

#### 使用until创建range

也可以使用**until**方法来创建一个**Range**：

```scala
    scala> for i <- 1 until 3 do println(i)
    1
    2
```

**until**方法不包括指定的最后一个元素，因此它被认为&#x662F;_&#x5F00;区间（exclusive）_，而**to**方法&#x662F;_&#x95ED;区间（inclusive）_，如以下示例所示：

```scala
    (1 to 3).toVector        // Vector(1, 2, 3)
    (1 until 3).toVector     // Vector(1, 2)
    (1 to 10 by 3).toList    // List(1, 4, 7, 10)
    (1 until 10 by 3).toList // List(1, 4, 7)
```

#### 填充序列

如前所述，一旦有了一个**Range**，就可以把它转换成序列。这是填充序列的常见方法，例如出于测试的目的：

```scala
    (1 to 5).toList       // List[Int] = List(1, 2, 3, 4, 5)
    (1 until 5).toVector  // Vector[Int] = Vector(1, 2, 3, 4)
    (1 to 5).toBuffer     // mutable.Buffer[Int] = ArrayBuffer(1, 2, 3, 4, 5)

    (1 to 5).toSeq        // immutable.Range = Range 1 to 5
    (1 to 5).toSet        // Set[Int] = Set(5, 1, 2, 3, 4)
    (1 to 5).to(LazyList) // LazyList[Int] = LazyList(<not computed>)
```

注意，从注释中显示的结果可以看出，大多数**Range**都转换为实际的序列，而 **toSeq** 和 **to(LazyList)** 是延迟计算的（惰性计算）。

### 讨论

创建一个**Range**时，REPL输出如下所示：

```scala
    scala> val r = 1 to 5
    r: scala.collection.immutable.Range.Inclusive = Range 1 to 5
                                                    ------------
```

通过这种方式，**Range**表现为一个惰性的集合。实际上，可以在REPL中运行此代码，将很快看到REPL输出，并且不会耗尽内存：

```scala
    scala> 1 to 999_999_999
    res0: scala.collection.immutable.Range.Inclusive = Range 1 to 999999999
```

但是，一旦强制将**Range**转换成为序列（例如**Vector**），就会创建元素并消耗内存：

```scala
    scala> (1 to 999_999_999).toVector
    java.lang.OutOfMemoryError: GC overhead limit exceeded
```

如果真的需要一个这么大的列表，您可以创建一个**Range**并将其转换为**LazyList**：

```scala
    scala> (1 to 999_999_999).to(LazyList)
    val res1: LazyList[Int] = LazyList(<not computed>)
```

这种方法几乎立即返回，并且不会为其元素分配内存。你还可以使用其**range**方法创建一个**LazyList**：

```scala
    scala> LazyList.range(1, 999_999_999)
    res1: scala.collection.immutable.LazyList[Int] = LazyList(<not computed>)
```

#### 使用序列的range方法

如**LazyList.range**示例所示，可以使用特定序列类的**range**方法来创建该实例：

```scala
    Vector.range(1, 3)      // Vector(1, 2)
    Array.range(1, 6, 2)    // Array(1, 3, 5)
    List.range(1, 6, 2)     // List(1, 3, 5)

    import collection.mutable.ArrayBuffer
    ArrayBuffer.range(1, 3) // ArrayBuffer(1, 2)
```

结果中不包括第二个参数，因此它的工作方式类似于**until**方法。第三个参数是step步长，默认为**1**：

```scala
    List.range(1, 10)    // List(1, 2, 3, 4, 5, 6, 7, 8, 9)
    List.range(1, 10, 2) // List(1, 3, 5, 7, 9)
    List.range(1, 10, 3) // List(1, 4, 7)
    List.range(1, 10, 4) // List(1, 5, 9)
```

#### Char类型的Range

可以对**Char**类型的值使用以上相同的方法：

```scala
    // 'to' and 'until' are lazy
    'a' to 'e'     // NumericRange a to e
    'a' until 'e'  // NumericRange a until e

    // 'to' is inclusive, 'until' is not
    ('a' to 'e').toList     // List(a, b, c, d, e)
    ('a' until 'e').toList  // List(a, b, c, d)

    // you can also use a step with Char
    ('a' to 'e' by 2).toList  // List(a, c, e)
    ('a' to 'e').by(2).toList // List(a, c, e)
```

***

#### 详情（TODO）

根据背后的原理，由于**Int**和**Char**类上的隐式转换，**to**和**until**方法可用。根据这些类的Scaladoc：

* 对于**Int**类，**to**和**until**方法是“通过隐式转换将**Int**转换到**scala.runtime.RichInt**，由**scala.LowPriorityImplicits**中的方法**intWrapper**执行添加。”
* 对于**Char**类，**to**和**until**方法是“通过隐式转换将**Char**转换到**scala.runtime.RichChar**，由**scala.LowPriorityImplicits**中的方法**charWrapper**执行添加。”

例如，当输入以下部分代码时，表示正在调用**RichInt**类的**to**方法：

```scala
    1 to
```

因此，这两段代码是等效的：

```scala
    1 to 5
    1.to(5)
```

此外，在下面例子中，还可以清楚地看到**to**、**by**和**until**方法的使用：

```scala
    (1 to 10 by 3).toVector     // Vector(1, 4, 7, 10)
    (1 to 10).by(3).toVector    // Vector(1, 4, 7, 10)
    1.to(10).by(3).toVector     // Vector(1, 4, 7, 10)
    1.until(10).by(3).toVector  // Vector(1, 4, 7)
```

***

#### 更多使用Range填充集合的方法

通过使用**Range**的**map**方法，可以使用**Int**或**Char**类型以外的元素创建序列：

```scala
    scala> val x = (1 to 5).map(_ * 2.0)
    val x: IndexedSeq[Double] = Vector(2.0, 4.0, 6.0, 8.0, 10.0)
```

这是一种创建测试样本数据的好方法。使用类似的方法，还可以返回**Tuple2**元素的序列：

```scala
    scala> val x = (1 to 5).map(e => (e,e))
    val x: IndexedSeq[(Int, Int)] = Vector((1,1), (2,2), (3,3), (4,4), (5,5))
```

该序列可以很容易转换为一个**Map**：

```scala
    scala> val map = (1 to 5).map(e => (e,e)).toMap
    val map: Map[Int, Int] = HashMap(5 -> 5, 1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4)
```

关于用数据填充集合的方式，还可以使用**tabulate**和**fill**方法：

```scala
    List.tabulate(3)(_ + 1) // List(1, 2, 3)
    List.tabulate(3)(_ * 2) // List(0, 2, 4)
    List.tabulate(4)(_ * 2) // List(0, 2, 4, 6)
    Vector.fill(3)("a")     // Vector(a, a, a)
```

上述示例展示了**Vector**和**List**类，但它们也适用于**ArrayBuffer**、**Array**和其他集合类。

## 15.3 创建一个Set并添加元素

### 问题

你想要创建一个新的不可变或可变的**set**，并向其中添加元素。

### 解决方案

_Se&#x74;_&#x662F;一个只包含唯一元素的序列。不可变set和可变的set的处理方式是不一样的，下面将用一些例子说明。

#### 不可变Set

以下示例展示了如何创建一个新的不可变**Set**，然后向其中添加元素。首先，创建一个不可变**Set**：

```scala
    val s1 = Set(1, 2) // s1: Set[Int] = Set(1, 2)
```

注意，不需要导入不可变**Set**；默认情况下可用。

与其他不可变集合一样，使用 **+** 和 **++** 方法向不可变**Set**中添加新元素，记得将结果赋值给新变量：

```scala
    // add one element
    val s2 = s1 + 3 // s2: Set(1, 2, 3)

    // add multiple elements from another sequence
    val s3 = s2 ++ List(4, 5) // s3: Set(5, 1, 2, 3, 4)
```

上述示例将字段声明为不可变的**val**，只是为了清楚展示该方法是如何工作的。你还可以将变量声明为**var**，并将结果集重新赋值给同一变量：

```scala
    var s = Set(1, 2)   // s: Set[Int] = Set(1, 2)
    s = s + 3           // s: Set(1, 2, 3)
    s += 4              // s: Set(1, 2, 3, 4)
    s = s ++ List(5, 6) // s: HashSet(5, 1, 6, 2, 3, 4)
```

参阅11.3小节获取有关可变/不可&#x53D8;_&#x53D8;&#x91CF;_&#x548C;可变/不可&#x53D8;_&#x96C6;&#x5408;_&#x4E4B;间差异的更多信息。

#### 可变set

与其他可变集合一样，使用 **+=**、**++=** 和 **add\*** 方法将元素添加到可变集合中：

```scala
    // declare that you want a set of Ints
    val s = scala.collection.mutable.Set[Int]()
        // s: Set[Int] = HashSet()

    // add one element; += is an alias for addOne
    s += 1                   // s: HashSet(1)
    s.addOne(2)              // s: HashSet(1, 2)

    // add multiple elements; ++= is an alias for addAll
    s ++= List(3, 4)         // s: HashSet(1, 2, 3, 4)
    s.addAll(List(5, 6))     // s: HashSet(1, 2, 3, 4, 5, 6)

    // note that there is no error when you attempt to add a duplicate element
    s += 2                   // s: HashSet(1, 2, 3, 4, 5, 6)

    // add elements from any sequence (any IterableOnce)
    s ++= Vector(7, 8)       // s: HashSet(1, 2, 3, 4, 5, 6, 7, 8)

    // the `add` method returns true if the element is added to the set,
    // false otherwise
    val res = s.add(99)      // res=true, s=HashSet(1, 2, 3, 99, 4, 5, 6, 7, 8)
    val res = s.add(1)       // res=false, s=HashSet(1, 2, 3, 99, 4, 5, 6, 7, 8)
```

最后两个示例展示了可变**Set**上**add**方法的一个独特特性：根据元素是否已经被添加，返回true或false。如果试图向**Set**中添加一个已经存在的元素，则其他方法会默默地失败。如有必要，可以在添加元素之前测试是否包含该元素：

```scala
    s.contains(5) // true
```

尽管第一个示例展示了如何创建一个空**Set**，但也可以在声明可变**Set**时向其添加元素，就像其他集合一样：

```scala
    import scala.collection.mutable.Set
    val s = Set(1, 2, 3)
        // s: scala.collection.mutable.Set[Int] = HashSet(1, 2, 3)
```

## 15.4 删除Set中的元素

### 问题

你想要从可变或不可变**Set**中删除元素。

### 解决方案

不可变和可变**Set**的处理方式不同，如以下示例所示。

#### 不可变Set

根据定义，当使&#x7528;_&#x4E0D;可变Se&#x74;_&#x65F6;，不能从其中删除元素，但可以使用常用的 **-** 和 **--** 方法删除元素，同时将结果赋值给新变量：

```scala
    // create an immutable set
    val s1 = Set(1, 2, 3, 4, 5, 6) // s1: Set[Int] = HashSet(5, 1, 6, 2, 3, 4)

    // remove one element
    val s2 = s1 - 1                // s2 == HashSet(5, 6, 2, 3, 4)

    // remove multiple elements defined in another sequence
    val s3 = s2 -- Seq(4, 5)       // s3 == HashSet(6, 2, 3)
```

也可以使用13.7小节中的所有过滤方法。例如，可以使用**filter**、**take**和**drop**等方法：

```scala
    val s1 = Set(1, 2, 3, 4, 5, 6) // s1: Set[Int] = HashSet(5, 1, 6, 2, 3, 4)
    val s2 = s1.filter(_ > 3)      // s2: HashSet(5, 6, 4)

    val s3 = s1.take(2) // s3: HashSet(5, 1)
    val s4 = s1.drop(2) // s4: HashSet(6, 2, 3, 4)
```

但请注意，由于元素在**Set**中的存储顺序取决于其元素的值和数量，因此很少会使用**take**和**drop**等方法：

```scala
    val set = List.range(0, 1_000_000).toSet
    set.take(3) // HashSet(769962, 348877, 864012)
```

根据我的经验，这些方法主要用于提取**Set**的子集以进行测试。

#### 可变Set

使用 **-=** 和 **--=** 方法&#x4ECE;_&#x53EF;变Se&#x74;_&#x4E2D;删除元素，如以下示例所示。首先，创建一个可变**Set**：

```scala
    val s = scala.collection.mutable.Set(1, 1, 1, 2, 3, 4, 5, 6, 7, 8)
    // s: scala.collection.mutable.Set[Int] = HashSet(1, 2, 3, 4, 5, 6, 7, 8)
```

注意，在该示例的结果中，删除了重复的**1**值，因为**Set**仅包含唯一的元素。

现在，你可以使用 **-=** 或者 **subtractOne** 方法删除一个元素：

```scala
    // '-=' is an alias for 'subtractOne'
    s -= 1           // s: HashSet(2, 3, 4, 5, 6, 7, 8)
    s.subtractOne(2) // s: HashSet(3, 4, 5, 6, 7, 8)
```

还可以使用 **--=** 或 **subtractAll** 删除在另一个序列中定义的多个元素：

```scala
    // '--=' is an alias for 'subtractAll'
    s --= List(3,4,5)        // s: HashSet(6, 7, 8)
    s.subtractAll(List(6,7)) // s: HashSet(8)
```

注意，尝试删除不存在的元素不会引发异常，也不会报告错误；可以使用**remove**方法（稍后展示）获取该信息：

```scala
    s -= 99 // s: HashSet(8)
```

对于可变**Set**，可以根据需要使用其他方法，如**FilterPlace**、**clear**和**remove**。下面的例子展示了前两种方法：

```scala
    val s = scala.collection.mutable.Set(1, 2, 3, 4, 5)
    s.filterInPlace(_ > 2)  // s: HashSet(3, 4, 5)
    s.clear                 // s: HashSet()
```

下面的例子表明，如果成功删除元素，**remove**方法返回true，否则返回false：

```scala
    val s = scala.collection.mutable.Set(1, 2, 3, 4, 5)
    val res = s.remove(2)  // res=true, s=HashSet(1,3,4,5)
    val res = s.remove(99) // res=false, s=HashSet(1,3,4,5)
```

## 15.5 按排序顺序在Set中存储值

### 问题

你希望能够按排序顺序将元素存储在**Set**中。

### 解决方案

如果要按排序顺序将元素存储在**Set**中，请使用**SortedSet**，它有不可变和可变两种版本。如果要按插入元素的顺序在**Set**中存储元素，请使用**LinkedHashSet**。

#### SortedSet

**SortedSet**按排序顺序返回元素。下面是两个不可变**SortedSet**的例子：

```scala
    import scala.collection.immutable.SortedSet
    val s = SortedSet(10, 4, 8, 2)         // s: TreeSet(2, 4, 8, 10)
    val s = SortedSet('b', 'a', 'd', 'c')  // s: TreeSet(a, b, c, d)
```

与其他不可变集合一样，可以使用 **+** 和 **++** 等方法添加元素，以及 **-** 和 **--** 删除元素：

```scala
    val s1 = SortedSet(10)     // s1: TreeSet(10)
    val s2 = s1 + 4            // s2: TreeSet(4, 10)
    val s3 = s2 ++ List(8, 2)  // s3: TreeSet(2, 4, 8, 10)
    val s4 = s3 - 8            // s4: TreeSet(2, 4, 10)
    val s5 = s4 -- List(2, 10) // s5: TreeSet(4)
```

#### LinkedHashSet

**LinkedHashSet**是一个可变**Set**，它按元素插入的顺序保存元素：

```scala
    import scala.collection.mutable.LinkedHashSet
    val s = LinkedHashSet(10, 4, 8, 2) // s: LinkedHashSet(10, 4, 8, 2)
```

与其他可变集合一样，可以使用 **+=** 和 **++=** 等方法添加元素，使用 **-=** 和 **--=** 删除元素：

```scala
    val s = LinkedHashSet(10) // s: LinkedHashSet(10)
    s += 4             // s: LinkedHashSet(10, 4)
    s ++= List(8, 2)   // s: LinkedHashSet(10, 4, 8, 2)
    s -= 4             // s: LinkedHashSet(10, 8, 2)
    s --= List(8, 10)  // s: LinkedHashSet(2)

    // attempting to add an element that’s already in the set
    // is quietly rejected
    val s = LinkedHashSet(2) // s: LinkedHashSet(2)
    s += 2                   // s: LinkedHashSet(2)
    s ++= List(2,2,2)        // s: LinkedHashSet(2)
```

### 讨论

解决方案中的例子可以正常运行是因为**Set**中元素的类型有一个隐式的**Ordering**。除非提供隐式的**Ordering**，否则自定义类型将无法工作。参阅12.11小节和13.14小节获取有关如何扩展**scala.math.Ordered**特质的详细信息，或者在排序时提供隐式或显式的**Ordering**。

### 另见

* 参阅12.11小节和13.14小节获取更多关于**Ordered**和**Ordering**特质的信息。
* 参阅Scaladoc中**SortedSet**特质（ _https://oreil.ly/QrkNe_ ）的其他实现类。

## 15.6 创建和使用栈

### 问题

你想要在Scala应用程序中使用后进先出（LIFO）的数据结构。

### 解决方案

栈（Stack）是一个后进先出的数据结构。在大多数编程语言中，使用**push**方法将元素添加到栈中，并使用**pop**将元素从栈中移除，Scala也不例外。

Scala包含栈的不可变和可变版本；下面的例子展示了如何使用 _可变_ **Stack** 类。

创建一个空的可变栈：

```scala
    import scala.collection.mutable.Stack
    val ints = Stack[Int]()
    val strings = Stack[String]()
```

创建栈时，还可以使用元素进行填充：

```scala
    val chars = Stack('a', 'b', 'c')    // Stack[Char] = Stack(a, b, c)
    val ints = Stack(1, 2, 3)           // Stack[Int] = Stack(1, 2, 3)
    val ints: Stack[Int] = Stack(1,2,3) // Stack[Int] = Stack(1, 2, 3)
```

一旦有了一个可变栈，就可以使用**push**方法将元素放到栈的顶部：

```scala
    import scala.collection.mutable.Stack
    val s = Stack[String]() // s: Stack[String] = Stack()

    // add one element at a time
    s.push("a")             // s: Stack(a)
    s.push("b")             // s: Stack(b, a)

    // add multiple elements
    s.push("c", "d")        // s: Stack(d, c, b, a)
```

要从栈中删除元素，可以使用**pop**方法将其从栈顶部弹出：

```scala
    val next = s.pop // next=d, s=Stack(c, b, a)
```

可以使用**top**方法查看栈的下一个元素，而不用删除它：

```scala
    val top = s.top // top=c, s=Stack(c, b, a)
```

但是要小心使用**pop**和**top**方法，因为如果栈为空，它们会抛出**java.util.NoSuchElementException**。

可以使用**clear**或**clearAndShrink**方法清空可变栈：

```scala
    // creates a stack from 0 to 999_999
    val nums = Stack.range(0, 1_000_000)
    nums.clear             // nums: Stack[String] = Stack()
    nums.clearAndShrink(0) // nums: Stack[String] = Stack()
```

**clear**方法将删除所有元素，但不会调整栈的内部大小。**clearAndShrink**方法将内部表示的大小减小到你指定的值。

### 讨论

我看到一些人建议在这个例子中使用**List**，而不是不可变栈。**List**至少会减少一层代码，你可以使用 **::** 将元素推到**List**顶部，也可以使用**head**和**headOption**等方法访问第一个元素。

#### 其他方法

与其他集合类一样，**Stack**有很多其他方法，包括：

```scala
    val s = Stack("apple", "banana", "kiwi")
    s.size                 // 3
    s.isEmpty              // false
    s.count(_.length > 4)  // 2
    s.filter(_.length > 4) // Stack(apple, banana)
```

在任何编程语言中，栈结构通常具有**push**和**pop**方法，表15-1展示了Scala中**Stack**可用的一些push/pop方法。

_Table 15-1. Scala中Stack的push和pop方法_

| 方法       | 描述                  |
| -------- | ------------------- |
| pop      | 删除并返回顶部元素           |
| popAll   | 删除并使用**Seq**返回所有元素  |
| popWhile | 删除所有条件为true的元素      |
| push     | 将一个或多个元素添加到栈的顶部     |
| pushAll  | 将可遍历集合中的所有元素添加到栈的顶部 |

下面的例子展示了这些方法的工作原理：

```scala
    val s = Stack[Int]() // s: collection.mutable.Stack[Int] = Stack()
    s.push(1)                 // s: Stack(1)
    s.push(2,3)               // s: Stack(3, 2, 1)
    s.pushAll(List(4,5))      // s: Stack(5, 4, 3, 2, 1)
    val a = s.pop             // a=5, s=Stack(4, 3, 2, 1)
    val b = s.popWhile(_ > 2) // b=List(4, 3), s=Stack(2, 1)
    val c = s.popAll          // c=List(1, 2), s=Stack()
```

#### Stack继承ArrayDeque（TODO：乌鸦图）

从Scala 2.13开始，可变**Stack**类继承**ArrayDeque**类（ _https://oreil.ly/78WdF_ ），根据Scaladoc，“Append, prepend, removeFirst, removeLast，随机方法（按索引访问和按索引替换）都是常量时间复杂度。一般来书，在索引为 **i** 的位置删除和插入的时间复杂度是**O(min(i, n-i))**，因此，从结束/开始的位置插入和删除元素很快。”

## 15.7 创建和使用队列

### 问题

你想要在Scala应用程序中创建和使用先进先出（FIFO）的数据结构。

### 解决方案

队列是一种先进先出（FIFO）的数据结构，Scala提供了不可变和可变版本。解决方案将展示可变队列的使用，讨论中将简要介绍不可变队列的使用。

创建一个空的可变队列：

```scala
    import scala.collection.mutable.Queue
    val q = Queue[Int]()
    val q = Queue[String]()
```

也可以在创建队列的时候初始化元素：

```scala
    val q = Queue(1, 2, 3) // q: Queue[Int] = Queue(1, 2, 3)
```

一旦有了一个可变队列，就可以使用 **+=**、**++=**、**enqueue**和**enqueueAll**方法向其添加元素，如下面的例子所示：

```scala
    import scala.collection.mutable.Queue
    val q = new Queue[String] // q: collection.mutable.Queue[String] = Queue()

    // add elements to the queue
    q += "a" // q: Queue(a)
    q ++= List("b", "c") // q: Queue(a, b, c)
    q.enqueue("d") // q: Queue(a, b, c, d)
    q.enqueue("e", "f") // q: Queue(a, b, c, d, e, f)
    q.enqueueAll(List("g", "h")) // q: Queue(a, b, c, d, e, f, g, h)
```

注意，新元素被添加到队列的末尾。由于队列是FIFO，因此通常使用**dequeue**方法从队列头部移除元素，每次移除一个元素：

```scala
    import scala.collection.mutable.Queue
    val q = Queue(1, 2, 3) // q: mutable.Queue[Int] = Queue(1, 2, 3)

    // take an element from the head of the queue
    val next = q.dequeue // next=1, q=Queue(2, 3)
    val next = q.dequeue // next=2, q=Queue(3)
    val next = q.dequeue // next=3, q=Queue()

    // `q` is now empty; beware calling dequeue on an empty Queue:
    val next = q.dequeue
        // result: java.util.NoSuchElementException: empty collection
```

还可以使用**dequeueFirst**和**dequeueAll**方法通过指定条件从队列中删除元素：

```scala
    import scala.collection.mutable.Queue
    val q = Queue(1,2,3,4,5) // q: Queue(1, 2, 3, 4, 5)

    // found the number 3, so remove it from the queue
    val res = q.dequeueFirst(_ > 2) // res=Some(3), q=Queue(1, 2, 4, 5)

    // no matches
    val res = q.dequeueFirst(_ > 5) // res=None, q=Queue(1, 2, 4, 5)

    // match three elements, remove them from the queue
    val res = q.dequeueAll(_ > 1) // res=List(2, 4, 5), q=Queue(1) 

    // no matches
    val res = q.dequeueAll(_ > 1) // res=List(), q=Queue(1)
```

### 讨论

与其他集合类一样，队列类有很多其他方法，包括：

```scala
    import scala.collection.mutable.Queue
    val q = Queue(1,2,3,4,5)
    q.size // 5
    q.isEmpty // false
    q.count(_ > 3) // 2
    q.filter(_ > 3) // Queue(4, 5)
```

#### 不可变队列

使用不可变队列时，通常使用**enqueue**和**enqueueAll**方法添加元素，使用**dequeue**方法删除元素：

```scala
    import scala.collection.immutable.Queue

    val q1 = Queue[Int]()   // q1: Queue[Int] = Queue()
    val q2 = q1.enqueue(1)  // q2: Queue(1)
    val q3 = q2.enqueueAll(List(2,3)) // q3: Queue(1, 2, 3)

    val (a, q4) = q3.dequeue // a=1, q4=Queue(2, 3)
    val (b, q5) = q4.dequeue // b=2, q5=Queue(3)
    val (c, q6) = q5.dequeue // c=3, q6=Queue()

    // `q6` is now empty; beware calling dequeue on an empty queue:
    val (d, q7) = q6.dequeue
        // result: java.util.NoSuchElementException: dequeue on empty queue
```

如上述示例所示，请记住将结果分配给一个新变量，因为不可变队列中的数据无法修改。
