Tuesday, May 29, 2018

Kotlin Data Structure: Stack

Welcome to this post.
This is going to be a series post about data structure and algorithm, In this series, I use kotlin as a default language.

Let's start with stack data structure-

Stack is a simple data structure.
The implementation of this data structure is also called LIFO that means Last in Fast out.
Basically, in this data structure, the last data will come in first.

Src: Wikipedia

In this picture, the First A block moves into C. Now if we want to get a block from C then we must take the green block first that insert in the last. And this is the basic concept of Stack.
You check Wikipedia for more.

Now come in programming-
To put data in Stack there is a function called push()
and to access data called pop() and this function also removes the first element of Stack.

Src: Wikipedia


To implement sack we always think about the top position. For example, after a successful push top position will change and also in the pop operation.

So, create a class, (you can make an inner class) and create two variable,
  • one is for top position
  • other is a list to store data.
we are using kotlin so mutable list will be perfect.
initialize top as -1 and an empty list
class Stack<T> {
    private var top = -1
    private val array:MutableList<T> = mutableListOf()
}

push() function
         now our top position is -1. so in the push method, we just increase the top position. Just add plus one in every push. and insert data in the array at this index.
fun push(value: T) {
    top += 1
    array.add(top,value)
}

pop() function:
          when we create the class we initialize top position as -1. basically, array stary from zero indexes. so -1 index does not exist. so first check the value of the top position. if the position is -1 the stack has no data yet. If you called pop() function you are trying to get data from the empty stack. For this case, if the stack is empty we throw an exception.
if (top == -1) {
    throw Exception("Stack is empty")
}

now take the value from array and array index will be top value. And finally, reduce the top position.
fun pop(): T {

    if (top == -1) {
         throw Exception("Stack is empty")
    }

    val value = array[top]
    top -= 1
    return value
}

now create a variable that will show the length of this stack. we use get method of kotlin.
If the top is -1 then the length will be 0 and is not then length will be top + 1
val length:Int get() {
     return if (top == -1) 0
     else top + 1
}

Now time for put data and access data from this stack

create the main function-
fun main(args: Array<String>) {
}
create an instance of stack and type will be Int
val stack = Stack<Int>()
push():
run a for loop and the number range will be 0 to 10. And insert the date in the stack
for (i in 0 until 10){
    stack.push(i)
}

Now print the length of Stack-
println("Stack length:${stack.length}")
Output:
Stack length:10
so the data inserted successfully. Now get the data

pop()
we run a while loop until the stack length is zero
while (stack.length > 0){
    println("Stack: value:${stack.pop()} length:${stack.length}")
}
Output:
Stack: value:9 length:9
Stack: value:8 length:8
Stack: value:7 length:7
Stack: value:6 length:6
Stack: value:5 length:5
Stack: value:4 length:4
Stack: value:3 length:3
Stack: value:2 length:2
Stack: value:1 length:1
Stack: value:0 length:0

see the first value is 9 and but we start to insert data from 0. We find zero in the last.
at the last, the value is zero and the length is zero.
So now our stack is zero.

If we try to get data from stack then see what will happen-
println("Stack ${stack.pop()}")
Output:
Exception in thread "main" java.lang.Exception: Stack is empty
    at dataStructure.stack.Stack.pop(StackDemo.kt:33)
    at dataStructure.stack.StackDemoKt.main(StackDemo.kt:18)
we will get an exception.

That's it, we finished the implementation of stack and do push and pop operation.

In case you miss something, check the full code on Github

Thank you very much for reading. Hope this will help you.
Keep practicing

Happy coding

About Author:

I am Shudipto Trafder,
Since 2015, I write android code. I love to implement new ideas. I use java and also kotlin. Now I am learning Flutter. I love to learn new things and also love to share. And that is the main reason to run this blog.


Let's Get Connected: Facebook Twitter Linkedin Github

No comments :