随笔 - 8, 文章 - 0, 评论 - 6, 引用 - 0
数据加载中……

实现一个栈,使其push,pop,min(取得栈中的最小元素)均为O(1)

实现一个栈,使其push,pop,min(取得栈中的最小元素)均为O(1)

我的解
interface IntStack
{
    int pop();
    void push(int i);
    int get();
}

class MinStack
{
    //store all the element
    private IntStack elemStack = new IntStack();
    
    //store current and historical smallest element
    private IntStack minStack = new IntStack();
    
    public void push(int i)
    {
        elemStack.push(i);
        
        int currentMin = minStack.get();
        if(i <= currentMin) minStack.push(i);
    }
    
    public int pop()
    {
        int result = elemStack.pop();
        if(result == minStack.get()) minStack.pop();
        return result;
    }
    
    public int getMinElem()
    {
        return minStack.get();
    }
}

posted on 2007-07-18 20:57 Job Hu 阅读(883) 评论(0)  编辑  收藏 所属分类: 算法与数据结构


只有注册用户登录后才能发表评论。
网站导航: