频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
微软等数据结构与算法面试100题 第二题
2012-08-21 09:20:40      个评论      
收藏   我要投稿

第二题

题目: 要求设计一个栈,栈包含min函数的功能,即能够在O(1)的时间内做min, pop, push运算。

分析:
因为传统的栈只有push和pop功能,push和pop功能都是在O(1)的时间内做操作,题目要求具有min函数的功能,也就是在pop操作和push操作以后可以
在O(1)的时间内给出最小值的功能。因为如果是直接增加min函数,那么每次计算最小值的时候都是O(N)的时间,为了要达到O(1)的时间,因此需要一个
数组来存储这一动态变化过程,min_array中min_array[k]存储前K个数字里面最小值。

代码:
[cpp] 
#include<iostream> 
using namespace std; 
 
 
template <class T> 
class Stack{ 
 
private: 
 
    int size; 
    T * data; 
    int top; 
    T * min_data; 
    T min_value; 
 
public: 
         
    Stack(int size = 100); 
    ~Stack(); 
 
    T pop(); 
    //为什么要去地址呢  
 
    void push(const T item); 
    void print(){cout<<min_value<<endl;} 
 
 
}; 
 
template<class T> 
Stack<T>::Stack(int size){ 
      
    data = new T [size]; 
    min_data = new T [size]; 
    this->top = -1;  
 

 
template<class T> 
Stack<T>::~Stack() 

 
    delete []data; 
    delete []min_data; 

 
 
template<class T> 
void Stack<T>::push(const T  item) 

    if(top==size-1){ 
        cout<<"堆栈溢出"<<endl; 
        //return; 
    }    
    top ++; 
    data[top]=item; 
     
    if(top==0)  
    { 
        min_data[top] = item; 
        min_value = item; 
    } 
    else 
    { 
        if(item < min_data[top-1]) 
        { 
            min_data[top] = item; 
            min_value = item; 
        } 
        else 
        { 
            min_data[top] = min_data[top-1]; 
            this->min_value = min_data[top-1]; 
        } 
    } 

 
template<class T> 
T Stack<T>::pop() 

    if(top==-1) 
    { 
        cout<<"堆栈空"<<endl; 
        return -1; 
    } 
     
    T DATA_POP = data[top]; 
 
    min_value = min_data[top-1]; 
 
    top = top -1; 
 
     
 
    return DATA_POP; 
 

 
 
int main(){ 
 
    int stack_size = 100; 
    Stack<int> a_value(stack_size); 
 
    // test 
    a_value.push(10); 
    a_value.print(); 
         
    a_value.push(2); 
    a_value.print(); 
     
    a_value.push(3); 
    a_value.print(); 
     
    a_value.push(1); 
    a_value.print(); 
    a_value.push(5); 
    a_value.print(); 
     
    cout<<"sc"<<endl; 
    a_value.pop(); 
    a_value.print(); 
     
    a_value.pop(); 
    a_value.print();      
     
 
    return 0; 

点击复制链接 与好友分享!回本站首页
上一篇:微软等数据结构与算法面试100题 第一题
下一篇:微软等数据结构与算法面试100题 第三题
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站