作者：@小萌新
專欄：@C++初階
作者簡介：大二學生 希望能和大家一起進步！
本篇博客簡介：實現(xiàn)幾道Stack和queue的作業(yè)題

創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供陸川網(wǎng)站建設、陸川做網(wǎng)站、陸川網(wǎng)站設計、陸川網(wǎng)站制作等企業(yè)網(wǎng)站建設、網(wǎng)頁設計與制作、陸川企業(yè)網(wǎng)站模板建站服務，十年陸川做網(wǎng)站經(jīng)驗，不只是建網(wǎng)站，更提供有價值的思路和整體網(wǎng)絡服務。

Stack queue作業(yè)題

• • 最小棧問題
  • 棧的壓入彈出序列
  • 逆波蘭表達式問題
• 總結(jié)

最小棧問題

它問題的題目描述是這樣子的

什么意思呢？ 用一句話解釋下 就是設計一個棧

這個棧除了能夠執(zhí)行正常的操作之外我們還要可以隨時的獲取這個棧中的最小元素

那我們想想看我們的思路是什么？

是不是只要設計兩個棧就好了？

一個棧正常的存放數(shù)據(jù)

一個棧比較下當前存放的數(shù)據(jù)是否比自己最小的數(shù)據(jù)小

如果小于自己最小的數(shù)據(jù)那就入這個數(shù)據(jù) 如果不小于自己最小的數(shù)據(jù) 那么就再入一次目前來說最小的數(shù)據(jù)

這道題的主要難點在于思路 思路解決了 后面的問題也就解決了

代碼表示如下

class MinStack {public:
    MinStack() {}
    
    void push(int val) 
    {_stk.push(val);
        if (_stkmin.empty())
        {_stkmin.push(val);
        }
        else
        {if (_stkmin.top() >val)
            {_stkmin.push(val);
            }
            else
            {_stkmin.push(_stkmin.top());
            }
        }
    }
    
    void pop() 
    {_stk.pop();
        _stkmin.pop();
    }
    
    int top() 
    {return _stk.top();
    }
    
    int getMin() 
    {return _stkmin.top();
    }
    
private:
    stack_stk;
    stack_stkmin;
};

棧的壓入彈出序列

題目如下

這里的題目要求我們來設計一個算法 檢驗棧的插入彈出序列是否是有效的

也就是說 最后能否完全彈出所有的數(shù)據(jù)

那想想看 我們這個時候應該怎么做呢？

要設計一個算法去計算有點太難了是不是

那么我們可不可以直接使用一個棧來模擬這個過程呢？

如果模擬通過是不是就表示肯定能通過了啊

我們一開始可以設計兩個指針

一個指針指向插入數(shù)據(jù)的數(shù)組

一個指針指向刪除數(shù)據(jù)的數(shù)組

像這樣

當我們的出棧序列不等于入棧序列的時候那就一直入棧

當我們的出棧序列等于入棧序列的時候呢 就開始出棧

原則是：出掉所有符合出棧序列的數(shù)

像是這種情況 就代表出掉了所有的可以出的序列了

所以我們這個時候就停止出棧

當5也入棧的時候

這個時候就是按照 5 3 2 1的順序出棧了

那么我們的代碼表示如下

class Solution {public:
    bool IsPopOrder(vectorpushV,vectorpopV) 
    {stackst;
        int pushvi = 0;
        int popvi = 0;
        while(pushvi< pushV.size())
        {st.push(pushV[pushvi]);
            pushvi++;

            // 判斷是否要刪除
            while(!st.empty() && st.top() == popV[popvi])
            {st.pop();
                popvi++;
            }
        }

        // 最后判斷下結(jié)束
        return popvi == popV.size(); 
        
    }
};

運行結(jié)果如下

逆波蘭表達式問題

題目如下

這里大家首先要理解逆波蘭表達式究竟是什么？

大家可以上各類視頻網(wǎng)站詳細了解下 由于博客篇幅限制 這里

就只談逆波蘭表達式如何使用

它的原則其實很簡單就只有兩條

1 如果我們遍歷到加減乘除四個字符串 那么我們就從棧中取出兩個元素來分別作為左操作數(shù)和右邊操作進行運算 之后還將它入棧

2 如果我們遍歷到了數(shù)字字符串 那么我們就將它轉(zhuǎn)化成整型數(shù)字 然后存放到棧當中去

那么對應的代碼表示也就很簡單了

   long num1 = st.top(); st.pop();
           long num2 = st.top(); st.pop();

           if (x == "+") st.push(num2 + num1);
           if (x == "-") st.push(num2 - num1);
           if (x == "*") st.push(num2 * num1);
           if (x == "/") st.push(num2 / num1);

  st.push(stol(x));

最后在棧里面的數(shù)字其實就是我們要求的答案了

那么完整的代碼表示如下

class Solution {public:
    int evalRPN(vector& tokens) {stackst;
        for (auto x : tokens)
        {if (x == "+" || x =="-" || x =="*" || x =="/")
            {long num1 = st.top(); st.pop();
                long num2 = st.top(); st.pop();

                if (x == "+") st.push(num2 + num1);
                if (x == "-") st.push(num2 - num1);
                if (x == "*") st.push(num2 * num1);
                if (x == "/") st.push(num2 / num1);
            }
            else
            {st.push(stol(x));
            }
        }
        return st.top();
    }
};

運行結(jié)果如下

總結(jié)

講解了棧的三道題目 最小棧問題 棧的壓入彈出序列 逆波蘭表達式問題

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站名稱：C++初階作業(yè)Stack&&queue作業(yè)題一-創(chuàng)新互聯(lián)
鏈接URL：http://jinyejixie.com/article32/dshisc.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供響應式網(wǎng)站、面包屑導航、動態(tài)網(wǎng)站、定制開發(fā)、網(wǎng)站收錄、Google

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)