创建包含min()函数的栈

阳光穿透心脏的1/2处 2022-05-26 06:15 122阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td>package&nbsp;栈;&nbsp;/**&nbsp;* 设计含最小函数min()的栈，要求min、push、pop的时间复杂度都是O(1)&nbsp;* &nbsp;* 思路：用数据栈和最小数据栈来模拟一个含有最小函数min()的栈，其中，最小数据栈存储的是数据栈中的最小元素&nbsp;*&nbsp;* @author&nbsp;LiZhe&nbsp;*/public&nbsp;class&nbsp;MinStack { 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 Stack dataStack&nbsp;= new&nbsp;Stack();//定义存储数据的栈 
 Stack minStack&nbsp;= new&nbsp;Stack();//定义存储最小数据的栈 
 
 /** 
 &nbsp;* 添加数据 
 &nbsp;* 
 &nbsp;* 思路：首先向数据栈中添加数据，然后要判断最小数据栈是否为空，若为空，或者，最小数据栈中的峰值比新添加的元素大， 
 &nbsp;* 也将新元素添加到最小数据栈中 
 &nbsp;* @param&nbsp;data 
 &nbsp;*/ 
 public&nbsp;void&nbsp;push(int&nbsp;data){ 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 dataStack.push(data); 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 if(minStack.isEmpty() || minStack.peek()&gt;data){ 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 minStack.push(data); 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 
 /** 
 &nbsp;* 从栈中取元素 
 &nbsp;* 
 &nbsp;* 思路：如果数据栈为空，直接返回null 
 &nbsp;* 如果数据栈不为空，从数据栈中弹出栈顶元素，并返回 
 &nbsp;* 如果最小数据栈的栈顶元素与数据栈弹出的元素相同，那么最小数据栈也要弹出元素 
 &nbsp;* @return 
 &nbsp;*/ 
 public&nbsp;Integer pop(){ 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 if(dataStack.isEmpty()){ 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 return&nbsp;null; 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 Integer data&nbsp;= dataStack.pop(); 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 if(data&nbsp;== minStack.peek()){ 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 minStack.pop(); 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 return&nbsp;data; 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 
 /** 
 &nbsp;* 查看栈的峰值 
 &nbsp;* @return 
 &nbsp;*/ 
 public&nbsp;Integer peek(){ 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 return&nbsp;dataStack.peek(); 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 
 /** 
 &nbsp;* 查看栈中的最小元素 
 &nbsp;* @return 
 &nbsp;*/ 
 public&nbsp;Integer min(){ 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 return&nbsp;minStack.peek(); 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 
 /** 
 &nbsp;* 主函数 
 &nbsp;* @param&nbsp;args 
 &nbsp;*/ 
 public&nbsp;static&nbsp;void&nbsp;main(String[] args) { 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 MinStack minStack&nbsp;= new&nbsp;MinStack(); 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 minStack.push(4); 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 minStack.push(3); 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 minStack.push(8); 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 minStack.push(6); 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 System.out.println("查看栈中的最小元素："); 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 System.out.println(minStack.min()); 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 </blockquote>}</td> 
 </tr> 
 </tbody> 
</table>