要求：pop、push、getMin等函数的功能的时间复杂度都是O(1)。
思路：用两个标准栈来实现。其中一个栈用于存储数据（称为数据栈，stackData），另一个栈用于存储当前数据栈中的最小值（称为最小栈，stackMin）。
入栈规则： 假设入栈的数据为 num，则将其压入stackData中，然后判断stackMin是否为空。
如果stackMin 为空，则将num 也压入stackMin中。如果stackMin 不为空，则比较 num 与 stackMin 栈顶元素的大小。如果num 小于等于 stackMin 栈顶元素，则将num 压入stackMin中。如果num 大于 stackMin 栈顶元素，则stackMin不做操作。出栈规则： 将stackData的栈顶元素出栈，如该元素等于stackMin的栈顶元素，则stackMin将栈顶元素出栈。如该元素大于stackMin的栈顶元素，则stackMin不做操作。
获取栈中最小元素时，只需要输出stackMin的栈顶元素。
具体代码为：
class New_stack { public: New_stack(); ~New_stack(); void push(int n); void pop(); int top(); int getMin(); private: stack<int> stack_data; stack<int> stack_min; }; New_stack::New_stack() { } New_stack::~New_stack() { } void New_stack::push(int n) { stack_data.push(n); if (stack_min.empty()) stack_min.push(n); else if (n <= stack_min.top()) stack_min.push(n); } int New_stack::top() { return stack_data.top(); } void New_stack::pop() { if (stack_data.empty()) cout << "The stack is empty !" << endl; if (stack_data.top() == stack_min.top()) stack_min.pop(); stack_data.pop(); } int New_stack::getMin() { if (stack_data.empty()) cout << "The stack is empty !" << endl; return stack_min.top(); }测试代码：
int main() { cout <<"the stack who has getMin functon " << endl; New_stack stack_min; stack_min.push(10); stack_min.push(12); stack_min.push(5); stack_min.push(3); stack_min.push(54); for (int i = 0; i < 5; ++i) { cout << "the stack min value: " << stack_min.getMin() << endl; stack_min.pop(); } return 0; }测试结果：
要求：一个栈中的元素为整型，现在将栈从顶到底按从大到小的顺序排序。只允许申请一个栈。除此之外，可以申请新的变量，但是不允许使用其他的数据结构。
思路：申请一个栈用于存储临时的排序结果（记为temp_stack），申请一个变量用于记录排序栈的栈顶元素（记为cur）。如果temp_stack为空，则将cur压人temp_stack中；如果temp_stack不为空且cur 小于等于temp_stack的栈顶元素，则将压入temp_stack中；如果temp_stack不为空且cur 大于temp_stack的栈顶元素，则需要将temp_stack栈中的元素压入排序栈中，直到cur值小于等于temp_stack的元素或temp_stack为空。用这种方式排序后，temp_stack栈从顶到底的元素顺序为从小到大的顺序。因此，还需要将temp_stack栈中的元素压入原始栈中。从而实现栈从顶到底按从大到小的顺序排序。
代码：
void sortStackbyStack(stack<int> &s) { stack<int> temp_stack; int cur = 0; while (!s.empty()) { cur = s.top(); s.pop(); while (!temp_stack.empty() && temp_stack.top() < cur) { s.push(temp_stack.top()); temp_stack.pop(); } temp_stack.push(cur); } while (!temp_stack.empty()) { s.push(temp_stack.top()); temp_stack.pop(); } }测试代码：
int main() { stack<int> s; cout << endl <<"用栈将另一个栈排序： " << endl; cout <<" 原始栈： " ; s.push(1); s.push(5); s.push(6); s.push(4); s.push(7); for (int i = 0; i < 5; ++i) { cout << s.top() << " "; s.pop(); } cout << endl; cout << " 排序栈： "; s.push(1); s.push(5); s.push(6); s.push(4); s.push(7); sortStackbyStack(s); for (int i = 0; i < 5; ++i) { cout << s.top() << " "; s.pop(); } cout << endl; return 0; }测试结果：
Leetcode1019题
该题是查找链表中当前元素后面第一个大于当前元素值的元素。用暴力法解决该问题时间复杂度是O(n^2)。但是这种做法肯定难以让人满意。所以需要寻找一种更好的方法。
该问题的最优解是用栈来处理。具体思路为： 栈内存放的是 结点的编号。 每压入一个编号前，先检查该编号对应元素是否大于栈顶的编号对应元素，、如果大于，则栈顶编号出列，且栈顶编号对应元素的greater为 当前编号对应元素。如果不大于，则继续压栈。
这样做的目的是 用栈来记录哪些节点未找到它的目标节点。没找到目标节点的节点就保留在栈中，那些找到目标节点的节点则记录它的目标节点然后出栈。
具体代码为：
vector<int> nextLargerNodes(ListNode* head) { stack<int> hole; vector<int> values; for (auto node = head; node; node = node->next)//获取链表中节点的值，将其保存在values中，以便进行处理。 { values.push_back(node->val); } vector<int> res(values.size(), 0); for (auto i = 0; i < values.size(); ++i) { //查找目标值的过程 while (!hole.empty() && values[i] > values[hole.top()]) { res[hole.top()] = values[i]; hole.pop(); } hole.push(i); } return res; }运行结果为：
