丨棧如何實現(xiàn)瀏覽器前進和后退功能

我第一次接觸這種數(shù)據(jù)結(jié)構(gòu)的時候，就對它存在的意義產(chǎn)生了很大的疑惑。因為我覺得，相比數(shù)組和鏈表，棧帶給我的只有限制，并沒有任何優(yōu)勢。那我直接使用數(shù)組或者鏈表不就好事實上，從功能上來說，數(shù)組或鏈表確實可以替代棧，但你要知道，特定的數(shù)據(jù)結(jié)構(gòu)是對特定場景的抽象，而且，數(shù)組或鏈表了太多的操作接口，操作上的確靈活自由，但使用時就比較不可控，自然也就更容易出錯。如何實現(xiàn)一個“棧從剛才棧的定義里，我們可以看出，棧主要包含兩個操作，入棧和出棧，也就是在棧頂插入一個數(shù)據(jù)和從棧頂刪除一個數(shù)據(jù)。理解了棧的定義之后，我們來看一看如何用代碼實現(xiàn)一個實際上，棧既可以用數(shù)組來實現(xiàn)，也可以用鏈表來實現(xiàn)。用數(shù)組實現(xiàn)的棧，我們叫作棧，用鏈表實現(xiàn)的棧，我們叫作鏈式棧。 我這段代碼是用Java來實現(xiàn)的，但是不涉及任何高級語法，并且我還用中了詳細的注//publicclassArrayStackprivateString[]items;//privateint privateint 6//初始化數(shù)組，申請一個大小為npublicArrayStack(intn)this.items=newthis.n=this.count= publicbooleanpush(Stringitem)//數(shù)組空間不夠了，直接返回falseif(count==n)return//將item放到下標為count的位置，并且countitems[count]= return publicStringpop()//棧為空，則直接返回if(count==0)return//返回下標為count-1的數(shù)組元素，并且棧中元素個數(shù)countStringtmp=items[count-return 33不管是順序棧還是鏈式棧，我們數(shù)據(jù)只需要一個大小為n的數(shù)組就夠了。在入棧和出棧過程中，只需要一兩個臨時變量空間，所以空間復(fù)雜度是O(1)。注意，這里數(shù)據(jù)需要一個大小為n的數(shù)組，并不是說空間復(fù)雜度就是O(n)。因為，這n個空間是必須的，無法省掉。所以我們說空間復(fù)雜度的時候，是指除了原本的數(shù)據(jù)空空間復(fù)雜度分析是不是很簡單？時間復(fù)雜度也不難。不管是順序棧還是鏈式棧，入棧、出棧只涉及棧頂個別數(shù)據(jù)的操作，所以時間復(fù)雜度都是O(1剛才那個基于數(shù)組實現(xiàn)的棧，是一個固定大小的棧，也就是說，在初始化棧時需要事先指定棧的大小。當(dāng)棧滿之后，就無法再往棧里添加數(shù)據(jù)了。盡管鏈式棧的大小不受限，但要t你還記得，我們在數(shù)組那一節(jié)，是如何來實現(xiàn)一個支持動態(tài)擴容的數(shù)組的嗎？當(dāng)數(shù)組空間不夠時，我們就重新申請一塊更大的內(nèi)存，將原來數(shù)組中數(shù)據(jù)統(tǒng)統(tǒng)拷貝過去。這樣就實現(xiàn)了一個支持動態(tài)擴容的數(shù)組?？梢粤恕．?dāng)棧滿了之后，我們就申請一個更大的數(shù)組，將原來的數(shù)據(jù)搬移到新數(shù)組中。我畫了一張圖，你可以對照著理解一下。 O(1)。但是，對于入棧操作來說，情況就不一樣了。當(dāng)棧中有空閑空間時，入棧操作的時間復(fù)雜度為O(1O(n)。也就是說，對于入棧操作來說，最好情況時間復(fù)雜度是O(1)，情況時間復(fù)雜度是O(n)。定義不涉及內(nèi)存搬移的入棧操作為simple-push操作，時間復(fù)雜度為O(1)如果當(dāng)前棧大小為K，并且已滿，當(dāng)再有新的數(shù)據(jù)要入棧時，就需要重新申請2倍大小的內(nèi)存，并且做K個數(shù)據(jù)的搬移操作，然后再入棧。但是，接下來的K-1次入棧操作，我們都不需要再重新申請內(nèi)存和搬移數(shù)據(jù)，所以這K-1次入棧操作都只需要一個simple-push你應(yīng)該可以看出來，這K次入棧操作，總共涉及了K個數(shù)據(jù)的搬移，以及K次simple-pushKK和一個simple-push操作。以此類推，入棧操作的均攤時間復(fù)雜度就為O(1)。OO，只有在個別時刻才會為O(n)，所以把耗時多的入棧操作的時間均攤到其他入棧操作上，平均情況下的耗時O(1)。函數(shù)調(diào)用棧,用來函數(shù)調(diào)用時的臨時變量。每進入一個函數(shù)，就會將臨時變量作為一個棧幀入棧，當(dāng)被調(diào)用函數(shù)執(zhí)行完成，返回之后，將這個函數(shù)對應(yīng)的棧幀出棧。為了讓你更好地理解，我們一塊來看下這段代碼的執(zhí)行過程。intmain()inta=intret=intres=ret=add(3,res=a+printf("%d",reuturn9intadd(intx,inty)intsum=sum=x+return15從代碼中我們可以看出，main()函數(shù)調(diào)用了add()函數(shù)，獲取計算結(jié)果，并且與臨時變量a相加，最后打印res的值。為了讓你清晰地看到這個過程對應(yīng)的函數(shù)棧里出棧、入棧的操作，我畫了一張圖。圖中顯示的是，在執(zhí)行到add()函數(shù)時，函數(shù)調(diào)用棧的情況。為了方便解釋，我將算術(shù)表達式簡化為只包含加減乘除四則運算，比如：319+44-3。對于這個四則運算，我們?nèi)四X可以很快求解出答案，但是對于計算機來說，理解這實際上，編譯器就是通過兩個棧來實現(xiàn)的。其中一個保存操作數(shù)的棧，另一個是保存運算符的棧。我們從左向右遍歷表達式，當(dāng)遇到數(shù)字，我們就直接壓入操作數(shù)棧；當(dāng)遇到運算符，就與運算符棧的棧頂元素進行比較。2我將3+5*8-6這個表達式的計算過程畫成了一張圖，你可以結(jié)合圖來理解我剛講的計算過{}，并且它們可以任意嵌套。比如，{[{}]}或[{()}([])]等都為合法格式，而{[}()]或[({)]為不合為格我們使用兩個棧，XY，X，當(dāng)點擊后退按鈕時，再依次從棧X中出棧，并將出棧的數(shù)據(jù)依次放入棧Y。當(dāng)我們點擊前進按鈕時，我們依次從棧Y中取出數(shù)據(jù)，放入棧X中。當(dāng)棧X中沒有數(shù)據(jù)時，那就說明沒有頁面可以繼續(xù)后退瀏覽了。當(dāng)棧Y中沒有數(shù)據(jù)，那就說明沒有頁面可以點擊前進按鈕瀏覽了。a，b，ca，b，ccacbX彈出，并且依次放入到棧Y。這個時候，兩個棧的數(shù)據(jù)就是這個樣子：bbbY棧，放入棧X中。此時兩個棧的數(shù)據(jù)是這個樣子：bdc復(fù)查看了，所以需要清空棧Y。此時兩個棧的數(shù)據(jù)這個樣子：O(1我們都知道，JVM內(nèi)存管理中有個“堆棧”的概念。棧內(nèi)存用來局部變量和方法調(diào)用，堆內(nèi)存用來Java中的對象。那JVM里面的“?！备覀冞@里說的“?！笔遣晃乙褜⒈竟?jié)內(nèi)容相關(guān)的詳細代碼更新 售賣。頁面已增加防盜追蹤，將依法其上一 07|鏈表（下）：如何輕松寫出正確的鏈表代碼下一 09|隊列：隊列程池等有限資源池中的應(yīng)阿杜S考特

175代碼區(qū)：方法體的二進制代碼。高級調(diào)度（作業(yè)調(diào)度）、中級調(diào)度（內(nèi)存調(diào)度）、置 91…

219S

173代碼區(qū)：方法體的二進制代碼。高級調(diào)度（作業(yè)調(diào)度）、中級調(diào)度（內(nèi)存調(diào)度）、姜

133小洋 66…鯽 對我來說理解有些，所 28實現(xiàn)代碼：（棧的數(shù)組實現(xiàn)publicclassStackOfArray<Item>implements Item[]a=(Item[])new 17清以輕 pre和nex