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.
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.
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.
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.
pop() function:
now take the value from array and array index will be top value. And finally, reduce the top position.
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
Now time for put data and access data from this stack
create the main function-
run a for loop and the number range will be 0 to 10. And insert the date in the stack
Now print the length of Stack-
pop()
we run a while loop until the stack length is zero
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-
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
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 datapop()
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