= Solution
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.
\b[All six operations run in $O(1)$ time], with a fixed <array> of `MAX` <integers> and constant extra state. Creating and zero-initializing the <array> takes $O(\mathrm{MAX})$ time, outside those operation bounds. Capacity zero gives a valid always-empty bounded structure whose pushes fail their <precondition>.
Back to article page
