Stack

When we try to solve a task with our code using collections, it is important to know what requirements we want to follow. Many collections have an implemented behavior, which makes it easy for you to work with them. Two widely used behaviors are FIFO (Queue collections) and LIFO (Stack collections).

In this topic, we will learn how to work with stacks (LIFO strategy) and see how they can help us improve our code and resolve certain code problems.

Collection behaviors

There are two types of collections with their specific behavior, which you will use very often in your tasks: FIFO and LIFO.

• FIFO behavior – the First-In-First-Out principle. In such collections, data is always added to the end and removed always from the beginning. This collection is called queue. You can see that pattern whenever you go to a supermarket and stand in a checkout queue: the first person to arrive will always be the first to be served. Its fundamental methods are enqueue (add at the end) and dequeue (remove from the beginning).

• LIFO behavior – the Last-In-First-Out principle. This collection is called stack. According to its principle, the last element to be added will be the first to be removed: that is, the elements are stacked. You can consider an example of putting your books into a box: you put them one on top of the other, and you will first take the top one when getting them out of the box. Its fundamental methods are push (add at the top), pop (remove from the top), and peek, which returns the top element.

Stack

In the JVM, the Stack class models and implements the Stack data structure using the LIFO strategy (Last-In-First-Out). It is a Java Class; it does not belong to pure Kotlin collections, so you must import it to be able to use it (import java.util.Stack). If you want an alternative, a collection based on Kotlin, you can use ArrayDeque.

When you add an item to a stack, you place it on top of the stack. When you remove an item from a stack, you always remove the top-most item. It extends the class Vector with five operations that allow a vector to be treated as a stack. Other existing methods are inherited from Vector.

Let's see the specific stack operations you can use in your code:

• push(): this method places an element at the top of the stack.

• pop(): this methods removes the object at the top of the stack and returns that object. It will throw EmptyStackException if this stack is empty.

• peek(): it retrieves or fetches the first/top element of the stack without removing it from the stack. It will throw EmptyStackException if this stack is empty.

• empty(): it returns true if there is nothing at the top of the stack; else, it will return false.

• search(): it returns the position of the element from the top of the stack; else, it will return -1.

Let's see an example of this kind of collection.

import java.util.*

fun main() {
    val stack = Stack<Int>()

    // push at top
    stack.push(1)
    stack.push(2)
    stack.push(3)

    println(stack) // [1, 2, 3]

    // pop from top
    stack.pop()

    println(stack) // [1, 2]

    // peek at top
    println(stack.peek()) // 2

    println(stack) // [1, 2]

    // search for element
    println(stack.search(1)) // 2
    println(stack.search(9)) // -1

    // is empty?
    println(stack.empty()) // false
    
}

Also, we can transform a List into a Stack and operate with it, using pop(). The following example prints a list of names using the LIFO strategy:

import java.util.*

fun main() {
    
    val listOfNames = listOf("John", "Jane", "Mary", "Peter", "Paul", "George")
    val stackOfNames = Stack<String>()

    stackOfNames.addAll(listOfNames)
    while (stackOfNames.isNotEmpty()) {
        print(stackOfNames.pop())
        print(" ")
    }
    // George Paul Peter Mary Jane John 
}

Remember: if you need the FIFO and LIFO behavior, whether both or just one of them, it is better to use ArrayDeque because it's much more efficient than Java Stack or List and it is a 100% pure Kotlin collection. Java Stack inherits from the Vector class. Vector implements a growable array of objects; it is very similar to ArrayList, but Vector is synchronized, which means that in a multithreading environment, it holds other threads in a runnable or non-runnable state until the current thread releases the lock of the object to perform an operation. On the other hand, the Vector class and some of its methods are now obsolete and have been replaced by ArrayDeque, which is better adapted to FIFO/LIFO strategies and is more optimized for concurrent and multithreaded environments.

Conclusion

In this topic, we have learned how to use Stack to manage collections by simulating the LIFO (Last-In-First-Out) behavior: when you add an item, it is put at the top, and when you remove an item, it will be removed from the top. The Java Stack class will help you accomplish these tasks in your projects.

Now is the time to do some tasks to check what you have learned. Are you ready?