如何对Scala不可变队列进行模式匹配？

Question

我想使用immutable.Queue，特别是：

1. 我想访问队列的头部而不弹出它。不可变队列是使用两个不可变列表/堆栈实现的，从代码中看，这个操作似乎不是常数时间（请参见这行代码），尽管弹出是（平摊常数时间）。有人能确认或纠正我吗？

2. 我喜欢List的模式匹配语法（例如，list match { case head :: tail => ... }）。我们是否也有类似于Queue的东西？

- user716468

Answer 1

您可以在Seq上使用通用匹配器+：：

val q = Queue.empty[Int]

q match {
  case x +: xs => // non-empty case
  case _ => // empty case
}

您也可以使用Queue的unapplySeq：

q match {
  case Queue(x, _*) => // non-empty case
  case Queue() => // empty case
}

请注意，这两种方法可能比 Queue.head 更加低效，因为它们必须构造已出队列的队列，而该构造过程仅在摊销时间中为 O(1)。

- gzm0

---

感谢你提供了 +: 的指针。我看到它来自于 SeqExtractors 类。 - user716468

我的第一个问题仍然存在：Queue.head 真的是 O(1) 吗？我修改了我的问题，包括源代码的链接。 - user716468

不，它不是。如果你遇到了你提到的那一行，你将不得不查找 in 列表。像这样的不可变的 dequeue 在摊销 O(1) 的时间内实现，因为你正好对每个元素进行了 enqueue 和 dequeue（这也并不一定正确，可以通过 dequeue 并且舍弃结果队列来实现）。由于你可以多次执行 head，所以你询问的特定 head 可能不会被摊销。 - gzm0

根据您的回复，答案文本关于Queue.head是摊销的O(1)有点不正确。您能修正一下吗？谢谢！ - user716468