Стеки

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

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

Элемент, который вставляется последним, удаляется первым - Last In First Out (LIFO).
Элемент, вставленный первым, покидает стек последним.

Стек — это простая структура данных, удобная для многих операций, требующих упорядочивания или принудительного исполнения. Сложность пространства для n операций push

(протолкнуть) составляет O(n), тогда как средний случай O(1). Точно так же pop (вытолкнуть) и peek (заглянуть) имеют сложность O(1), что верно для isEmpty и isFull.

Оценка:

Заглавный элемент (headOption)
- Время - O(1)
- Память - O(1)
Остаток стека без начального элемента (tailOption)
- Время - O(1)
- Память - O(1)
Проверка стека на пустоту (isEmpty)
- Время - O(1)
- Память - O(1)
Вычисление длины стека (length)
- Время - O(n)
- Память - O(n)
Добавление элемента в стек (push)
- Время - O(1)
- Память - O(1)
Выталкивание элемента из стека (pop)
- Время - O(1)
- Память - O(1)
Получение элемента из стека (peek)
- Время - O(1)
- Память - O(1)

Код:

enum Stack[+A]:
  case EmptyStack
  case NonEmptyStack(value: A, tail: Stack[A])

  lazy val headOption: Option[A] = this match
    case EmptyStack          => None
    case NonEmptyStack(h, _) => Some(h)

  lazy val tailOption: Option[Stack[A]] = this match
    case EmptyStack             => None
    case NonEmptyStack(_, tail) => Some(tail)

  lazy val isEmpty: Boolean = this match
    case EmptyStack          => true
    case NonEmptyStack(_, _) => false

  lazy val length: Int = this match
    case EmptyStack             => 0
    case NonEmptyStack(_, tail) => 1 + tail.length

  def push[B >: A](value: B): Stack[B] = NonEmptyStack(value, this)

  def pop(): Option[(A, Stack[A])] = this match
    case EmptyStack                 => None
    case NonEmptyStack(value, tail) => Some((value, tail))

  def peek(): Option[(A, Stack[A])] = this match
    case EmptyStack              => None
    case NonEmptyStack(value, _) => Some((value, this))

end Stack

Пример:

val emptyStack: Stack[Int]    = EmptyStack
val nonEmptyStack: Stack[Int] = NonEmptyStack(2, NonEmptyStack(1, EmptyStack))
  
emptyStack.headOption         // None
nonEmptyStack.headOption      // Some(2)

emptyStack.tailOption         // None
nonEmptyStack.tailOption      // Some(NonEmptyStack(1,EmptyStack))

emptyStack.isEmpty            // true
nonEmptyStack.isEmpty         // false

emptyStack.length             // 0
nonEmptyStack.length          // 2

emptyStack.push(5)            
// NonEmptyStack(5,EmptyStack)
nonEmptyStack.push(5)
// NonEmptyStack(5,NonEmptyStack(2,NonEmptyStack(1,EmptyStack)))

emptyStack.pop()
// None
nonEmptyStack.pop()
// Some((2,NonEmptyStack(1,EmptyStack)))

emptyStack.peek()
// None
nonEmptyStack.peek()
// Some((2,NonEmptyStack(2,NonEmptyStack(1,EmptyStack))))

Ссылки:

scalabook

Стеки

Использование cookies