建設(shè)網(wǎng)站要在需求長沙縣網(wǎng)絡(luò)營銷咨詢
后續(xù)會有補(bǔ)充和更改?
棧和隊列
棧和隊列也屬于線性表?
棧
一種特殊的線性表,只允許在固定的一端進(jìn)行插入和刪除元素。該端稱為棧頂,另一端稱為棧底。
棧中的數(shù)據(jù)遵循后進(jìn)先出(LIFO)的原則
壓棧/進(jìn)棧/入棧:數(shù)據(jù)插入到棧中的操作。入數(shù)據(jù)在棧頂
出棧:棧中數(shù)據(jù)的刪除操作。出數(shù)據(jù)也在棧頂?
棧的實現(xiàn)
?棧的實現(xiàn)一般可以使用數(shù)組或者鏈表來實現(xiàn),相對而言數(shù)組的結(jié)構(gòu)實現(xiàn)更優(yōu)一些,因為棧的插入和刪除都是在棧頂,也就是數(shù)組的尾部,而數(shù)組在尾上插入數(shù)據(jù)的代價比較小。
如果要用鏈?zhǔn)綏?#xff0c;用頭部做棧頂更優(yōu)一些
那么棧的實現(xiàn)是用數(shù)組好還是鏈表好呢?
用數(shù)組更好,因為?;旧暇褪俏膊逦矂h,而數(shù)組尾插尾刪的效率很高,鏈表也是可以的,而且鏈表需要用雙向的,如果用單向的話,尾插好說,但是尾刪不好用
實際中一般不用定長的靜態(tài)棧結(jié)構(gòu),所以主要學(xué)會實現(xiàn)動態(tài)增長的棧
棧不要輕易遍歷,因為它是一邊進(jìn)一邊出,遍歷棧意味著把棧騰空
隊列
隊列:只允許在一端進(jìn)行插入數(shù)據(jù)操作,在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表。隊列具有先進(jìn)先出(FIFO)的特性
隊列和棧的某些性質(zhì)相反
入隊列:進(jìn)行插入操作的一端稱為隊尾
出隊列:進(jìn)行刪除操作的一端稱為隊頭
隊列的實現(xiàn):
? ? ? ? 隊列也可以用數(shù)組和鏈表的結(jié)構(gòu)實現(xiàn),使用鏈表的結(jié)構(gòu)實現(xiàn)更優(yōu)一些,如果用數(shù)組,想隊頭出數(shù)據(jù)只能將其覆蓋,效率比較低。
? ? ? ? 另外,實際中我們有時還會使用一種隊列叫循環(huán)隊列。如生產(chǎn)者消費者模型中可能就會使用循環(huán)隊列。環(huán)形隊列可以使用數(shù)組實現(xiàn),也可以使用環(huán)形鏈表實現(xiàn)。
隊列的應(yīng)用場景:
? ? ? ? 1.排隊。要保持絕對公平性的地方,用它。
? ? ? ? 2.廣度優(yōu)先遍歷。BFS、DFS。