本文主要是介绍剑指offer: 包含min函数的栈、栈的压入弹出序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
包含min函数的栈
题目: 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在 该栈中，调用min、push及pop的时间复杂 度都是O(1)。
分析: 使用辅助栈，每当加入一个新的元素，都将当前最小值压入辅助栈(辅助栈的栈顶总是当前所有元素中的最小元素)。
class Solution {
public:stack<int> stack_data;stack<int> stack_help;void push(int value) {if (stack_data.empty()){stack_data.push(value);stack_help.push(value);}else{stack_data.push(value);stack_help.push(value < stack_help.top() ? value : stack_help.top()); }}void pop() {stack_data.pop();stack_help.pop();}int top() {return stack_data.top();}int min() {return stack_help.top();}
};使用模板类：
template <class T> class Solution{
public: stack<T> stack_data;stack<T> stack_help;void push(T value){if (stack_data.empty()) {stack_data.push(value);stack_help.push(value);}else{stack_data.push(value);stack_help.push(value < stack_help.top() ? value : stack_help.top()); }}void pop(){stack_data.pop();stack_help.pop();}int top() {return stack_data.top();}int min() {return stack_help.top();}
};栈的压入、弹出序列
题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否是该栈的弹出序列。假设压入栈的所有数字均不相等。
class Solution {
public:bool IsPopOrder(vector<int> pushV,vector<int> popV) {stack<int> stack_help;vector<int> :: iterator it;vector<int> :: iterator jt = pushV.begin();stack_help.push(*jt);jt++;for (it = popV.begin(); it != popV.end();){// 如果当前匹配上了，直接匹配下一个元素。if (stack_help.top() == *it){stack_help.pop();it++; // 只有匹配上了才可以进行下一个元素 continue;}// 如果当前没有匹配上，继续寻找，如果直到结束都没找到，false while(jt != pushV.end() && *jt != *it){stack_help.push(*jt);jt++;} if (jt == pushV.end()) return false;// 要把当前的能匹配上的加入辅助栈 stack_help.push(*jt);jt++; // jt使用过了要加1 }return true; }
};
这篇关于剑指offer: 包含min函数的栈、栈的压入弹出序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
