编程之美3.7——队列中取最大值操作问题
问题：
假设有这样一个拥有3个操作的队列：
1. EnQueue(v): 将v加入队列中
2. DeQueue(): 使队列中的队首元素删除并返回此元素
3. MaxElement: 返回队列中的最大元素
设计一种数据结构和算法，让MaxElement操作的时间复杂度尽可能地低。
解法1：
用最大堆来维护队列中的节点，队列用单链表表示，每个节点包含数据，而最大堆用数组表示,数组元素为节点的指针。入队的时间复杂度为O(logn)，出队的时间复杂度为O(n)，达不到书上的O(logn)，取最大值的时间复杂度为O(1)。
#include <iostream>#include <algorithm>#include <vector>using namespace std;class Stack{public:void Push(int d){vec.push_back(d);// 判断最大数是否发生改变if (maxvec.size()==0 || d>vec[maxvec[maxvec.size()-1]]){maxvec.push_back(vec.size()-1);}}int Pop(){if (vec.size()==0)return 0;// 若删除的是当前的最大数，则pop到前一个最大数if (vec.size()-1 == maxvec[maxvec.size()-1])maxvec.pop_back();int d = vec[vec.size()-1];vec.pop_back();return d;}bool empty(){return maxvec.size()==0;}int maxElement(){int maxpos = maxvec[maxvec.size()-1];return vec[maxpos];} private:vector<int> vec;// 存入压进来的数据vector<int> maxvec;// 每当最大数发生改变时，存入新的最大数的位置};class Queue{public:void EnQueue(int d){sb.Push(d);}int DeQueue(){if (sa.empty()){while (!sb.empty()){sa.Push(sb.Pop());}}return sa.Pop();}int maxElement(){return max(sa.maxElement(), sb.maxElement());}private:Stack sa, sb;// 两个后进先出的stack相当于先进先出的queue};int main(){const int n = 11;int data[] = {7, 4, 15, 9, 5, 10, 13, 3, 20, 17, 19};int i;Queue q;for (i=0; i<n/2; i++)q.EnQueue(data[i]);int d = q.DeQueue();d = q.DeQueue();d = q.DeQueue();d = q.DeQueue();d = q.DeQueue();d = q.DeQueue();d = q.DeQueue();for (; i<n; i++)q.EnQueue(data[i]);}