Two Stack using single Array in Kotlin

by

Two stacks in one array is a technique that allows us to implement two separate stacks in a single array by dividing the array into two halves and treating each half as a separate stack. In this approach, we maintain two pointers to keep track of the top elements of each stack, and push and pop elements from each stack using these pointers.

In the example given, the TwoStacks class implements two stacks in a single array by dividing the internal array into two halves and using the first half for stack 1 and the second half for stack 2. The push1 and pop1 operations for stack 1 are implemented using the top1 pointer, which starts at -1 and increases by 1 with each push and decreases by 1 with each pop. Similarly, the push2 and pop2 operations for stack 2 are implemented using the top2 pointer, which starts at the end of the array (i.e., the length of the array) and decreases by 1 with each push and increases by 1 with each pop.

implementation of a two-stack data structure using a single Kotlin array:

Kotlin
class TwoStacks(val capacity: Int) {
    private val array = arrayOfNulls<Any>(capacity)
    private var top1 = -1 // index of top element of stack 1
    private var top2 = capacity // index of top element of stack 2

    fun push1(value: Any) {
        if (top1 + 1 >= top2) {
            throw IllegalStateException("Stack overflow")
        }
        top1++
        array[top1] = value
    }

    fun push2(value: Any) {
        if (top2 - 1 <= top1) {
            throw IllegalStateException("Stack overflow")
        }
        top2--
        array[top2] = value
    }

    fun pop1(): Any {
        if (top1 < 0) {
            throw NoSuchElementException("Stack underflow")
        }
        val value = array[top1]
        array[top1] = null
        top1--
        return value!!
    }

    fun pop2(): Any {
        if (top2 >= capacity) {
            throw NoSuchElementException("Stack underflow")
        }
        val value = array[top2]
        array[top2] = null
        top2++
        return value!!
    }

    fun peek1(): Any? {
        return if (top1 >= 0) {
            array[top1]
        } else {
            null
        }
    }

    fun peek2(): Any? {
        return if (top2 < capacity) {
            array[top2]
        } else {
            null
        }
    }
}
fun main() {
    val twoStacks = TwoStacks(6)

    // Push some values onto stack 1
    twoStacks.push1("A")
    twoStacks.push1("B")
    twoStacks.push1("C")

    // Push some values onto stack 2
    twoStacks.push2(1)
    twoStacks.push2(2)
    twoStacks.push2(3)

    // Pop some values from stack 1
    println(twoStacks.pop1()) // Output: C
    println(twoStacks.pop1()) // Output: B

    // Pop some values from stack 2
    println(twoStacks.pop2()) // Output: 3
    println(twoStacks.pop2()) // Output: 2

    // Push more values onto stack 1
    twoStacks.push1("X")
    twoStacks.push1("Y")
    twoStacks.push1("Z")

    // Peek at the top elements of both stacks
    println(twoStacks.peek1()) // Output: Z
    println(twoStacks.peek2()) // Output: 1
}
  • The TwoStacks class is defined with a constructor that takes a single parameter capacity, which represents the maximum size of both stacks combined.
  • The array property is initialized with an array of capacity elements, all initially set to null.
  • The top1 and top2 properties are initialized to -1 and capacity, respectively. These properties represent the index of the top element in each stack.
  • The push1 method takes a value and adds it to the first stack. It first checks if there is enough space in the array to add the value by comparing the index of the top element of the first stack (top1) with the index of the top element of the second stack (top2). If there is not enough space, it throws an IllegalStateException. Otherwise, it increments top1, sets the value at that index in the array, and returns nothing.
  • The push2 method takes a value and adds it to the second stack. It first checks if there is enough space in the array to add the value by comparing the index of the top element of the first stack (top1) with the index of the top element of the second stack (top2). If there is not enough space, it throws an IllegalStateException. Otherwise, it decrements top2, sets the value at that index in the array, and returns nothing.
  • The pop1 method removes and returns the top element of the first stack. It first checks if the first stack is not empty by checking if the index of the top element of the first stack (top1) is greater than or equal to 0. If it is empty, it throws a NoSuchElementException. Otherwise, it gets the value at the index top1 in the array, sets that index to null, decrements top1, and returns the value.
  • The pop2 method removes and returns the top element of the second stack. It first checks if the second stack is not empty by checking if the index of the top element of the second stack (top2) is less than the capacity of the array. If it is empty, it throws a NoSuchElementException. Otherwise, it gets the value at the index top2 in the array, sets that index to null, increments top2, and returns the value.
  • The peek1 method returns the top element of the first stack without removing it. It first checks if the first stack is not empty by checking if the index of the top element of the first stack (top1) is greater than or equal to 0. If it is empty, it returns null. Otherwise, it returns the value at the index top1 in the array.
  • The peek2 method returns the top element of the second stack without removing it. It first checks if the second stack is not empty by checking if the index of the top element of the second stack (top2) is less than the capacity of the array. If it is empty, it returns null. Otherwise, it returns the value at the index top2 in the array.

Main Function:

  1. A new instance of the TwoStacks class is created with a capacity of 6, which creates an internal array of size 6 and initializes the two stack pointers top1 and top2 to -1 and 6 respectively.
  2. Three strings (“A”, “B”, and “C”) are pushed onto stack 1 using the push1 method.
  3. Three integers (1, 2, and 3) are pushed onto stack 2 using the push2 method.
  4. The top two elements of stack 1 are popped and printed using the pop1 method.
  5. The top two elements of stack 2 are popped and printed using the pop2 method.
  6. Three more strings (“X”, “Y”, and “Z”) are pushed onto stack 1 using the push1 method.
  7. The top elements of both stacks are peeked at and printed using the peek1 and peek2 methods.

The time complexity of the main function for the TwoStacks class is O(1) for all the operations being performed. This is because all the operations such as push, pop, and peek are implemented using simple array operations, and do not involve any loops or recursion that depend on the size of the input.

The space complexity of the TwoStacks class itself is O(n), where n is the capacity of the internal array used to implement the two stacks. However, the main function only uses a fixed amount of space to create the TwoStacks instance and perform the operations, which is independent of the input size. Therefore, the space complexity of the main function is also O(1) in this case.

Leave a Comment