package com.q0155;

import java.util.ArrayDeque;

import java.util.Deque;

import java.util.Objects;

/**

* @author xjn

* @since 2020-05-31

* https://leetcode-cn.com/problems/min-stack/

* 155. 最小栈

* 时间复杂度O(1)

* 空间复杂度O(n)

*/

public class MinStack {

/**

* initialize your data structure here.

*/

private Deque<Integer> dataStack, minStack;

public MinStack() {

dataStack = new ArrayDeque<>();

minStack = new ArrayDeque<>();

}

public void push(int x) {

dataStack.push(x);

if (minStack.isEmpty() || x <= minStack.peek()) {

minStack.push(x);

}

}

public void pop() {

if (dataStack.isEmpty()) {

throw new RuntimeException("'Your stack is Empty");

}

Integer pop = dataStack.pop();

if (!minStack.isEmpty() && Objects.equals(pop, minStack.peek())) {

minStack.pop();

}

}

public int top() {

if (dataStack.isEmpty()) {

throw new RuntimeException("'Your stack is Empty");

}

return dataStack.peek();

}

public int getMin() {

if (minStack.isEmpty()) {

throw new RuntimeException("'Your stack is Empty");

}

return minStack.peek();

}

}