满足min.push.pop操作时间复杂度为o(1)的栈

发布时间:2017-6-28 9:55:32 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"满足min.push.pop操作时间复杂度为o(1)的栈",主要涉及到满足min.push.pop操作时间复杂度为o(1)的栈方面的内容,对于满足min.push.pop操作时间复杂度为o(1)的栈感兴趣的同学可以参考一下。

/** 设计一个栈结构,满足一下条件:min,push,pop操作的时间复杂度为O(1)。 */ #include <limits> #include <exception> #include <iostream> class stack { public: stack(int max_size) { this->max_size=max_size; this->cur_size=0; this->cur_min=std::numeric_limits<int>::max(); this->cur_min_pos=-1; this->arr=new int[max_size]; this->pos_arr=new int[max_size]; } ~stack() { delete[] arr; delete[] pos_arr; } int min() { return this->cur_min; } void push(int val) { if(this->cur_size==this->max_size) return ; else { if(val<this->cur_min) { this->cur_min=val; this->pos_arr[this->cur_size]=this->cur_min_pos; this->cur_min_pos=this->cur_size; } this->arr[this->cur_size++]=val; } } int pop() { if(this->cur_size==0) throw std::exception("stack has been empty"); else { if(this->cur_min_pos==--this->cur_size) { this->cur_min_pos=this->pos_arr[this->cur_size]; this->cur_min=this->arr[this->cur_min_pos]; } return this->arr[this->cur_size]; } } private: //currrent min int cur_min; //cur_min pos int cur_min_pos; //value array int* arr; //pos array int* pos_arr; //max size int max_size; //current size int cur_size; }; int main(int argc,char* argv[]) { try { stack t(10); t.push(23); t.push(2); t.push(32); t.push(1); std::cout<<t.min()<<std::endl; /// t.pop(); std::cout<<t.min()<<std::endl; }catch(std::exception& e) { std::cout<<"stack is empty!"<<std::endl; } system("PAUSE"); return 0; }

上一篇:PMBOK学习笔记-项目管理、项目集管理和项目组合管理间的关系
下一篇:android广播事件和权限

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。