不変なスタック

目次

不変なスタック

もし後入れ先出し列が必要であれば、スタック(Stack)を利用できます。 pushを使うと要素をスタックにプッシュでき、popを使うと要素をポップでき、topを使うとスタックのトップを削除せずに調べられます。 これらの演算は全て定数時間です。

これはスタックに対する単純な演算です:

scala> val stack = scala.collection.immutable.Stack.empty

stack: scala.collection.immutable.Stack[Nothing] = Stack()

scala> val hasOne = stack.push(1)

hasOne: scala.collection.immutable.Stack[Int] = Stack(1)

scala> stack

stack: scala.collection.immutable.Stack[Nothing] = Stack()

scala> hasOne.top

res20: Int = 1

scala> hasOne.pop

res19: scala.collection.immutable.Stack[Int] = Stack()

不変なスタックは機能がリストに包括されるため、Scalaプログラムでは滅多に使われません: 不変なスタックに対するpushはリストに対する::と同じであり、 不変なスタックに対するpopはリストに対するtailと同じです。

続いては: 不変なキュー

不変なスタック

目次