编程之美--3.7

题目描述：实现一个队列，要求有MAX操作，且越快越好。

思路：这道题其实就是之前碰到的，两个栈实现一个队列+min栈，变形题目，当然可以使用类似于min栈的实现（http://www.cnblogs.com/cane/p/3793510.html）来实现一个max栈了，

这里提供一个书上的另外的一个实现max栈的思路，其实就是通过额外的空间来完成，对于重复元素也可以处理好的。

  1 #include <iostream>
  2 #include <queue>
  3 #include <climits>
  4 #include <algorithm>
  5 #include <memory.h>
  6 #include <stdio.h>
  7 #include <ostream>
  8 #include <vector>
  9 #include <list>
 10 #include <cmath>
 11 #include <string>
 12 #include <stdexcept>
 13 #include <stack>
 14 using namespace std;
 15 
 16 template<typename T>
 17 class maxstack
 18 {
 19     T stackItem[100];
 20     int stackTop;
 21     int link2NextMaxItem[100];
 22     int maxStackItemIndex;
 23 public:
 24     maxstack()
 25     {
 26         stackTop = -1;
 27         maxStackItemIndex = -1;
 28     }
 29     void push(T x)
 30     {
 31         stackTop++;
 32         if(stackTop >= 100)
 33         {
 34             throw std::out_of_range("full");
 35         }
 36         stackItem[stackTop] = x;
 37         if(x >= Max())
 38         {
 39             link2NextMaxItem[stackTop] = maxStackItemIndex;
 40             maxStackItemIndex = stackTop;
 41         }
 42         else
 43             link2NextMaxItem[stackTop] = -1;
 44     }
 45     T pop()
 46     {
 47         T ret;
 48         if(stackTop < 0)
 49         {
 50             throw std::out_of_range("empty");
 51         }
 52         ret = stackItem[stackTop];
 53         if(stackTop == maxStackItemIndex)
 54             maxStackItemIndex = link2NextMaxItem[stackTop];
 55         stackTop--;
 56         return ret;
 57     }
 58     T Max()
 59     {
 60         if(maxStackItemIndex >= 0)
 61             return stackItem[maxStackItemIndex];
 62         else
 63             return INT_MIN;
 64     }
 65     bool Empty()
 66     {
 67         if(stackTop < 0)
 68             return true;
 69         return false;
 70     }
 71 };
 72 
 73 template<typename T>
 74 class Queue
 75 {
 76     maxstack<T> A;
 77     maxstack<T> B;
 78 public:
 79     void Enqueue(T elem)
 80     {
 81         A.push(elem);
 82     }
 83     T Dequeue()
 84     {
 85         if(B.Empty())
 86         {
 87             while(!A.Empty())
 88             {
 89                 B.push(A.pop());
 90             }
 91         }
 92         return B.pop();
 93     }
 94     T Max()
 95     {
 96         return max(A.Max(),B.Max());
 97     }
 98 };
 99 
100 int main()
101 {
102 
103     return 0;
104 }