FILO stack in Java

java

Example implementation FILO stack in Java.

Implement a stack (i.e. a First-In-Last-Out queue) with an additional min operation that returns the smallest element in the stack.
All the operations (push, pop and min) should have O(1) time complexity.

You are free to implement the task in any of the following programming languages:
Java, Kotlin
Python
TypeScript or JavaScript

Provide the necessary scripts to build and run the program. Implement unit tests.

Example implementation FILO stack in Java

package warmup;

import java.util.*;
import java.util.Random;

// Java program to implement a stack that supports getMin() in O(1) time and O(1) 

class StackFILO_O1 {
    Stack s;
    Integer min;

    StackFILO_O1() {
        s = new Stack();
    }

    Integer getMin() {
        if (s.isEmpty()) {
            System.out.println("Stack is empty");
            return null;
        } else {
            System.out.println("Min values in the stack is: " + min);
            return min;
        }
    }

    void print() {
        if (s.isEmpty()) {
            System.out.println("Stack is empty");
            return;
        }

        Integer t = s.peek();

        System.out.print("StackFILO: ");

        if (t < min)
            System.out.println(min);
        else
            System.out.println(t);
    }

    Integer pop() {
        if (s.isEmpty()) {
            System.out.println("Stack is empty");
            return null;
        }

        System.out.print("pop(): ");
        Integer t = s.pop();

        if (t < min) {
            System.out.println(min);
            min = 2 * min - t;
            return min;
        } else {
            System.out.println(t);
            return t;
        }
    }

    void push(Integer x) {
        if (s.isEmpty()) {
            min = x;
            s.push(x);
            System.out.println("push(): " + x);
            return;
        }

        if (x < min) {
            s.push(2 * x - min);
            min = x;
        }

        else
            s.push(x);

        System.out.println("push(): " + x);
    }

    public static void main(String[] args) {
        StackFILO_O1 stack = new StackFILO_O1();
        Random rand = new Random();
        for (int i = 0; i < 10; i++) {
            stack.push(rand.nextInt(100));
        }
        stack.getMin();
        stack.print();
    }
}
Subscribe
Notify of
guest
0 Comments
Newest
Oldest Most Voted
Inline Feedbacks
View all comments