题目描述：实现一个队列，要求有MAX操作，且越快越好。
思路：这道题其实就是之前碰到的，两个栈实现一个队列+min栈，变形题目，当然可以使用类似于min栈的实现（）来实现一个max栈了，
这里提供一个书上的另外的一个实现max栈的思路，其实就是通过额外的空间来完成，对于重复元素也可以处理好的。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include
11 #include 12 #include 13 #include 14 using namespace std; 15 16 template 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 74 class Queue 75 { 76 maxstack A; 77 maxstack 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 }