【算法入門(mén)必刷】算法入門(mén)-數(shù)據(jù)結(jié)構(gòu)-棧（二）

• 前言
• 算法入門(mén)刷題訓(xùn)練
• • 題目AB2： 棧的壓入、彈出序列
  • • 題目分析
    • 理論準(zhǔn)備
    • 題解
• 小結(jié)

📦個(gè)人主頁(yè)：一二三o-0-O的博客
🏆技術(shù)方向：C/C++客戶端資深工程師（直播+音視頻剪輯）
👨?💻作者簡(jiǎn)介：數(shù)據(jù)結(jié)構(gòu)算法與音視頻領(lǐng)域創(chuàng)作者
📒 系列專(zhuān)欄：牛客網(wǎng)面試必刷
📣專(zhuān)欄目標(biāo)：幫助伙伴們通過(guò)系統(tǒng)訓(xùn)練，掌握數(shù)據(jù)結(jié)構(gòu)與算法，收獲心儀Offer
📝推薦一個(gè)找工作神器：牛客刷題網(wǎng) 【面試經(jīng)驗(yàn)|實(shí)習(xí)招聘內(nèi)推，求職就業(yè)一戰(zhàn)解決】
🧡如果對(duì)您有幫助的話，歡迎點(diǎn)贊👍收藏📂，關(guān)注不迷路

【算法入門(mén)必刷】數(shù)據(jù)結(jié)構(gòu)-棧篇系列文章：
【算法入門(mén)必刷】數(shù)據(jù)結(jié)構(gòu)-棧（一）
【算法入門(mén)必刷】數(shù)據(jù)結(jié)構(gòu)-棧（二）
【算法入門(mén)必刷】數(shù)據(jù)結(jié)構(gòu)-棧（三）
【算法入門(mén)必刷】數(shù)據(jù)結(jié)構(gòu)-棧（四）
【算法入門(mén)必刷】數(shù)據(jù)結(jié)構(gòu)-棧（五）
【算法入門(mén)必刷】數(shù)據(jù)結(jié)構(gòu)-棧（六）

前言

開(kāi)啟刷題，請(qǐng)點(diǎn)擊右邊鏈接進(jìn)行跳轉(zhuǎn)點(diǎn)擊這里

算法入門(mén)刷題訓(xùn)練

題目AB2： 棧的壓入、彈出序列

題目分析

輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷第二個(gè)序列是否可能為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。
1.0<=pushV.length == popV.length <=1000
2.-1000<=pushV[i]<=1000
3.pushV 的所有數(shù)字均不相同

根據(jù)題目描述是要驗(yàn)證提供的第一個(gè)序列表示棧的壓入順序，返回第二個(gè)序列是否可能為該棧的彈出順序。對(duì)于第一個(gè)壓入序列，只要輔助棧為空，就將元素依次入棧。遇到一個(gè)元素等于當(dāng)前的第二個(gè)序列的元素，那就停止將第一個(gè)序列元素繼續(xù)入棧，先出棧。如果能按照這個(gè)流程將兩個(gè)序列都訪問(wèn)完，就返回true，否則返回false。

理論準(zhǔn)備

首先我們要掌握stack的一些基礎(chǔ)操作：

-----將元素入棧-----
std::stack mystack;
// 依次將元素1-10入棧
for (int i=1;i<=10;i++) mystack.push(i);

-----判斷stack是否為空-----
std::stack mystack;
for (int i=1;i<=10;i++) mystack.push(i);
// 如果棧不為空，進(jìn)入循環(huán)
while (!mystack.empty())
{
}

----獲取stack中元素?cái)?shù)量-----
std::stack mystack;
for (int i=1;i<=10;i++) mystack.push(i);
// 獲取數(shù)量
int size = mystack.size();

-----獲取棧頂元素-----
std::stack mystack;
for (int i=1;i<=10;i++) mystack.push(i);
// 獲取棧頂元素
int topNum = mystack.top();

-----彈出棧頂元素-----
std::stack mystack;
int sum (0);
for (int i=1;i<=10;i++) mystack.push(i);
while (!mystack.empty())
{
sum += mystack.top();
// 彈出棧頂元素
mystack.pop();
}
std::cout << "total: " << sum << ‘\n’;

題解

具體的解決方案如下：

利用stack聲明一個(gè)輔助棧。然后分別訪問(wèn)提供的兩個(gè)序列。

// 獲取序列的大小
int nPop = popV.size();
//記錄訪問(wèn)第二個(gè)序列的下標(biāo)
int index{};
//聲明輔助棧
stack< int > sPush;

輔助棧為空或者棧頂不等于第二個(gè)序列當(dāng)前元素，就持續(xù)將第一個(gè)序列數(shù)組元素加入棧中。棧頂元素等于第二個(gè)序列數(shù)組就將當(dāng)前元素就出棧。當(dāng)?shù)谝粋€(gè)序列訪問(wèn)完，第二個(gè)序列無(wú)法依次彈出，就是不匹配，否則兩個(gè)序列都訪問(wèn)就是匹配。

// 遍歷第一個(gè)序列
for(int i{};i<nPop;++i){
// 獲取第二個(gè)序列的當(dāng)前元素
int target = popV[i];
//如果當(dāng)前輔助棧為空或者輔助棧定元素不等于第二個(gè)序列的當(dāng)前元素，就持續(xù)將第一個(gè)序列元素入棧
while(index < nPop && (sPush.empty() || sPush.top() != target)){
sPush.push(pushV[index++]);
}
// 棧頂元素等于第二個(gè)序列數(shù)組當(dāng)前元素就出棧
if(sPush.top() == target){
sPush.pop();
}else {//第二個(gè)序列無(wú)法依次彈出，就是不匹配，返回false
return false;
}
}

模擬過(guò)程可參考下圖：

完整代碼如下：

class Solution { public:bool IsPopOrder(vector<int> pushV,vector<int> popV) {int nPop = popV.size();int index{};stack<int> sPush;for(int i{};i<nPop;++i){int target = popV[i];while(index < nPop && (sPush.empty() || sPush.top() != target)){sPush.push(pushV[index++]);}if(sPush.top() == target){sPush.pop();}else return false;}return true;} };

當(dāng)提交成功后，會(huì)展示如下界面，那么恭喜這道題目就通過(guò)了！

小結(jié)

祝愿所有的伙伴都能拿到自己心儀的Offer！📣伙伴們點(diǎn)擊右邊鏈接立刻開(kāi)啟刷題吧：牛客——刷題網(wǎng)

總結(jié)

以上是生活随笔為你收集整理的猿创征文|【算法入门必刷】数据结构-栈（二）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。