什么網(wǎng)站做視頻賺錢網(wǎng)絡(luò)推廣營銷方案100例
前言
上篇博客我們討論了棧和隊列的有關(guān)結(jié)構(gòu)，本篇博客我們繼續(xù)來討論有關(guān)棧和隊列習題
這些題算是經(jīng)典了
💓 個人主頁：小張同學zkf
? 文章專欄：數(shù)據(jù)結(jié)構(gòu)
? ? ? 若有問題 評論區(qū)見📝
🎉歡迎大家點贊👍收藏?文章 ?
?
?
目錄
1. 括號匹配問題?
2.用隊列實現(xiàn)棧
3.用棧實現(xiàn)隊列
4.設(shè)計循環(huán)隊列
?
1. 括號匹配問題?
由題可知我們需要判斷一對括號是否成立，成立的話，就返回true，失敗的話就返回false，這道題乍一看不好判斷，其實我們可以用棧來解決，棧是后進先出的原則，我們可以判斷如果是左括號的話讓這個括號進棧，如果是右括號的話，讓棧里的括號出棧與右括號匹對，若匹對成功，則繼續(xù)判斷下一個括號，這里我們需要考慮極端情況，假如括號都遍歷完了，棧內(nèi)還有左括號，代表此時左括號多，不匹配，所以還需要判斷棧是否為空，還有如果第一個入棧的括號若是右括號，必定不匹配，直接false。
思路已給出，代碼如下
對于c語言來說，注意先把棧寫好，寫好后再調(diào)用棧的函數(shù)，后續(xù)c++就不用這么麻煩了
2.用隊列實現(xiàn)棧
?
這道題就是給你兩個隊列，通過隊列實現(xiàn)一個棧，我們都知道棧是后進先出的原則，而隊列是先進先出的原則，那如何用兩個隊列實現(xiàn)棧那？
?
首先我們思考，假如現(xiàn)在有兩個隊列q1和q2，我們畫圖分析
根據(jù)圖上操作要想實現(xiàn)棧的后進先出的原則，我們在入棧時先用一個隊列q1來做入棧操作，若出棧，由于后進先出的原則，我們可以先把除最后一個元素，剩下的元素全部導(dǎo)入q2，然后再將還在q1的元素通過出隊的方式實現(xiàn)出棧，若繼續(xù)入棧，此刻元素都在q2那么就用q2實現(xiàn)入棧操作，然后出棧時，按照上面的操作來回導(dǎo)入就可以了。?
所以出棧比較難，其他操作都是常規(guī)的，我們說一下出棧，我們可以用假設(shè)法，分為空的隊列和非空的隊列，非空的隊列前size-1的元素，pop出來再push進空的隊列，再pop最后一個元素
對了，判空條件是兩個隊里都沒元素時，此刻棧為空
代碼如下
3.用棧實現(xiàn)隊列
?
?兩個隊列可以實現(xiàn)棧，那兩個棧如何實現(xiàn)隊列那
隊列是先進先出原則，那對于棧來說，后進先出，若兩個棧，將第一個棧的所有元素全部導(dǎo)入第二個棧，此刻我們想想比如第一個棧原本1,2,3,4，現(xiàn)在導(dǎo)入第二個棧此刻是不是就是4,3,2,1，此刻第二個棧若出棧的話正好符合了隊列的先進先出
我們可以在畫圖看一下
其實對于兩個棧，將第一個棧導(dǎo)入另一個棧，原本第一個棧的元素是后進先出的原則，導(dǎo)入第二個棧就變成現(xiàn)進先出了
代碼如下
?
4.設(shè)計循環(huán)隊列
重頭戲來了
循環(huán)隊列，就是在一個有限空間里重復(fù)利用，如圖
?
如圖，我們用兩個指針指向數(shù)組頭，一個是隊頭指針head，一個是隊尾指針tail，push數(shù)據(jù)時，tail++，相當于Tail指向的是最后一個元素的下一個位置·，這一點跟棧棧頂元素有點類似，當初始化為0時，?指針指向最后一個元素的下一個位置，pop的話移動頭元素head就行了，不過上面的圖不現(xiàn)實，因為隊列空和滿時對應(yīng)的條件都一樣，都是head=Tail，所以我們得找一個辦法讓這個條件不一樣，才能判空
一種是用一個size變量加加，記錄數(shù)據(jù)，這是一種方法。
其實還有另一種方法，我們可以多一個空間,開k+1個空間，但只能放k個元素
如圖，此刻若放滿正好是第四個圖，相當于tail的下一個位置就是head，那么我們是不是可以根據(jù)取模得到關(guān)系（tail+1）%(k+1)==head達到這個條件就是滿，空的條件就很簡單，head==Tail
?
如果是返回尾元素，就是tail指針指向的上一個位置，tail-1，但是我們得考慮如上圖這種情況，Tail回到前面，但是此刻tail－1越界了，所以這時我們可以根據(jù)取模，(Tail-1+k+1)%(k+1)?就得到了尾元素的位置
頭元素就是head指向的元素
OK，剩下的操作就是常規(guī)操作，代碼如下
?結(jié)束語
棧與隊列經(jīng)典習題就結(jié)束了，有什么問題可私聊我，里面的滿足條件多想一想就能想明白，特別是最后一道題
OK,本篇博客結(jié)束！！！
?