The implementation maintains the two boundaries from part b:
class ArrayDoubleStack(val MAX: Int) extends DoubleStack {
require(MAX >= 0)
private val data = new Array[Int](MAX)
private var left = 0
private var right = MAX
def isEmptya: Boolean = left == 0
def isEmptyb: Boolean = right == MAX
def pusha(x: Int): Unit = {
require(left < right, "double stack is full")
data(left) = x
left += 1
}
def pushb(x: Int): Unit = {
require(left < right, "double stack is full")
right -= 1
data(right) = x
}
def popa: Int = {
require(left > 0, "stack a is empty")
left -= 1
data(left)
}
def popb: Int = {
require(right < MAX, "stack b is empty")
val answer = data(right)
right += 1
answer
}
}Initialization gives empty abstract lists. Each push consumes one free position next to the appropriate top; each pop returns that top and releases its position. The guards preserve the ordering of the two boundaries and prevent invalid indexing. The abstraction function shows directly that the untouched stack is unchanged. Keeping
data private prevents clients from violating the representation invariant; this strengthens encapsulation relative to a publicly exposed implementation field without changing the six required operations.All six operations run in time, with a fixed array of
MAX integers and constant extra state. Creating and zero-initializing the array takes time, outside those operation bounds. Capacity zero gives a valid always-empty bounded structure whose pushes fail their precondition. Articles by others on the same topic
There are currently no matching articles.