题解 | #栈的压入、弹出序列#
栈的压入、弹出序列
http://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106
判断出栈序列是否合理问题，看了半天，栈的问题还是用另一个栈解决比较方便，原因就是性质是一样的。
在这个问题中，知道了入栈序列和出栈序列，那么我们用一个栈模拟入栈，用出栈序列约束其出栈元素。
（1）：将入栈序列中元素压入栈
（2）：判断栈顶元素是否等于出栈元素，等于即将其pop（），出栈序列加一，重复判断
（3）：循环（1）（2），直到入栈序列所有元素被遍历
（4）：判断栈是否为空，若为空，则意味着出栈序列合理的，否则，不合理
代码：
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
stack<int> st;
int l = pushV.size();
int pushind = 0,popind = 0;
while(pushind < l){
st.push(pushV[pushind]);
while(!st.empty() & st.top() == popV[popind]){
st.pop();
popind++;
}
pushind++;
}
if(st.empty())
return true;
else
return false;
}
};
查看10道真题和解析
京东工作强度 412人发布