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

转载请注明出处：http://www.cnblogs.com/wuzetiandaren/p/4254348.html

声明：现大部分文章为寻找问题时在网上相互转载，此博是为自己做个记录记录，方便自己也方便有类似问题的朋友，本文的思想也许有所借鉴，但源码均为本人实现，如有侵权，请发邮件表明文章和原出处地址，我一定在文章中注明。谢谢。

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

题目分析：

　　1.可以用另一个临时栈，当元素进栈时，临时栈则保存当该元素进栈时，该栈内元素的最小值，但这多浪费了一个栈的空间，并不是解。

　　2.网上有人给出了一些思路，只用一个多余的临时变量保存当前栈里的最小值来解决该问题，其核心思想是进栈时利用对临时变量和入栈值进行一些处理，出栈时能够利用当前的临时变量值还原进栈时该变量的原始值以及该元素出栈后临时变量的值。网友http://blog.csdn.net/anchor89/article/details/6055412#comments的文章给我很大的启示，再次深表感谢！

算法设计：

　　1. push时,候 如果 value >= min, v_push 直接入栈，如果 value < min, 那么入栈的是 2 * value - min, 然后 min = value .

　　2.pop出时， 如果栈顶的stack[top] >= min 直接出，如果 stack[top] < min 则出现异常，将min作为pop的返回值，另外需要还原前一个最小值: min = 2 * min - stack[top]

事实上，有如下规律： (k为任意整数)：

* push(v_push)时：如果 v_push >= min, v_push 直接入栈；如果 v_push < min, 那么入栈的是 k * v_push - min, 然后 min = v_push. top++
* Pop()时:如果栈顶的stack[top] >= min 直接出;如果 stack[top] < min 则将min作为pop的返回值，再还原前一个最小值min =k* min - stack[top]. top--

java 实现源码：

package com.interview;

import java.util.Scanner;

/**定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
 * 要求函数min、push以及pop的时间复杂度都是O(1)。
 * 
 * @param args
 */
public class _2StackMin {
    private static int MIN = Integer.MAX_VALUE;   //初始化最小元素
    private static int top = -1;
    private static int[] stack;
    private static int temp = MIN;  //由于最小元素会在操作的过程中，以此来保存原始最小值
    public _2StackMin() {
        super();
    }
    
    public _2StackMin(int size) {
        super();
        this.stack = new int[size];
    }

    public static void main(String[] args) {
        new _2StackMin(5);
        min();
    }
    
    //返回最小值的函数
    public static void min(){
        boolean flag = true;        
        while(flag){
            Scanner scan = new Scanner(System.in);
            System.out.println("请选择入栈还是出栈：入栈：push  出栈：pop 退出：exit");
            String operate = scan.nextLine();
            if(operate.equals("push")){
                System.out.println("请输入入栈的值：");
                int value = scan.nextInt();
                MIN = push(value);
                System.out.println("当前栈里的最小值为："+MIN);
            }
            else if(operate.equals("pop")){
                pop();
            }
            else if(operate.equals("exit")){
                flag = false;
            }
        }
    }
    
    //进栈
    private static int push(int value){
        if(top==stack.length-1){
            System.out.println("栈已满，请选择出栈操作！");
        }
        else if(value>=MIN){  //如果 v_push >= min, v_push 直接入栈
            stack[++top] = value;
        }
        else{           //入栈的是 2 * v_push - min, 然后 min = v_push
            stack[++top] = 2*value - MIN;
            MIN = value;
        }
        return MIN;
    }
    
    //出栈
    private static void pop(){
        if(top==-1){
            System.out.println("栈已空，请选择入栈或退出操作操作！");
            return;
        }
        else if(stack[top] >= MIN){     //如果栈顶的top >= min 直接出
            //int stack0 = stack[top];
            System.out.println("出栈的是："+stack[top--]);
            if(temp!=MIN){
                System.out.println("当前栈里的最小值为："+MIN);
            }    
            else
                System.out.println("这已经是最后一个元素！");
        }
        else{                     //将min作为pop的返回值，让 min = 2 * min - top
            System.out.println("出栈的是："+MIN);
            MIN = 2*MIN - stack[top];
            top--;
            if(temp!=MIN){
                System.out.println("当前栈里的最小值为："+MIN);
            }
            else
                System.out.println("这已经是最后一个元素！");
        }        
    }
}

 运行结果：

请选择入栈还是出栈：入栈：push  出栈：pop 退出：exit
push
请输入入栈的值：
3
当前栈里的最小值为：3
请选择入栈还是出栈：入栈：push  出栈：pop 退出：exit
push
请输入入栈的值：
5
当前栈里的最小值为：3
请选择入栈还是出栈：入栈：push  出栈：pop 退出：exit
push
请输入入栈的值：
2
当前栈里的最小值为：2
请选择入栈还是出栈：入栈：push  出栈：pop 退出：exit
push
请输入入栈的值：
7
当前栈里的最小值为：2
请选择入栈还是出栈：入栈：push  出栈：pop 退出：exit
push
请输入入栈的值：
1
当前栈里的最小值为：1
请选择入栈还是出栈：入栈：push  出栈：pop 退出：exit
pop
出栈的是：1
当前栈里的最小值为：2
请选择入栈还是出栈：入栈：push  出栈：pop 退出：exit
pop
出栈的是：7
当前栈里的最小值为：2
请选择入栈还是出栈：入栈：push  出栈：pop 退出：exit
pop
出栈的是：2
当前栈里的最小值为：3
请选择入栈还是出栈：入栈：push  出栈：pop 退出：exit
pop
出栈的是：5
当前栈里的最小值为：3
请选择入栈还是出栈：入栈：push  出栈：pop 退出：exit
pop
出栈的是：3
这已经是最后一个元素！
请选择入栈还是出栈：入栈：push  出栈：pop 退出：exit
pop
栈已空，请选择入栈或退出操作操作！
请选择入栈还是出栈：入栈：push  出栈：pop 退出：exit
exit