Stacks
Stack is a data structure that can perform a part of the operation that lists can. We can take only the last element appended to the stack. The operation taking out the element is called "pop", and appending the element is called "push". It sounds like there is no use for stacks, however, stacks can perform those operations more efficiently than lists. This is another kind of tradeoff we saw for lists. Analogous to lists, stacks can be implemented as array-based and linked-stack. And the implementations are quite simple.
Stack ADT
trait StackADT[E] {
def clear: Unit
def push(item: E): Unit
def pop: E
def peek: E
def length: Int
}
Array-based stack
import scala.reflect.ClassTag
class AStack[E: ClassTag](size: Int = 10) extends StackADT[E] {
private val maxSize: Int = size
private var top: Int = 0
private val listArray: Array[E] = new Array[E](maxSize)
def clear: Unit = top = 0
def push(item: E): Unit = {
assert (top != maxSize)
listArray(top) = item
top += 1
}
def pop: E = {
assert (top != 0)
top -= 1
listArray(top)
}
def peek: E = {
assert (top != 0)
listArray(top - 1)
}
def length: Int = top
}
// the same as Link for linked list
class Link[E](item: Option[E], nextVal: Option[Link[E]]) {
private var linkElement: Option[E] = item
private var nextLink: Option[Link[E]] = nextVal
def next: Option[Link[E]] = nextLink
def setNext(nextVal: Option[Link[E]]): Unit = nextLink = nextVal
def element: Option[E] = linkElement
def setElement(item: Option[E]): Unit = linkElement = item
}
class LStack[E](size: Int = 0) extends StackADT[E] {
// ignore the input size which is there for the consistency with AStack
private var top: Option[Link[E]] = None
private var stackSize: Int = 0
def clear: Unit = {
top = None
stackSize = 0
}
def push(item: E): Unit = {
top = Some(new Link[E](Some(item), top))
stackSize += 1
}
def pop: E = {
assert (top.isDefined)
val item: E = top.get.element.get
top = top.get.next
stackSize -= 1
item
}
def peek: E = {
assert (top.isDefined)
top.get.element.get
}
def length: Int = stackSize
}
Comparison of stack implementations
As mentioned above, stacks are efficient for what they can do. As for time complexity, it is obvious from implementations that they do all the operation in $\Theta(1)$ time. Space complexity is the same as the list for each implementation.
Imitating recursion
Recursive call of functions in a program is managed using a stack. When a subroutine is called, the program push the necessary information onto the stack, and when it returns, the information is popped from the stack. Therefore, we can replace the recursion with a iteration with stack. As an example, I will show an implementation of the algorithm to solve Tower of Hanoi problem with iteration and stack.
Tower of Hanoi
object Operation extends Enumeration {
type Operation = Value
val CALL, MOVE = Value
}
import Operation._
case class TOH(operation: Operation, size: Int, start: Int, goal: Int, temp: Int) {
def this(size: Int, start: Int, goal: Int, temp: Int) = this(CALL, size, start, goal, temp)
def this(size: Int, start: Int, goal: Int) = this(MOVE, size, start, goal, -1)
def move() = println(s"Move ring $size from pole $start to pole $goal")
}
def solveTOH(height: Int): Unit = {
val stack = new AStack[TOH](2 * height + 1)
stack.push(new TOH(height, 1, 2, 3))
while(stack.length > 0) {
val item: TOH = stack.pop
item.operation match {
case MOVE => item.move
case CALL if item.size > 0 => {
stack.push(new TOH(item.size - 1, item.temp, item.goal, item.start))
stack.push(new TOH(item.size, item.start, item.goal))
stack.push(new TOH(item.size - 1, item.start, item.temp, item.goal))
}
case _ =>
}
}
}
solveTOH(3)