Back to Lesson 8

Exercise 1: Implementing a stack using a list

Consider the following interface for the Stack ADT:

interface Stack {
    fun push(item: Int)
    fun pop(): Int
    fun peek(): Int
    fun isEmpty(): Boolean
}

Write a class ListStack that implements this interface using a MutableList as its underlying data store.

Here is a main function you could use to test your code:

fun main() {
    val s = ListStack()
    s.push(2025)
    s.push(4)
    s.push(16)
    
    println("Elements present in stack: ")
    println(s)
    
    println("" + s.pop() + " popped from stack")
    println("Top element is: " + s.peek())

    println("Elements present in stack: ")
    println(s)
}

Back to Lesson 8

Exercise 2: Implementing a stack using an array

Deep under the hood, all lists are actually built on the array data type. They’re tricky to work with, though, because they have a fixed size (so you can’t make it any bigger – instead, you have to copy all elements to a new, bigger array).

You can make a new array that holds 10 Ints, with all values initially null (signifying that you don’t have a valid value in those elements), using the arrayOfNulls function:

    val myarr: Array<Int?> = arrayOfNulls<Int>(10)

Once you have an array, you can access/modify elements using square brackets (e.g., myarr[2]) and get the number of elements (some of which may be null) with .count() (like myarr.count()).

Write a class ArrayStack that implements this interface using an Array<Int?> as its underlying data store.

Here is a main function you could use to test your code:

fun main() {
    val s = ArrayStack()
    s.push(2025)
    s.push(4)
    s.push(16)

    println("Elements present in stack: ")
    for (elt in s) {
        if (elt != null) {
            println(elt)
        }
    }

    println("" + s.pop() + " popped from stack")
    println("Top element is: " + s.peek())

    println("Elements present in stack: ")
    for (elt in s) {
        if (elt != null) {
            println(elt)
        }
    }
}

Back to Lesson 8

Exercise 3: Validating proper nesting

We can say that a sequence of operations (for example, lock/unlock requests) is “properly nested” we complete requests in the reverse order that we start them. For example, the following are properly nested sequences (assuming the first occurrence of a letter marks the start and the second marks the end for that pair):

• AA
• ABBA
• ABCCBA
• ABBCCA

However, the following are not properly nested sequences:

• ABAB
• ABCACB

How could you use a stack to determine whether a given input string is properly nested? Try to write some code to solve this!

Back to Lesson 8