Now that we have clearly defined the stack as an abstract data type, we will turn our attention to using Kotlin to implement the stack. Recall that when we give an abstract data type a physical implementation, we refer to the implementation as a data structure.
As we described earlier, in Kotlin, as in any object-oriented programming language, the implementation of choice for an abstract data type such as a stack is the creation of a new class. The stack operations are implemented as member functions. Further, to implement a stack, which is a collection of elements, it makes sense to utilize the power and simplicity of the collections provided by Kotlin. We will a typical Kotlin mutable list.
Recall that a mutable list in Kotlin provides an ordered collection mechanism and a set of methods. For example, if we have the list [2, 5, 3, 6, 7, 4], we need only to decide which end of the list will be considered the top of the stack and which will be the bottom (also referred to as the base of the stack). Once that decision is made, the operations can be implemented using the list methods such as add and remove.
The following stack implementation (Listing 3.5.1) assumes that the end of the list will hold the top element of the stack. As the stack grows (as push operations occur), new items will be added on the end of the list. pop operations will manipulate that same end.
Because we implement this stack using a list, we will name the class ListStack. Every member function that implements something in the interface needs the word override to appear at the beginning of the function definition. This indicates that we are overriding the empty implementation for that function provided in the interface with actual code.
class ListStack<T> : StackADT<T> {
/*
* Create a new stack. The top of the stack is at the end
* of the list.
*/
private val items = mutableListOf<T>()
/*
* Returns true if there are no items on the stack;
* false otherwise.
*/
override fun isEmpty(): Boolean {
return items.isEmpty()
}
/*
* Pushes given item on the top of the stack
*/
override fun push(item: T) {
items.add(item)
}
/*
* Removes the item on top of the stack and returns it.
* If the stack is empty, throws an exception.
*/
override fun pop(): T {
if (isEmpty()) {
throw NoSuchElementException("Stack is empty.")
}
return items.removeLast()
}
/*
* Returns the item on top of the stack without removing it.
* If the stack is empty, throws an exception.
*/
override fun peek(): T {
if (isEmpty()) {
throw NoSuchElementException("Stack is empty.")
}
return items[items.count() - 1]
}
/*
* Returns the number of items on the stack.
*/
override fun size(): Int {
return items.count()
}
/*
* Convert to string as an array from bottom to top
*/
override fun toString(): String {
return items.toString()
}
}
Remember in our discussion of MutableList in Subsection 1.9.1 that we put the data type in angle brackets? This allowed us to have an MutableList<String>, MutableList<Int>, etc. We would also like to be able to create a ListStack whose elements are of any data type. To do this, we specify in line 1 that a stack has a generic data type. The T is like a variable that, instead of holding an integer, double, or string value, holds a data type. Thus, when we create a ListStack<String>, the data type String provides the value that fills in the generic T. The body of the class uses T anywhere that it needs the type of stack we are dealing with.
Now we must write a program that creates a ListStack object and then uses it. Listing 3.5.2 shows the ListStack class in action as we perform the sequence of operations from Section 3.4. We don’t need to import the ListStack class as long as its source file is in the same directory as our test program. (The interactive code in Listing 3.5.2 has been set up properly for this to work.)
It is important to note that we could have chosen to implement the stack using an list where the top is at the beginning instead of at the end. In this case, the previous pop and append methods would no longer work and we would have to index position 0 (the first item in the list) explicitly using remove and add. The implementation is shown in Listing 3.5.3.
class AltListStack<T>: StackADT<T> {
/*
* Create a new stack. The top of the stack is at the end
* of the ArrayList.
*/
private val items = mutableListOf<T>()
/*
* Returns true if there are no items on the stack;
* false otherwise.
*/
override fun isEmpty(): Boolean {
return items.isEmpty()
}
/*
* Pushes given item on the top of the stack
*/
override fun push(item: T) {
items.addFirst(item)
}
/*
* Removes the item on top of the stack and returns it.
* If the stack is empty, throws an exception.
*/
override fun pop(): T {
if (isEmpty()) {
throw NoSuchElementException("Stack is empty.")
}
return items.removeFirst()
}
/*
* Returns the item on top of the stack without removing it.
* If the stack is empty, throws an exception.
*/
override fun peek(): T {
if (isEmpty()) {
throw NoSuchElementException("Stack is empty.")
}
return items[0]
}
/*
* Returns the number of items on the stack.
*/
override fun size(): Int {
return items.count()
}
/*
* Convert to string as an array from bottom to top
*/
override fun toString(): String {
return items.toString()
}
}
This ability to change the physical implementation of an abstract data type while maintaining the logical characteristics is an example of abstraction at work. However, even though the stack will work either way, if we consider the performance of the two implementations, there is definitely a difference. Recall that the add() and removeLast() operations for the end of the list were both \(O(1)\text{.}\) This means that the first implementation will perform push and pop in constant time no matter how many items are on the stack. The performance of the second implementation suffers in that the addFirst and removeFirst operations will both require \(O(n)\) for a stack of size n. Clearly, even though the implementations are logically equivalent, they would have very different timings when performing benchmark testing.
Having these two implementations helps to show the value of using an interface to define the member functions. Consider this short function that randomly chooses which stack to use. (A random choice is silly, but it’s a good way to briefly illustrate the point.)
import kotlin.random.Random
fun main() {
val myStack: StackADT<Int>
if (Random.nextInt(1) == 1) {
myStack = ListStack<Int>()
} else {
myStack = AltListStack<Int>()
}
for (i in 1..20) {
myStack.push(i)
}
for (i in 1..20) {
println(myStack.pop())
}
}
Kotlin uses type inferencing to figure out the type of a variable while the program is compiling, before it begins running. When we enter code such as val x = 3, Kotlin automatically determines that the variable x must be types as an Int because we assign it to an integer. In the above program, however, the type of myStack is unknown until the program starts. Will it be a ListStack, or an AltListStack? Both stack implementations implement StackADT, so we can specify that the type of the variable myStack is StackADT. This is sufficient to allow the program to compile and run, and will work for either implementation.
