包含min函数的栈

问题描述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。调用min、push、pop的时间复杂度都是O(1)

思路分析

可以构造一个辅助栈，该栈里只放每次的最小栈顶元素集合，比如刚开始往栈里放3,4；则辅助栈里存放的是3,3；即每次比较新加的元素和原辅助栈栈顶最小元素的大小

码上有戏

public class StackWithMin {

	Stack<Integer> m_data=new Stack<>();
	   Stack<Integer> m_min=new Stack<>();
	   
	   public void push(Integer value){
		   m_data.push(value);
		   
		    if(m_min.size()==0||value<m_min.peek())
		    	m_min.push(value);
		    else{
		    	m_min.push(m_min.peek());
		    }
	   }
	   
	   public void pop(){
		   if(m_data.size()>0&&m_min.size()>0)
		   {
			   m_data.pop();
			   m_min.pop();
		   }
	   }
	
	   public Integer min(){
		   if(m_data.size()>0&&m_min.size()>0)
			   return m_min.peek();
		   return null;
	   }
	
	public static void main(String[] args) {
		StackWithMin sta=new StackWithMin();
		 sta.push(3);
		  sta.push(4);
		   sta.push(2);
		    System.out.println(sta.min());
		      sta.pop();
		        System.out.println(sta.min());
		
	}

}

输出结果

2,3