包含min函数的栈

题目链接

       要求min,push及pop的时间复杂度都是O(1),就必须要借助于辅助栈;我们可以定义个dataStack和一个assistStack
       push时,将数据push到dataStack,assistStack只存入最小的元素到头部,方便min函数直接取出;首次push时直接将元素分别push到两个栈内,如果不是首次push就把assistStack头部的元素与当前元素对比,把最小的放入到头部
       pop时,为了保证两个栈内元素个数相等,两个栈同时pop
       top时,取出栈顶元素,并不删除,直接从dataStack里面取即可
       min时,直接取assistStack中的头部元素

public class MinStack {

    Stack dataStack;
    Stack assistStack;

    public MinStack() {
        dataStack = new Stack<>();
        assistStack = new Stack<>();
    }

    public void push(int x) {
        dataStack.push(x);
        if (assistStack.isEmpty()) {
            assistStack.push(x);
            return;
        }
        assistStack.push(Math.min(assistStack.peek(), x));
    }

    public void pop() {
        dataStack.pop();
        assistStack.pop();
    }

    public int top() {
        return dataStack.peek();
    }

    public int min() {
        return assistStack.peek();
    }
}

type MinStack struct {
	dataStack, assistStack *list.List
}

func Constructor() MinStack {
	return MinStack{
		dataStack:   list.New(),
		assistStack: list.New(),
	}
}

func (this *MinStack) Push(x int) {
	this.dataStack.PushBack(x)
	if this.assistStack.Len() == 0 || this.assistStack.Back().Value.(int) >= x {
		// 数据栈等于0获取栈头大于等于当前元素才会添加
		this.assistStack.PushBack(x)
	}
}

func (this *MinStack) Pop() {
	assist := this.assistStack.Back()
	data := this.dataStack.Back()
	if assist.Value.(int) == data.Value.(int) {
		// 只有辅助栈元素与数据栈相同才会删除
		this.assistStack.Remove(assist)
	}
	this.dataStack.Remove(data)

}

func (this *MinStack) Top() int {
	return this.dataStack.Back().Value.(int)
}

func (this *MinStack) Min() int {
	return this.assistStack.Back().Value.(int)
}