LinkedListStack impl
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
object Main extends App {
case class Node(item: String, next: Option[Node])
class FixedCapacityStack(capacity: Int = 0){
val s = Array.fill[String](capacity){""}
var n = 0
def isEmpty: Boolean = n == 0
def push(item: String): Unit = {
s(n) = item
n = n + 1
}
def pop(): String = {
n = n - 1
val item = s(n)
s(n) = null
item
}
}
class ResizingArrayStack(capacity: Int = 0){
var s: Array[String] = Array.fill[String](capacity){""}
var n = 0
def isEmpty: Boolean = n == 0
def push(item: String): Unit = {
if (n == s.length) resize(2 * s.length)
s(n) = item
n = n + 1
}
def pop(): String = {
n = n - 1
val item = s(n)
s(n) = null
if (n > 0 && n == s.length/4) resize(s.length/2)
item
}
def resize(capacity: Int): Unit = {
val copy = Array.fill[String](capacity){""}
for (i <- 0 until n){
copy(i) = s(i)
}
s = copy
}
}
class LinkedListCustom {
var first:Option[Node] = None
def isEmpty(): Boolean = first.isEmpty
def push(item: String)= {
val formerFirst = first
first = Some(Node(item, formerFirst))
}
def pop(): String = {
val res = first.map(_.item)
first = first.flatMap(_.next)
res.getOrElse("")
}
}
val l = new ResizingArrayStack(20)
for (n <- 0 until 100) {
l.push(n.toString)
}
for (n <- 0 until 100) {
println(l.pop())
}
}
Scala
INFO