面试题：

使用int数组实现一个栈类，为这个栈类增加getMaxValue方法

做法：
在实现好的栈类里面，维护一个子栈，用来存储所有入栈时当过最大值的数字
比如栈：3 2 5 1 2 4
那么维护的子栈中存储的是：3 5

比如栈：3 3 2 5 1 2 4
那么维护的子栈中存储的是：3 3 5

#include<iostream>
#include<algorithm>
using namespace std;class Stack {public:int* data;int capacity;int top;Stack* maxRecord;Stack():Stack(true) {}~Stack() {if (maxRecord->is_empty()) {delete maxRecord;}delete[] data;}void push(int item) {if (top == capacity - 1) {expand_capacity();}data[++top] = item;//add maxif (maxRecord) {if (maxRecord->is_empty()) {maxRecord->push(item);}else {if (item >= maxRecord->getTop()) {maxRecord->push(item);}}}}int pop() {if (!is_empty()) {//pop maxif (maxRecord) {if (!maxRecord->is_empty()) {if (maxRecord->getTop() == getTop()) {maxRecord->pop();}}}return data[top--];}else {throw runtime_error("Stack is empty");}}int getTop() {if (!is_empty()) {return data[top];}else {throw std::runtime_error("Stack is empty");}}bool is_empty() {return top == -1;}int size() {return top + 1;}int getMaxValue() {if (maxRecord) {if (!maxRecord->is_empty()) {return maxRecord->getTop();}else {cout << "empty" << endl;}}}void expand_capacity() {int new_capacity = capacity * 2;int* new_data = new int[new_capacity];for (int i = 0; i <= top; ++i) {new_data[i] = data[i];}delete[] data;data = new_data;capacity = new_capacity;}
private:Stack(bool need) { //将有参构造隐藏capacity = 2;data = new int[capacity];top = -1;if (need) {maxRecord = new Stack(!need); //防止递归创建}else {maxRecord = nullptr;}}};int main()
{Stack stack;stack.push(2);stack.push(1);stack.push(3);stack.push(3);stack.push(2);stack.push(5);cout << "Stack size: " << stack.size() << endl;cout << "MaxValue: " << stack.getMaxValue() << endl;stack.pop();cout << "MaxValue: " << stack.getMaxValue() << endl;stack.pop();cout << "MaxValue: " << stack.getMaxValue() << endl;stack.pop();cout << "MaxValue: " << stack.getMaxValue() << endl;stack.pop();cout << "MaxValue: " << stack.getMaxValue() << endl;return 0;
}