一:棧
棧就是限定在尾部進行插入和刪除的線性表.
這種后入先出的結(jié)構(gòu)叫做Last in first out,LIFO結(jié)構(gòu);
線性表的特性椀吞玻基本都有,不過插入和刪除需要特殊處理,入棧叫做push,出棧叫做pop.棧的應(yīng)用極其廣泛,凡是能夠回退的場景,都可以用棧實現(xiàn),比如網(wǎng)頁.
1.順序結(jié)構(gòu)
順序存儲的棧,叫做順序棧.
顯然入棧和出棧都是O(1)的.
順序棧,有一種獨特的使用方法,共用數(shù)組空間;
順序存儲的線性表需要一個數(shù)組來存儲,數(shù)組的長度需要事先申請,這些空間是可以利用起來的;
有這樣一種常見,當(dāng)A占用空間增加時,B一定會減少,這種此漲彼伏的場景可以用兩個棧共用數(shù)組來實現(xiàn).
將棧A的棧底設(shè)置在數(shù)組的第一個元素,將棧B的棧底設(shè)置在數(shù)組的最后一個元素.入棧時,兩邊向中間靠攏.
2.鏈式存儲
鏈式存儲叫做鏈棧,這種結(jié)構(gòu)就很舒服了,既然棧是后進先出,那么直接把頭指針放在棧頂就ok了.
鏈棧和鏈表一樣,只是插入和刪除需要特殊操作.
插入,也就是入棧,把新節(jié)點的next指向top,再移動top即可.
刪除,就是出棧,把top往下移動一位,然后講棧頂節(jié)點釋放.
遞歸調(diào)用函數(shù)是一種典型的棧結(jié)構(gòu):
當(dāng)調(diào)用嵌套調(diào)用函數(shù)式,函數(shù)體和參數(shù)就會入棧,當(dāng)達到設(shè)置的條件時,就開始出棧
二:隊列
對比棧,隊列就是只準在一端插入,在另一端刪除的線性表
隊列是先進先出的,first in first out,簡稱FIFO.
只許進的(插入)叫隊尾,只許出的(刪除)叫隊頭;
1.順序存儲
順序結(jié)構(gòu)的線性表存在一個數(shù)組里.叫做順序隊列.
當(dāng)刪除隊頭元素時,后面的元素需要向前移動一位,以保證元素一直存儲在數(shù)組前n個;
當(dāng)然也可以不移動,這樣的話就相當(dāng)于隊頭移動了;
定義一個front指針指向隊頭,定義一個rear指向隊尾后后面一個下標(biāo)的位置;當(dāng)front = rear時,這就是個空隊列.
但是前面會空出來,當(dāng)隊尾到達數(shù)組最大時,叫做假溢出.
如果到達隊尾時再從頭開始,就可以解決假溢出,叫做循環(huán)隊列,注意它是順序結(jié)構(gòu)的,不是鏈式.
如此,當(dāng)數(shù)組最后一位被使用的時候,rear移動到了數(shù)組第0的位置,但是這樣一來,就沒法判斷隊列是空還是滿了
解決辦法是空出一個,然后根據(jù)一定的關(guān)系來判斷,就是(rear+1) % queueSize = front;當(dāng)滿足這個條件時,數(shù)組已滿.
2.鏈式存儲
鏈式存儲的隊列,叫做鏈隊列,本質(zhì)是個單向鏈表,多了一個rear指針,只能隊頭刪除,隊尾插入
-
入隊操作
就是在隊尾插入節(jié)點,然后修改rear指針
入隊 -
出隊操作
出隊就是刪除第一個節(jié)點,然后修改front指針
出棧
