设计含有Min函数的栈

题目：定义栈的数据结构，要求加一个min函数，能够找得到栈的最小元素。

要求函数min、push以及pop的时间复杂度都是O(1) 。

思路：栈的数据结构，是先进后出(后进先出)，本身push和pop的时间复杂度就是O（1）。得到栈的最小元素，有两种方案：1，可以遍历栈的所有元素，找到最小元素，这种方案的时间复杂度为O（n）空间复杂度为O（1）；2，是采用空间换时间的方法，栈的每个元素的数据结构出来保存自身的值之外，还要保存以这个元素为栈顶的情况下，min元素的值。

class MinElement
{
  public int value;
  public int minValue;
}

这样的数据结构把原来N的存储空间变为2N，在实际过程中，对于Stack A，它的min 为 a，这个时候新增一个元素b，当b的value值大于min时，b对应的minvalue值为min是不变的，minValue存储很多重复的值，因此可以把minValue和vlaue分开，重新使用一个堆栈保存栈的minValue。

定义一个堆栈minStack用来保存栈的minvalue，stack保存栈的值。

stack当push一个元素a时，minStack是否改变的条件如下：

1 当stack为空时，minStack直接把a入栈。
　

2当stack非空时，b为minStack的栈顶元素，当a<=b时（一定要注意=号，否则出栈就会出现问题），a入栈，否则不入栈。

stack当pop一个元素a时，minStack是否改变的条件如下：

1，b为minStack的栈顶元素，如果a<=b,则出栈，否则不出栈。

min函数返回的值就是，minStack的栈顶值。

这样的数据结构，在stack在push和pop元素时，都需要进行比较，而采用MinElement数据结构的栈，只需要在push元素时进行比较，pop时不需要比较。

当stack中push的元素都是一样的或者递减时，stack的空间消耗和MinElement一样，都需要额外的N的存储空间。

根据我的测试，随机生成10000个数据，入栈时，minStack的元素个数和stack的元素个数大概1:1000（两个堆栈的空间比为9.765625E-4），因此还是比较节省空间的。

下面是java代码：

import java.util.EmptyStackException;
import java.util.Stack;

public class MinStack {
    private Stack<Integer> stackValue;
    private Stack<Integer> stackMinValue;
    public MinStack()
    {
        stackValue=new Stack<Integer>();
        stackMinValue=new Stack<Integer>();
    }
    public void push(int item)
    {
        if(stackValue.empty())
        {
            stackValue.push(item);
            stackMinValue.push(item);
        }
        else
        {
            stackValue.push(item);
            if(item<=stackMinValue.peek())
            {
                stackMinValue.push(item);
            }
        }
        
    }
    public int pop()
    {
        if(stackValue.empty())
        {
            System.out.println("堆栈为空！！！");
            return Integer.MIN_VALUE;
        }
        else
        {
            int item=stackValue.pop();
            if(item==stackMinValue.peek())
            {
                stackMinValue.pop();
            }
            return item;
        }
    };
    public int peep()
    {
        try
        {
            return stackValue.peek();
        }catch(EmptyStackException e)
        {
            e.printStackTrace();
        }
        return Integer.MIN_VALUE;
    };
    public int peepMin()
    {
        try
        {
            return stackMinValue.peek();
        }catch(EmptyStackException e)
        {
            e.printStackTrace();
        }
        return Integer.MIN_VALUE;

    };
    public boolean empty()
    {
        return stackValue.empty();
    }
    public void clear()
    {
        stackValue.clear();
        stackMinValue.clear();
    }
    public int capacity()
    {
        return stackValue.capacity();
    }
    public int minCapacity()
    {
        return stackMinValue.capacity();
    }
}

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　菜包子　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 2013年5月13日15:19:57 于马甸桥东