首页 > 代码库 > 【编程之美】3.7 队列取最大值操作问题 ☆
【编程之美】3.7 队列取最大值操作问题 ☆
之前写过栈的，以为队列的也一样，结果一点都不一样。写了好久啊。
因为栈是后进先出，先进去的数字不会影响后面的数字；而队列是先进先出，后进去的会受先进入的数字的影响。
比如： (先) 1 9 3 8 4 (后) 这样的序列
栈存储 1 9 就可以了，因为9弹出后，自然 1 就是最大的
队列则不行，如果按上面存储9弹出后 剩下 3 8 4，8是最大的，没有存储。
我的方法，保存一个max的队列
入队列时： 如果新值比 max的最前面的元素大，那么把max清空，压入新值。 因为这个元素比所有值大，并且比所有值都晚弹出。
如果不满足上面条件，但是新值比数据队列的最后一个元素大或等于，把新值压入max队列。因为队列只剩下新值上一个元素和新值时，该新值就是最大的数字。
出队列时：如果弹出的数字和max队列最前面的数字一样大，弹出max中的元素
获得最大元素：获得max的最前面的元素。
#include <iostream>#include <queue>using namespace std;class My_Queue{public: My_Queue(){}; void EnQueue(int v) { if(max.empty()) { max.push(v); } else { if(v > max.front()) { while(!max.empty()) { max.pop(); } max.push(v); } else if(v >= data.back()) { max.push(v); } } data.push(v); } int DeQueue() { if(data.empty()) { printf("error"); return 0; } if(!max.empty() && data.front() == max.front()) { max.pop(); } int del = data.front(); data.pop(); return del; } int MaxElement() { if(max.empty()) { printf("no data\n"); return 0; } return max.front(); } queue<int> data; queue<int> max;};int main(){ My_Queue q; q.EnQueue(1); q.EnQueue(5); q.EnQueue(9); q.EnQueue(3); q.EnQueue(8); q.EnQueue(4); q.EnQueue(8); q.EnQueue(11); for(int i = 0; i < 8; i++) { printf("max:%d ", q.MaxElement()); printf("del:%d\n", q.DeQueue()); } return 0;}
书上答案：
用两个栈A, B来构造队列，因为栈取最大可以O(1),利用栈使得队列取最大也是O（1）
数据入队列时：都压入栈B
数据出队列时： 若A为空，则把B的数据依次弹出给A，再弹出A的最后一个元素 （两次后进先出就变成了先进先出）
若A不空，直接弹出A的最后一个元素
取最大值： 取栈A 和 栈B 最大值里 更大的那一个
【编程之美】3.7 队列取最大值操作问题 ☆
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。