定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元

首先声明一个数组,用来存放 入栈的数据,在申请一个数组,大小和前一个一样,此数组用来存放入栈过程中,依次存放对应位置的最小值。这个过程需要一个额外的变量表示指向栈中的栈顶元素,同时也表示指向存放排序后的数组中的第一个元素。

代码如下:(为了方便写代码,就没有考虑如果元素超过最大容量是进行对数组扩容的情况,小伙伴们可以自行进行扩容,在这里只是提供一个思路,虽然不是最好的)。

class StackEx {
	private int[] data;
	private int[] min;
	private int pos;
	private int len;
	public StackEx() {
		this(10);
	}
	public StackEx(int n) {
		pos = 0;
		len = n;
		data = new int[n];
		min = new int[n];
	}
	boolean push(int value) {//入栈操作的时候如果考虑完全应该进行扩容,在这里只是提供一个思路。
		if (pos < len) {
			if (pos == 0) {
				min[pos] = value;
			} else {
				if (value < min[pos - 1]) {
					min[pos] = value;
				} else {
					min[pos] = min[pos - 1];
				}
			}
			data[pos] = value;
			pos++;
			return true;
		}
		return false;
	}
	int pop() {
		return data[--pos];
	}
	int min() {
		return min[pos - 1];
	}
}
public class NowCoderMinStack {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] a = { 1, 3, 0, 19, 23, 29, 41, 2, 35, 9, 10 };
		StackEx stack = new StackEx(a.length);
		for (int i = 0; i < a.length; i++) {
			stack.push(a[i]);
		}
		stack.pop();
		System.out.println(stack.min());
	}
}

第二种思路 是利用辅助栈 ,声明一个栈用来存放元素的实例,声明一个栈用来存放与之对应位置上的最小元素的值,这样不用考虑扩容的情况。代码如下：
import java.util.Stack;
public class NowCoderMinStackSolution {
private Stack<Integer> minStack = new Stack<Integer>();
private Stack<Integer> dataStack = new Stack<Integer>();
public void push(int node) {
dataStack.push(node);
if (minStack.isEmpty()) {
minStack.push(node);
} else {
if (node <= min()) {
minStack.push(node);
} else {
minStack.push(min());
}
}
}
public void pop() {
if (dataStack.isEmpty()) {
return;
}
dataStack.pop();
minStack.pop();
}
public int top() {
if (!empty()) {
dataStack.peek();
}
return (Integer) null;
}
private boolean empty() {
return dataStack.isEmpty();
}
public int min() {
return minStack.peek();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = { 3, 1, 2, 5, 3, 9, -1, -2, 5, 9, 11 };
NowCoderMinStackSolution stack = new NowCoderMinStackSolution();
for (int i = 0; i < a.length; i++) {
stack.push(a[i]);
}
 stack.pop();
System.out.println(stack.min());
}
}

利用辅助栈来记录每一步的最小值（最小栈），1，如果push的数大于当前最小值则最小栈不push，如果小于等于则push；2，如果pop的时候等于最小栈中的栈顶元素则最小栈也pop，否则最小栈不pop；3，最小栈中的栈顶元素即为当前栈中最小值

package test;

import java.util.Stack;

public class Main {
    private Stack<Integer> stack= new Stack<Integer>();
    private Stack<Integer> stacktemp= new Stack<Integer>();
 public static void main(String[] args) {
  Main test = new Main();
     test.push(3);
     System.out.println(test.min());
     test.push(4);
     System.out.println(test.min());
     test.push(2);
     System.out.println(test.min());
     test.push(3);
     System.out.println(test.min());
     test.pop();
     System.out.println(test.min());
     test.pop();
     System.out.println(test.min());
     test.pop();
     System.out.println(test.min());
     test.push(0);
     System.out.println(test.min());
 }
    public void push(int node) {
        stack.push(node);
        if(stacktemp.empty()||node<=stacktemp.peek()){
            stacktemp.push(node);
        }
    }
   
    public void pop() {
        if(stack.empty()){
            throw new RuntimeException("Your stack is empty!");
        }
        if(stack.peek()==stacktemp.peek()){
            stacktemp.pop();
        }
        stack.pop();
    }
   
    public int top() {
        return stack.peek();
    }
   
    public int min() {
        if(stacktemp.empty()){
            throw new RuntimeException("Your stack is empty!");
        }
        return stacktemp.peek();
    }

}