今天做了一下WPS的筆試題，遇到了一道關于棧的題，覺得挺有意思的，就寫篇博客分享一下吧~~

題目要求：要求實現棧的數據結構，在該類型中實現一個能夠得到棧的最大元素的max函數，在該棧中，調用max,push,pop的時間復雜度是O(1).

解題思路：我們首先會想到的大概是，找最大元素不就排個序，直接取棧頂的元素不就好了嗎。可是這時，我們就把這個入棧的順序修改了。這并不是我們想要的。在不改變入棧順序的情況下，我們只能用一個輔助棧來解決這一類問題。

此時，我們可以將最大的元素放到這個輔助棧中，取輔助棧的棧頂元素就ok了。問題來了？

如何給輔助棧中放最大元素？？？

這里分為以下幾種情況：

1. 我們先往數據棧中放元素,當輔助棧為空時，直接將數據棧中的元素放入輔助棧中
2. 當輔助棧中有數據時，我們需要比較將要入棧的數據是否大于當前輔助棧中的數據，如果大于則繼續往輔助棧中放數據，否則放入當前輔助棧中的數據（這里用的比較巧妙，是為了尋找次大的數據，當pop出數據后，仍然可以找到次大的數據）

最終解題思路：

代碼實現：

由于自己考慮到了string類的特殊情況，里邊還使用了仿函數的形式，實現了簡單的模板類。

#include<iostream>
using namespace std;
#include<stack>
#include<assert.h>
#include<string>template<class T>
struct Less
{bool operator()(const T& left,const T& right){return left < right;}
};template<class T>
struct Greater
{bool operator()(const T& left,const T& right){return left >= right;}
};template<class T,class Compare>
class StackWithMax
{
public:void Push(const T& data);void Pop();T& MaxValue();private:stack<T> value_st;stack<T> max_st;
};template<class T,class Compare>
void StackWithMax<T,Compare>::Push(const T& data)
{value_st.push(data);if(max_st.size() == 0 || Compare()(data,max_st.top()))max_st.push(data);elsemax_st.push(max_st.top());
}template<class T,class Compare>
void StackWithMax<T,Compare>::Pop()
{assert(value_st.size() >= 0 && max_st.size() >= 0);max_st.pop();value_st.pop();
}
template<class T,class Compare>
T& StackWithMax<T,Compare>::MaxValue()
{assert(value_st.size() >= 0 && max_st.size() >= 0);return max_st.top();
}

測試代碼：

int main()
{StackWithMax<int,Greater<int>> st;st.Push(3);st.Push(4);st.Push(2);st.Push(1);st.Push(4);cout<<st.MaxValue()<<endl;st.Pop();cout<<st.MaxValue()<<endl;StackWithMax<string,Greater<string>> st1;st1.Push("aaa");st1.Push("bbb");st1.Push("ccc");st1.Push("fff");st1.Push("eee");cout<<st1.MaxValue()<<endl;st1.Pop();cout<<st1.MaxValue()<<endl;return 0;
}

運行結果：