什么網(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é)束!!!
?