[算法学习]栈中的最小值

算法

问题描述： 实现栈的pop、push、 min (得到栈中最小值)方法。

解法与分析：

  1. 由于每次压栈和出栈都可能会改变栈中的最小值，所以，我们增加一个存放最小值的栈。
  2. 当出栈操作时，最小值的栈也出栈；(当然，必须判断栈是否为空)
  3. 当压栈操作时，比较压栈元素值和最小栈的栈顶元素的大小，若比较小，则将它压入栈中，若不是，则将最小栈的栈顶元素重复压栈。(当然，必须判断栈是否为空)

参考代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
private Stack<Integer> dataStack = new Stack<Integer>();
private Stack<Integer> minStack = new Stack<Integer>();

/**
 * 出栈
 * @return
 */
public int pop()
{
    if (minStack.isEmpty() && dataStack.isEmpty())
    {
        throw new EmptyStackException();
    }
    minStack.pop();
    return dataStack.pop();
}

/**
 * 压栈
 * @param item
 */
public void push(int item)
{
    dataStack.push(item);
    if(minStack.isEmpty()||item<minStack.peek())
    {
        minStack.push(item);
    }
    else
    {
        minStack.push(minStack.peek());
    }
}

/**
 * 取最小值
 * @return
 */
public int min()
{
    if(minStack.isEmpty())
    {
        throw new EmptyStackException();
    }
    return minStack.peek();
}