首页 > 代码库 > 编程之美3.7 队列中最大值问题
编程之美3.7 队列中最大值问题
这道题目的意思是,有一个队列,它里面会存储一些数值,现在,要求你需要在 O(1) 的时间内返回这个队列中最大的那个值。
这道题目的和栈中最大值最小值问题是一样的解法,都是需要一个辅助的东西,对于这道题目,我需要的是一个辅助队列。
由于是需要找到最大值,我的做法是,如果辅助队列为空,那么,当数据入队列的时候就需要同时放入队列和辅助队列中;如果辅助队列不为空,但是入队列的那个元素比辅助队列的队首元素大或者相等,那么,也是需要同时放入两个队列中;其他情况,只需要放入队列中就可以了。当出队列的时候,如果队列的队首元素和辅助队列的队首元素相同,那么需要队列和辅助队列同时删掉队首元素。
有了上述的思想,我们不难得到如下的代码:
函数声明:
/*3.7 队列中最大值问题*/ class DutQueue { public : void DutEnQueue(int); int DutFront(); void DutPop(); int DutMaxElement(); private : std :: queue<int> q1, q2; };
源代码:
void DutQueue :: DutEnQueue(int v) { this -> q1.push(v); if (this -> q2.empty()) this -> q2.push(v); else if (this -> q2.front() <= v) this -> q2.push(v); } int DutQueue :: DutFront() { return this -> q1.front(); } void DutQueue :: DutPop() { if (this -> q1.front() == this -> q2.front()) { this -> q1.pop(); this -> q2.pop(); } else this -> q1.pop(); } int DutQueue :: DutMaxElement() { return this -> q2.front(); }
编程之美3.7 队列中最大值问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。