C++初階作業(yè)Stack&&queue作業(yè)題一-創(chuàng)新互聯(lián)

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

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

Stack queue作業(yè)題

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

最小棧問(wèn)題

它問(wèn)題的題目描述是這樣子的

什么意思呢？ 用一句話解釋下 就是設(shè)計(jì)一個(gè)棧

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

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

是不是只要設(shè)計(jì)兩個(gè)棧就好了？

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

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

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

這道題的主要難點(diǎn)在于思路 思路解決了 后面的問(wèn)題也就解決了

代碼表示如下

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;
};

棧的壓入彈出序列

題目如下

這里的題目要求我們來(lái)設(shè)計(jì)一個(gè)算法 檢驗(yàn)棧的插入彈出序列是否是有效的

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

那想想看 我們這個(gè)時(shí)候應(yīng)該怎么做呢？

要設(shè)計(jì)一個(gè)算法去計(jì)算有點(diǎn)太難了是不是

那么我們可不可以直接使用一個(gè)棧來(lái)模擬這個(gè)過(guò)程呢？

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

我們一開(kāi)始可以設(shè)計(jì)兩個(gè)指針

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

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

像這樣

當(dāng)我們的出棧序列不等于入棧序列的時(shí)候那就一直入棧

當(dāng)我們的出棧序列等于入棧序列的時(shí)候呢 就開(kāi)始出棧

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

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

所以我們這個(gè)時(shí)候就停止出棧

當(dāng)5也入棧的時(shí)候

這個(gè)時(shí)候就是按照 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++;

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

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

運(yùn)行結(jié)果如下

逆波蘭表達(dá)式問(wèn)題

題目如下

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

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

就只談逆波蘭表達(dá)式如何使用

它的原則其實(shí)很簡(jiǎn)單就只有兩條

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

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

那么對(duì)應(yīng)的代碼表示也就很簡(jiǎn)單了

   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ù)字其實(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();
    }
};

運(yùn)行結(jié)果如下

總結(jié)

講解了棧的三道題目 最小棧問(wèn)題 棧的壓入彈出序列 逆波蘭表達(dá)式問(wèn)題

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

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

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

廣告

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