java实现带min()方法的栈

定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。

 

感谢csdn July整理题目和答案http://blog.csdn.net/v_JULY_v/article/details/6057286

 

这里我写的第二题的java 代码实现。

实现原理

入栈时，比较辅助栈栈顶元素大小，如果新增元素小于等于辅助栈栈顶元素，辅助栈同时入栈。出栈时，如果出栈元素等于辅助栈栈顶元素（即出栈元素为最小值），辅助栈同时出栈

例如压栈 5,2,2,1,6,3

栈     辅助栈

5         5

2         2

2         2

1         1

6       

3

 

出栈时

3          1

6          1

1          2

2          2

2          5

5         null

 

一、定义节点类，添加了遍历和添加方法，在本题目中使用不到

package cn.edu.cqupt.mircrosoft100;

public class Node {
	private Integer value;
	private Node next;
	public Node(int value)
	{
		this.value=value;
	}
	public Node()
	{
		
	}
	public void add(int value)
	{
		if(null==this.value)
		{
			this.value=value;
			return;
		}
		if(null==next)
			next=new Node();
		next.add(value);
	}
	public void list()
	{
		if(null!=value)
		System.out.println(value);
		if(null==next)
			return;
		next.list();
	}
	public Integer getValue() {
		return value;
	}
	public void setValue(Integer value) {
		this.value = value;
	}
	public Node getNext() {
		return next;
	}
	public void setNext(Node next) {
		this.next = next;
	}
	
}
	

 

二、辅助栈的实现

package cn.edu.cqupt.mircrosoft100;

public class AssistStack {
	private Node top;
	public void push(int value)
	{
		Node add= new Node(value);
		if(null==top)
		{
			top=add;
			return;
		}
		add.setNext(top);
		top=add;
	}
	public Integer pop()
	{
		if(null==top)
			return null;
		Integer temp = top.getValue();
		top=top.getNext();
		return temp;
	}
	public Node getTop() {
		return top;
	}
	public void setTop(Node top) {
		this.top = top;
	}
}

 

三、实现最小栈

package cn.edu.cqupt.mircrosoft100;

public class MinStack {
	private AssistStack assistStack=new AssistStack();//辅助栈，实现O（1）min函数
	private Node top;
	public void push(int value)
	{
		Node add = new Node(value);
		if(null==top)
		{
			top=add;
			assistStack.push(value);
			return;
		}
		add.setNext(top);
		top=add;
		refresh();
	}
	public void refresh()
	{
		int temp = top.getValue();
		if(temp<=assistStack.getTop().getValue())
			assistStack.push(temp);
	}
	public Integer pop()
	{
		Integer temp = top.getValue();
		if(null==temp)
			return null;
		if(temp==assistStack.getTop().getValue())
			assistStack.pop();
		top=top.getNext();
		return temp;
	}
	public Integer getMin()
	{
		if(null==assistStack.getTop())
			return null;
		return assistStack.getTop().getValue();
	}
	public static void main(String args[])
	{
		MinStack minStack =new MinStack();
		minStack.push(5);
		minStack.push(2);
		minStack.push(3);
		minStack.push(3);
		minStack.push(6);
		System.out.println("min:"+minStack.getMin());
		System.out.println("pop:"+minStack.pop()); 
		System.out.println("min:"+minStack.getMin());
		System.out.println("pop:"+minStack.pop()); 
		System.out.println("min:"+minStack.getMin());
		System.out.println("pop:"+minStack.pop()); 
		System.out.println("min:"+minStack.getMin());
		System.out.println("pop:"+minStack.pop()); 
		System.out.println("min:"+minStack.getMin());
		System.out.println("pop:"+minStack.pop()); 
		System.out.println("min:"+minStack.getMin());
	}
}