题解 | #栈的压入、弹出序列#
栈的压入、弹出序列
http://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106
思路
- 先将pushV数组中的值入栈
- 将栈顶元素与popV数组的值依次比较:相等,popV数组元素向后移动一位,出栈里的数据一位;不等或栈为空结束。
- 判断popV数据是否走完,走完就匹配,返回true;否则返回false。
class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { stack<int> st; int i = 0;//控制入栈的pushV数据下表 int j = 0;//控制栈元素的pop,记录其popv长度 while(i < pushV.size()){ // pushV数组的值入栈 st.push(pushV[i]); ++i; //出栈,pop数组值依次与栈里面的数据比较 //若相等 pop ,出栈里的数据 ; 若不等 结束 while(!st.empty() && st.top() == popV[j]){ st.pop(); ++j; } } return j == popV.size();//j走完popv,是匹配 } };