Last active
April 25, 2021 12:26
-
-
Save s/d0dcfadc8a89b6f8fddc5b9e22e0d6fe to your computer and use it in GitHub Desktop.
MinStack implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package nl.saidozcan; | |
| import java.lang.ref.WeakReference; | |
| import java.util.Stack; | |
| import java.util.concurrent.locks.Lock; | |
| import java.util.concurrent.locks.ReadWriteLock; | |
| import java.util.concurrent.locks.ReentrantReadWriteLock; | |
| //================================================================================ | |
| // WeakBox | |
| // This class is a wrapper around any generic value to make it weak referenced to | |
| // avoid memory leaks in certain situations where, say class A holds a strong ref | |
| // to class B and vice versa. | |
| //================================================================================ | |
| class WeakBox<Element> { | |
| //================================================================================ | |
| // Properties | |
| //================================================================================ | |
| private WeakReference<Element> weakRef; | |
| //================================================================================ | |
| // Lifecycle | |
| //================================================================================ | |
| public WeakBox(Element val) { | |
| if (val != null) { | |
| this.weakRef = new WeakReference<Element>(val); | |
| } | |
| } | |
| //================================================================================ | |
| // Public | |
| //================================================================================ | |
| public Element getValue() { | |
| return this.weakRef.get(); | |
| } | |
| } | |
| //================================================================================ | |
| // MinStack | |
| // MinStack is a generic Stack which works with any type of types as elements | |
| // if the given type implements Comparable protocol. MinStack accomplishes following | |
| // operations on constant time: push, pop, top, getMin. | |
| //================================================================================ | |
| class MinStack<T extends Comparable> implements Stackable { | |
| //================================================================================ | |
| // Properties | |
| //================================================================================ | |
| // Stacks | |
| private Stack<WeakBox<T>> valuesStack; | |
| private Stack<WeakBox<T>> minStack; | |
| // Thread safety | |
| private final ReadWriteLock readWriteLock; | |
| private final Lock readLock; | |
| private final Lock writeLock; | |
| //================================================================================ | |
| // Lifecycle | |
| //================================================================================ | |
| public MinStack() { | |
| valuesStack = new Stack<WeakBox<T>>(); | |
| minStack = new Stack<WeakBox<T>>(); | |
| readWriteLock = new ReentrantReadWriteLock(); | |
| readLock = readWriteLock.readLock(); | |
| writeLock = readWriteLock.writeLock(); | |
| } | |
| //================================================================================ | |
| // Properties | |
| //================================================================================ | |
| public void push(T val) { | |
| if (val == null) return; | |
| // Entering the critical section | |
| writeLock.lock(); | |
| // Creating the WeakBox | |
| WeakBox<T> newValueWeakBox = new WeakBox(val); | |
| if (newValueWeakBox == null) return; | |
| // Pushing to the values stack | |
| valuesStack.push(newValueWeakBox); | |
| if (shouldAddValueToMinStack(val)) { | |
| minStack.push(newValueWeakBox); | |
| } | |
| // Leaving the critical section | |
| writeLock.unlock(); | |
| } | |
| public void pop() { | |
| writeLock.lock(); | |
| valuesStack.pop(); | |
| minStack.pop(); | |
| writeLock.unlock(); | |
| } | |
| public T top() { | |
| readLock.lock(); | |
| T poppedElement = valuesStack.peek().getValue(); | |
| readLock.unlock(); | |
| return poppedElement; | |
| } | |
| public T getMin() { | |
| readLock.lock(); | |
| T minElement = minStack.peek().getValue(); | |
| readLock.unlock(); | |
| return minElement; | |
| } | |
| private boolean shouldAddValueToMinStack(T val) { | |
| // If the min stack is empty add the new value directly | |
| if (minStack.isEmpty()) return true; | |
| // If the new value is less than the minStack.peek() | |
| // Then push the new value to the stack | |
| WeakBox<T> peekedValueFromMinStack = minStack.peek(); | |
| T unwrappedPeekedVal = peekedValueFromMinStack.getValue(); | |
| if (unwrappedPeekedVal.equals(null)) return false; | |
| return val.compareTo(unwrappedPeekedVal) < 0; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment