知識(shí)大綱
棧和隊(duì)列的數(shù)據(jù)結(jié)構(gòu)
相同點(diǎn)
棧和隊(duì)列都是對(duì)刪除和插入做了限制的線性表 棧和隊(duì)列的都是建立在線性表的數(shù)據(jù)結(jié)構(gòu)上的。因?yàn)榫€性表分順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，所有棧和隊(duì)列都同時(shí)區(qū)分這兩種數(shù)據(jù)結(jié)構(gòu)。也就同時(shí)擁有了這兩種數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點(diǎn)。
不同點(diǎn)
stack棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表。
- 順序棧：建立在線性表順序存儲(chǔ)上的棧結(jié)構(gòu)
當(dāng)數(shù)據(jù)類型相同且有相反關(guān)系時(shí)可以用共享空間解決棧的的空間大小固定的問(wèn)題。 - 鏈?zhǔn)綏＃航⒃诰€性表上鏈?zhǔn)酱鎯?chǔ)的棧結(jié)構(gòu)
增加了指針域，但是空間大小自由。就是是做每個(gè)數(shù)據(jù)元素的所站的控件增加了，但是鏈?zhǔn)綏Ｋ镜目丶亲杂傻摹?/li>
隊(duì)列是只允許在一段進(jìn)行插入操作，另一段進(jìn)行刪除操作的線性表
順序隊(duì)列 ： 建立在線性表順序存儲(chǔ)上的隊(duì)列結(jié)構(gòu)
不同隊(duì)列，前面刪除元素后后面的所有元素都會(huì)移動(dòng)，時(shí)間復(fù)雜度為O(n)
循環(huán)隊(duì)列，當(dāng)前面的元素被刪除后面的元素要溢出的時(shí)候，將再增加的元素添加到下標(biāo)為0的地方。解決了空間浪費(fèi)和假溢出的問(wèn)題鏈?zhǔn)疥?duì)列 ：建立在線性表鏈?zhǔn)酱鎯?chǔ)上的隊(duì)列結(jié)構(gòu)
棧和隊(duì)列的應(yīng)用
- 棧的應(yīng)用
1，計(jì)算機(jī)處理四則運(yùn)算表達(dá)式
1.1，將中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式
1.2,將后綴表達(dá)式進(jìn)行運(yùn)算得出結(jié)果
將數(shù)字和運(yùn)算符放到了2個(gè)棧里面
2，遞歸
一個(gè)直接調(diào)用自己或間接調(diào)用自己的函數(shù)，稱為遞歸。
尾遞歸（想要了解尾遞歸需要先了解尾調(diào)用）
什么是尾調(diào)用？
指某個(gè)函數(shù)的最后一步是調(diào)用另一個(gè)函數(shù)，尾調(diào)用不一定出現(xiàn)在函數(shù)尾部，只要是最后一步操作即可。
這個(gè)函數(shù)只能是一個(gè)函數(shù)不能再加減乘除任何參數(shù)
尾調(diào)用優(yōu)化
函數(shù)調(diào)用會(huì)在內(nèi)存形成一個(gè)"調(diào)用記錄"，又稱"調(diào)用幀"（call frame），保存調(diào)用位置和內(nèi)部變量等信息。
如果在函數(shù)A的內(nèi)部調(diào)用函數(shù)B，那么在A的調(diào)用記錄上方，還會(huì)形成一個(gè)B的調(diào)用記錄。等到B運(yùn)行結(jié)束，將結(jié)果返回到A，B的調(diào)用記錄才會(huì)消失。如果函數(shù)B內(nèi)部還調(diào)用函數(shù)C，那就還有一個(gè)C的調(diào)用記錄棧，以此類推。所有的調(diào)用記錄，就形成一個(gè)["調(diào)用棧"]。
尾調(diào)用由于是函數(shù)的最后一步操作，所以不需要保留外層函數(shù)的調(diào)用記錄，因?yàn)檎{(diào)用位置、內(nèi)部變量等信息都不會(huì)再用到了，只要直接用內(nèi)層函數(shù)的調(diào)用記錄，取代外層函數(shù)的調(diào)用記錄就可以了
尾遞歸
函數(shù)調(diào)用自身，稱為遞歸。如果尾調(diào)用自身，就稱為尾遞歸
遞歸非常消耗內(nèi)存
遞歸非常耗費(fèi)內(nèi)存，因?yàn)樾枰瑫r(shí)保存成千上百個(gè)調(diào)用記錄，很容易發(fā)生"棧溢出"錯(cuò)誤（stack overflow）。但對(duì)于尾遞歸來(lái)說(shuō)，由于只存在一個(gè)調(diào)用記錄，所以永遠(yuǎn)不會(huì)發(fā)生"棧溢出"錯(cuò)誤
- 隊(duì)列的應(yīng)用
計(jì)算機(jī)操作系統(tǒng)
客服系統(tǒng)
