棧的壓入贷掖、彈出序列
題目描述：
輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序渴语，請判斷第二個序列是否可能為該棧的彈出順序苹威。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序驾凶，序列4,5,3,2,1是該壓棧序列對應(yīng)的一個彈出序列牙甫，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）
解題思路：
- 如果下一個需要彈出的數(shù)字剛好是棧頂?shù)臄?shù)字狭郑，那么直接彈出腹暖。
- 若果下一個需要彈出的數(shù)字不是棧頂?shù)臄?shù)字， 那么我們把待入棧序列中的數(shù)字依次壓入輔助棧中翰萨，直到把這個需要彈出的數(shù)字壓到棧頂為止。
- 如果所有的數(shù)字都壓入了棧中糕殉，但是還是沒有找到下一個彈出的數(shù)字亩鬼，那么該序列不是一個可以彈出的序列
代碼：
class Solution{
public:
bool IsPopOrder(vector<int> pushV, vector<int> popV) {
// 設(shè)置一個輔助棧，以及一個輔助變量來記錄此時需要得到的棧頂彈出值
stack<int> stackData;
int data;
//
if (pushV.empty() || popV.empty()) {
return false;
}
if (pushV.size() != popV.size()) {
return false;
}
stackData.push(pushV[0]);
int j = 1;
for (int i = 0; i < popV.size(); ++i) {
// 取彈出序列最前面的值
data = popV[i];
// 如果彈出序列的值等于此時棧頂?shù)闹蛋⒌瑒t彈出棧頂值
// 并進入下一次的for循環(huán)雳锋，開始下一次的檢視
if (data == stackData.top()) {
stackData.pop();
}
// 如果棧頂?shù)臄?shù)值與彈出的序列不相等
// 則將此數(shù)值壓入輔助棧中，并檢視之后的待入棧值
else {
// 直到找到入棧序列中可以被彈出的那個值
while (j < pushV.size() && pushV[j] != data) {
stackData.push(pushV[j]);
++j;
}
// 退出while循環(huán)之后有兩種可能
// 1.j已經(jīng)遍歷完了入棧序列的所有值
if (j >= pushV.size()) {
return false;
}
// 2.找到了與待彈出元素相等的數(shù)值
// 將此數(shù)值壓入輔助棧羡洁，接著馬上彈出輔助棧（相當于沒有做任何操作）
else if (pushV[j] == data) {
++j;
}
}
}
// 如果順利進行完了上述的過程而且沒有返回false
// 則說明匹配成果
return true;
}
};
2018.10.11
