Стеки
Стек — это линейный список, в котором все операции вставки и удаления (и, как правило, операции доступа к данным) выполняются только на одном из концов списка.
Структура такого типа определяет набор правил:
- Элемент, который вставляется последним, удаляется первым - 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))))
Ссылки: