Stack in Kotlin

A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle.

A stack is a limited access data structure - elements can be added and removed from the stack only at the top.

The push operation adds an element at the top of the stack, and the pop operation removes an element from the top of the stack.

Imagine if you were looking at a stack of books. Whenever you wanted to add a book to the stack, it would be very easy to put it on top. Likewise, if you wanted to grab a book from the stack, it would be very easy just to grab the book on top. stack-in-kotlin

Common methods in Stack data structure in kotlin :

  • push : push an element onto the Stack
  • pop : pop an element off the Stack, i.e. the Top element
  • peek : "peek" at the very top element, i.e. return the Top element
  • isEmpty : return a boolean that determines whether the Stack is currently empty or not
  • size : return the current size of our Stack

Day to day life Usage :

  • Open and closing the curly braces problem in programs
  • Going back in browser history
  • An "undo" mechanism in text editors; this operation is accomplished by keeping all text changes in a stack.
  • A stack of plates/books in a cupboard.
  • etc[end of thinking capacity]

Stack implementation using List in Kotlin

We can implement the Stack data structure in different ways in kotlin, but in section we are going to see how to implement the Stack in kotlin using the list.

First let's create a Mutable list in kotlin to create the stack, we will be using this list to perform like stack. We can accept some values through the constructor and we can use as initial values if we want.


val elements: MutableList<Any> = mutableListOf()	

isStackEmpty :

isStackEmpty() function will check whether the Stack has any elements, if any element is there then isStackEmpty() function return true otherwise false.

We will be using the isEmpty() function from the list to check whether any element s there in the list, in terms we are checking in Stack as well.

I have used isStackEmpty() for avoiding confusion with isEmpty() function from the list

fun isStackEmpty() = elements.isEmpty()

size :

size() method will return number of elements present in the Stack, we are achieving this using the size property from the list


fun size() = elements.size	

push :

The push function adds an element to the Stack in kotlin, we will be using the add() function from the list internally


fun push(item: Any) = elements.add(item)	

pop :

Pop function removes and return the item/element which got added newly. Using lastOrNull() function from the list, we can get the last elements, which means latest addition if there is not elements then lastOrNull() function return null.

lastOrNull() function just fetches the last value but it will not remove the element from the Stack if it is not empty. So we have to remove the element by checking whether the Stack is empty or not.


fun pop() : Any? {
	val item = elements.lastOrNull()
	if (!isEmpty()){
		elements.removeAt(elements.size -1)
	}
	return item
} 		

peek :

As I explained in pop() function, the lastOrNull() can be used to check the latest addition, if there are no elements then it returns null


fun peek() : Any? = elements.lastOrNull()	

Complete example for creating the Stack in kotlin using the List


class StackWithList{
    val elements: MutableList<Any> = mutableListOf()

    fun isEmpty() = elements.isEmpty()

    fun size() = elements.size

    fun push(item: Any) = elements.add(item)

    fun pop() : Any? {
        val item = elements.lastOrNull()
        if (!isEmpty()){
            elements.removeAt(elements.size -1)
        }
        return item
    }
    fun peek() : Any? = elements.lastOrNull()

    override fun toString(): String = elements.toString()
}

fun main(args: Array<String>) {
    var stacklist  = StackWithList()
    println("is Stack empty : "+stacklist.isStackEmpty())
    stacklist.push("karthiq")
    println("peek is : " +stacklist.peek())
    stacklist.push(false)
    stacklist.push(5)
    stacklist.push(12.22)
    println("the pop elements is : " +stacklist.pop())
    println("the size is : " +stacklist.size())
    println("is Stack empty : " +stacklist.isStackEmpty())
}

Stack implementation using Arrays in Kotlin

We can implement the stacks using the arrays in kotlin, the idea is behind the implementation is create new arrays and move the old array values when the old array is full.

We need variable to keep the track of the size and index that currently we are pointing at.

  • stackSize : this variables is used to keep the track for array size, this is useful while creating new arrays
  • stackArr : Our array which will act as Stack in the program, this will be assigned with new arrays when old array is full
  • top : This variable keeps track of the index, this will increased or decreased based on the Push and Pop operations receptively

private var stackSize = size;
private var stackArr = IntArray(stackSize);
private var top = -1;

push() function adds the element to the array, before adding the element we make sure that array has space for new element.

If array does not have space for new element, then we create new array and move old array element to new array using increaseStackCapacity function.

Once we have/get the space we can assign the received value to the index, the index is nothing but the top variable, we need to increase the value by 1 then assign the value


fun push(entry: Int) {
	if (this.isStackFull()) {
		println("Stack is full. Increasing the capacity.")
		this.increaseStackCapacity()
	}

	top += 1
	println("Adding: $entry")
	this.stackArr[top] = entry
}	

isStackFull() function return boolean value, true if arrays is full or false.

Logic is simple, we compare the index/top with the size of the array - 1.

I hope, you know that if the array size is 5, then the last index will have value of 4 because index starts with 0

private fun isStackFull(): Boolean {
	return top === stackSize - 1
}

pop() function will remove the last element, but how do we get the last added element. it is simple that top variable keeps track of the current index, here current index is the one which is on top.

You might have doubt, are we removing the element from the array ? Answer: NO.

We just pretend like the popped element is no more present but popped element will be present till we change the array with new array.

Once we pop an element we reduce the top value by 1, now the top variable will have a index of the element which is the one before the last

So when we add a element using push, the last element will be replaced with new value. I hope, now you are in more confusion :)

fun pop(): Any {
	if (this.isStackEmpty()) {
		throw Exception("Stack is empty. Can not remove element.")
	}
	top -= 1
	var entry = this.stackArr[top]
	println("Removed entry: $entry")
	return entry
}

size() function will return the number of elements present in the arrays except popped ones. As I explained earlier, popped element will be present in the array till we replace it with new value.

So we cannot use the length property of the array because it will return the all the elements present arrays (which includes the popped ones)

Perhaps we have to return the index that we are currently pointing to but index always point to size -1, so now return the value as index +1.


fun size(): Any {
	return top+1
}	

peek() will return the last element in the arrays (excluding the popped elements), we can use the top variable as index to get the value


fun peek(): Any {
    return stackArr[top]
}

increaseStackCapacity() moves the old arrays elements to the new array, the exchange happens only when old array is full.

The new array will be created based on the calculation of old array, some people increase the array size by twice like old array size * 2, some people by 1.5 time like old array size * 1.5

  • If Logic is oldSize * 2 growth will be like, considering 6 as base capacity. Growth is 6, 12, 24, 48, 96, ...
  • if Logic is oldSize * 1.5 growth will be like 6, 9, 13, 19,... goes on
  • How you can decide the logic is, based on the memory size you want to allocate. For example, if you have 1,00,000 (one lakh) elements in array, if you use *2 then next moment you will be allocating memory for 2,00,000 (two lakh) elements, but if you use *1.5 the memory allocation is for 1,50,000 (one lakh fifty thousand) elements

private fun increaseStackCapacity() {
	val newStack = IntArray(this.stackSize * 2)
	for (i in 0 until stackSize) {
		newStack[i] = this.stackArr[i]
	}
	this.stackArr = newStack
	this.stackSize = this.stackSize * 2
}

isStackEmpty() method return whether a given stack is empty or not, returns true if no elements otherwise false.

top keeps the track of index where we added the new element, when it reaches 0, we still have element at 0. So when it reaches -1 then we can say there is no more elements in he stack.


fun isStackEmpty(): Boolean {
	return top === -1
}	

The complete example for kotlin stack implementation using arrays


class StackUsingArray(size:Int){
    private var stackSize = size;
    private var stackArr = IntArray(stackSize);
    private var top = -1;

    fun push(entry: Int) {
        if (this.isStackFull()) {
            println("Stack is full. Increasing the capacity.")
            this.increaseStackCapacity()
        }

        top += 1
        println("Adding: $entry")
        this.stackArr[top] = entry
    }

    fun pop(): Any {
        if (this.isStackEmpty()) {
            throw Exception("Stack is empty. Can not remove element.")
        }
        var entry = this.stackArr[top--]
        println("Removed entry: $entry")
        return entry
    }

    fun size(): Any {
        return top+1
    }
    fun peek(): Any {
        return stackArr[top]
    }

    private fun increaseStackCapacity() {
        val newStack = IntArray(this.stackSize * 2)
        for (i in 0 until stackSize) {
            newStack[i] = this.stackArr[i]
        }
        this.stackArr = newStack
        this.stackSize = this.stackSize * 2
    }

    fun isStackEmpty(): Boolean {
        return top === -1
    }
    private fun isStackFull(): Boolean {
        return top === stackSize - 1
    }
}

fun main(args: Array) {
    val stack = StackUsingArray(2)
    stack.push(1)
    stack.push(7)
    println("is stack empty : " +stack.isStackEmpty())
    println("size of stack : " +stack.size())
    println("peek : " +stack.peek())
    println("pop : " +stack.pop())
    println("size of stack : " +stack.size())
}	

Output of kotlin stack data structure


Adding: 1
Adding: 7
is stack empty : false
size of stack : 2
peek : 7
Removed entry: 7
pop : 7
size of stack : 1

aaaaaaaaaaaaa
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions

Recent Addition

new tutorial Selenium Online Training : Our next online training course for Selenium with Java starts from 17th December 2018.

You can attend first 3 classes for free, the total course fee is INR 10,000

The course time would be 8.00 PM(IST) for the first three classes

If you are interested to learn, then you can join the course by sending email to chercher.tech@gmail.com

or Register below


 
Join My Facebook Group
Join Group