实现更有效的队列

Question

type Queue[A] = List[A]

    def enqueue[A](e: A, queue: Queue[A]): Queue[A] = queue match {
    case Nil => List(e)
    case head :: tail => head :: enqueue(e, tail)
    } 

    def dequeue[A](queue: Queue[A]): Option[(A, Queue[A])] = queue match {
    case Nil => None()
    case head :: tail => Some((head, tail))
    }

我想看看我是否在正确的轨道上，或者有没有更有效的方法来实现这一点？

Answer 1

从标准库队列的源：

队列对象实现的数据结构允许：

• 以先进先出(FIFO)的方式插入和检索元素。
• 队列实现为一对列表，其中一个包含“in”元素，另一个包含“out”元素。
• 元素被添加到“in”列表中，并从“out”列表中删除。当“out”列表枯竭时，队列将通过将“out”列表替换为“in.reverse”，将“in”替换为“nil”来旋转。
• 向队列中添加项总是具有成本O(1)。移除项的成本O(1)，但在需要透视的情况下除外，在这种情况下，成本为O(n)，其中n是队列中的元素数。
• 发生这种情况时，保证n具有O(1)开销的删除操作。删除一项平均O(1).