FILO stack in 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.
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(); } }
Related Posts
Subscribe
Login
0 Comments
Newest
Oldest
Most Voted
Inline Feedbacks
View all comments