（初级）8.最小栈

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) -- 将元素 x 推入栈中。
• pop() -- 删除栈顶的元素。
• top() -- 获取栈顶元素。
• getMin() -- 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

使用两个栈来实现，一个栈来按顺序存储push进来的数据，另一个用来存出现过的最小值。

golang代码如下：

package stack

import (
    "container/list"
)

type Stack struct {
    list *list.List
}

func NewStack() *Stack {
    list := list.New()
    return &Stack{list}
}

func (stack *Stack) Push(value interface{}) {
    stack.list.PushBack(value)
}

func (stack *Stack) Pop() interface{} {
    e := stack.list.Back()
    if e != nil {
        stack.list.Remove(e)
        return e.Value
    }
    return nil
}

func (stack *Stack) Peak() interface{} {
    e := stack.list.Back()
    if e != nil {
        return e.Value
    }

    return nil
}

func (stack *Stack) Len() int {
    return stack.list.Len()
}

func (stack *Stack) Empty() bool {
    return stack.list.Len() == 0
}

/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */


type MinStack struct {
    s1, s2 *Stack
}

/** initialize your data structure here. */
func Constructor() MinStack {
    return MinStack{
        s1: NewStack(),
        s2: NewStack(),
    }
}

func (this *MinStack) Push(x int) {
    this.s1.Push(x)
    if this.s2.Empty() || x <= this.s2.Peak().(int) {
        this.s2.Push(x)
    }
}

func (this *MinStack) Pop() {
    x := this.s1.Pop()
    if x == this.s2.Peak().(int) {
        this.s2.Pop()
    }

}

func (this *MinStack) Top() int {
    return this.s1.Peak().(int)

}

func (this *MinStack) GetMin() int {
    return this.s2.Peak().(int)

}