Очереди

Очередь или односторонняя очередь — это линейный список, в котором все операции вставки выполняются на одном из концов списка, а все операции удаления (и, как правило, операции доступа к данным) — на другом.

По отношению к очередям применяют понятия начало (front) и конец (rear) очереди.

Структура такого типа определяет набор правил:

• Элемент, который вставляется первым, удаляется первым - First in First Out (FIFO).
• Элемент, вставленный последним, покидает очередь последним.

Временная сложность вставки и удаления элемента в очередь составляет O(1).

В Scala присутствует стандартная релизация очереди, описанная в соответствующем разделе.

Оценка:

• Первый элемент очереди (frontOption
  )
  • Время - O(1)
  • Память - O(1)
• Конец очереди (rearOption
  )
  • Время - O(1)
  • Память - O(1)
• Проверка очереди на пустоту (isEmpty
  )
  • Время - O(1)
  • Память - O(1)
• Добавление элемента в очередь (enqueue
  )
  • Время - O(1)
  • Память - O(1)
• Удаление элемента из очереди (dequeue
  )
  • Время - O(1)
  • Память - O(1)

Код:

final class Queue[+A](in: List[A], out: List[A]):
  def frontOption: Option[A] = dequeue.map(_._1)

  def rearOption: Option[Queue[A]] = dequeue.map(_._2)

  lazy val isEmpty: Boolean = in.isEmpty && out.isEmpty

  def enqueue[B >: A](x: B): Queue[B] = Queue(x :: in, out)

  def dequeue: Option[(A, Queue[A])] = out match
    case hd :: tl => Some((hd, Queue(in, tl)))
    case Nil => in.reverse match
        case hd :: tl => Some((hd, Queue(Nil, tl)))
        case Nil      => None

object Queue:
  def empty[A]: Queue[A] = Queue(Nil, Nil)

Пример:

val emptyQueue: Queue[Int]    = Queue.empty[Int]
val nonEmptyQueue: Queue[Int] = emptyQueue.enqueue(1).enqueue(2)

emptyQueue.frontOption    // None
nonEmptyQueue.frontOption // Some(1)

emptyQueue.rearOption     // None
nonEmptyQueue.rearOption  // Some(Queue(2))
 
emptyQueue.isEmpty)       // true
nonEmptyQueue.isEmpty)    // false

emptyQueue.enqueue(5))    // Queue(5)
nonEmptyQueue.enqueue(5)) // Queue(1,2,5)

emptyQueue.dequeue)       // None
nonEmptyQueue.dequeue)    // Some((1,Queue(2)))

Ссылки:

• Donald E. Knuth - The Art of Computer Programming, section 2.2.1
• Bhim P. Upadhyaya - Data Structures and Algorithms with Scala
• Scalacaster - Queue