package stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author dx
 * @version 1.0
 * @date 2022年3月27日 11:11
 * @description: 设计一个支持push,pop,top操作,并能在常数时间内检索到最小元素的栈:
 * 实现MinStack类:
 * Minstack() 初始化堆栈对象
 * void push(int val) 将元素val推入堆栈
 * void pop() 删除堆栈顶部的元素
 *
 *
 * 基本思路:采用两个栈,一个栈正常push和pull,另外一个栈每次push的时候比较当前栈顶和要push元素的大小,保证栈顶始终每次Push的都是最小值
 */
public class Minstack {

 Deque<Integer> stack = null;
 Deque<Integer> min = null;

 public Minstack(){

 stack = new LinkedList<Integer>();
 min = new LinkedList<Integer>();
 min.push(Integer.MIN_VALUE);
 }
 public void push(int val){
 stack.push(val);
 min.push(Math.min(min.peek(),val));
 }
 public void pop(){
 stack.pop();
 min.pop();
 }
 public int getMin(){
 return min.peek();
 }
 public int top(){
 return stack.peek();
 }
}