第三章 棧

ps：整個(gè)文章所涉及的源代碼我都發(fā)布在我的Github主頁上，大家可以自行下載，如果對(duì)您有一丟丟的幫助的話，記得在我的github項(xiàng)目上點(diǎn)上【star】喲，當(dāng)然不要忘了在本篇文章下方【點(diǎn)贊】喲~，你們的支持將是我最大的動(dòng)力！

（利他之心是每個(gè)優(yōu)秀開發(fā)者的傳統(tǒng)美德！——@惜墨的少年）

對(duì)棧的操作

棧是一種特殊的列表，棧內(nèi)元素只能通過列表的一端訪問，這一端稱為棧頂。棧是被稱為一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。所以任何不在棧頂?shù)脑囟紵o法訪問。為了得到棧底的元素，必須先拿掉上面的元素。

對(duì)棧的兩種操作：入棧和出棧。入棧使用push() 方法，出棧使用pop() 方法。另一個(gè)常用操作是預(yù)覽棧頂?shù)脑?。pop() 可以訪問棧頂?shù)脑兀瑫r(shí)棧頂元素被永久性刪除。peek() 方法則只返回棧頂元素，而不刪除它。

棧的實(shí)現(xiàn)

實(shí)現(xiàn)一個(gè)棧，首先要決定存儲(chǔ)數(shù)據(jù)的底層數(shù)據(jù)結(jié)構(gòu)。這里采用數(shù)組。

Stack類的構(gòu)造函數(shù)

實(shí)現(xiàn)push方法，向棧中壓入新元素時(shí)，保存到top所對(duì)應(yīng)的位置，top+1，指向數(shù)組下一個(gè)空位置：

實(shí)現(xiàn)push方法

pop與push相反，返回棧頂元素，同時(shí)top自減1：

實(shí)現(xiàn)pop方法

peek方法返回?cái)?shù)組第top-1位置的元素，即棧頂元素。如果空棧調(diào)用peek() ，結(jié)果為undefined。

實(shí)現(xiàn)peek方法

length方法可以知道棧內(nèi)存儲(chǔ)了多少個(gè)元素，返回top值：

length()

將top的值設(shè)為0，可以清空一個(gè)棧

clear()

測(cè)試Stack類的實(shí)現(xiàn)：

Stack類的實(shí)例化測(cè)試

測(cè)試代碼輸出結(jié)果：

測(cè)試結(jié)果

將數(shù)字轉(zhuǎn)換為二進(jìn)制和八進(jìn)制：

進(jìn)制轉(zhuǎn)換算法

測(cè)試轉(zhuǎn)換為二進(jìn)制和八進(jìn)制數(shù)

測(cè)試結(jié)果

回文

參加過競(jìng)賽的小伙伴們應(yīng)該知道，回文就是指一個(gè)單詞、短語或數(shù)字，從前往后寫和從后往前寫都是一樣的現(xiàn)象。比如“dad”，“racecar”就是回文，數(shù)字10001也是回文。通過對(duì)棧的操作很容易判斷字符串是否回文。

判斷是否回文算法實(shí)現(xiàn)

測(cè)試回文算法邏輯

測(cè)試結(jié)果

用棧模擬遞歸

常規(guī)的遞歸函數(shù)，計(jì)算任何數(shù)字的階乘：

普通的遞歸函數(shù)計(jì)算階乘

使用棧模擬遞歸過程

棧模擬遞歸算法