随笔 - 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 阅读(894) 评论(0)  编辑  收藏 所属分类: 算法与数据结构


只有注册用户登录后才能发表评论。


网站导航: