xx99av.com-日韩成人小视频,国产成人激情视频,精品一区二区三区视频,日本麻豆一区二区三区视频

如果你學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)，就一定會(huì)遇到“堆”,"棧","堆棧",這些對(duì)于小白來(lái)說(shuō)有些頭大，下面就來(lái)科普一下何謂堆棧？

 

按照WIKI的定義：

 

堆棧（英語(yǔ)：stack），是計(jì)算機(jī)科學(xué)中一種特殊的串列形式的抽象數(shù)據(jù)類型，其特殊之處在于只能允許在鏈表或數(shù)組的一端（稱為堆棧頂端指針，英語(yǔ)：top）進(jìn)行加入數(shù)據(jù)（英語(yǔ)：push）和輸出數(shù)據(jù)（英語(yǔ)：pop）的運(yùn)算。另外堆棧也可以用一維數(shù)組或鏈表的形式來(lái)完成。堆棧的另外一個(gè)相對(duì)的操作方式稱為隊(duì)列。需要記住的是，堆：順序隨意，棧：后進(jìn)先出(Last-In/First-Out)。
這里的pop和push到都是什么意思？其實(shí)這是堆棧數(shù)據(jù)結(jié)構(gòu)使用兩種基本操作：推入（壓棧，push）和彈出（彈棧，pop）：

 

推入：將數(shù)據(jù)放入堆棧的頂端（數(shù)組形式或串列形式），堆棧頂端top指針加一。

彈出：將頂端數(shù)據(jù)數(shù)據(jù)輸出（回傳），堆棧頂端數(shù)據(jù)減一。
如要了解堆棧，應(yīng)將之拆開分析。

 

堆的概念：

 

堆（英語(yǔ)：Heap）是計(jì)算機(jī)科學(xué)中的一種特別的樹狀數(shù)據(jù)結(jié)構(gòu)。通常是一個(gè)可以被看做一棵樹的數(shù)組對(duì)象。若是滿足以下特性，即可稱為堆：“給定堆中任意節(jié)點(diǎn) P 和 C，若 P 是 C 的父節(jié)點(diǎn)，那么 P 的值會(huì)小于等于（或大于等于） C 的值”。若父節(jié)點(diǎn)的值恒小于等于子節(jié)點(diǎn)的值，此堆稱為最小堆（英語(yǔ)：min heap）；反之，若父節(jié)點(diǎn)的值恒大于等于子節(jié)點(diǎn)的值，此堆稱為最大堆（英語(yǔ)：max heap）。在堆中最頂端的那一個(gè)節(jié)點(diǎn)，稱作根節(jié)點(diǎn)（英語(yǔ)：root node），根節(jié)點(diǎn)本身沒有父節(jié)點(diǎn)（英語(yǔ)：parent node）。
棧的概念

 

棧（stack）又名堆棧，它是一種運(yùn)算受限的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。這一端被稱為棧頂，相對(duì)地，把另一端稱為棧底。棧就是一個(gè)桶，后放進(jìn)去的先拿出來(lái)，它下面本來(lái)有的東西要等它出來(lái)之后才能出來(lái)（先進(jìn)后出）

 

棧(Stack)是操作系統(tǒng)在建立某個(gè)進(jìn)程時(shí)或者線程（在支持多線程的操作系統(tǒng)中是線程）為這個(gè)線程建立的存儲(chǔ)區(qū)域，該區(qū)域具有FIFO的特性，在編譯的時(shí)候可以指定需要的Stack的大小。
堆棧

 

其實(shí)堆棧本身就是棧，只是換了個(gè)抽象的名字。其特性是： 最后一個(gè)放入堆棧中的物體總是被最先拿出來(lái)，這個(gè)特性通常稱為后進(jìn)先出(LIFO)隊(duì)列。堆棧中定義了一些操作。 兩個(gè)最重要就是上述提到的PUSH和POP。PUSH操作在堆棧的頂部加入一個(gè)元素，POP操作相反，在堆棧頂部移去一個(gè)元素，并將堆棧的大小減一。
工作原理

 

對(duì)于工作方式你可能還是一頭霧水，以自助餐托盤為例解釋一下，你就會(huì)更加明了：

 

作為堆棧如何工作的一個(gè)例子，可以把它看成一個(gè)彈簧加載托盤分發(fā)器，這種類型經(jīng)常在自助餐廳中發(fā)現(xiàn)。每個(gè)托盤上都刻有數(shù)字。托盤依次從頂部裝入，每個(gè)托盤都放置在已經(jīng)裝入的托盤上，彈簧進(jìn)行壓縮，以便在必要時(shí)為更多托盤留出空間。例如，在圖中，托盤編號(hào)為42、23、2、9，先裝載42個(gè)托盤，后裝載9個(gè)托盤。

 最后一個(gè)托盤是9號(hào)。因此，“第一個(gè)出來(lái)”的盤子也是9號(hào)。當(dāng)顧客從托盤堆的頂部取出托盤時(shí)，第一個(gè)托盤是9號(hào)，第二個(gè)托盤是2號(hào)。然后更多的托盤被添加。這些托盤將不得不在我們裝載第一個(gè)托盤之前從堆棧上下來(lái)。在托盤堆的任意順序的push和pop出之后，托盤42仍然在底部。只有在42號(hào)托盤從堆棧頂部彈出后，堆棧才會(huì)再次清空。

 

而堆棧通常被放置在機(jī)器的最上面的地址區(qū)域。它們通常從最高的內(nèi)存位置增長(zhǎng)到較低的內(nèi)存位置，允許在程序內(nèi)存末端和堆棧“頂部”之間的內(nèi)存使用中獲得最大的靈活性。在我們的討論中，堆棧在內(nèi)存中是“向上”增長(zhǎng)還是“向下”增長(zhǎng)基本上是不相關(guān)的。堆棧的“top”元素是最后被推入并將首先被彈出的元素。堆棧的“底部”元素在刪除時(shí)將使堆棧為空。

 

二者區(qū)別

 

堆是在程序運(yùn)行時(shí)，而不是在程序編譯時(shí)，申請(qǐng)某個(gè)大小的內(nèi)存空間。即動(dòng)態(tài)分配內(nèi)存，對(duì)其訪問(wèn)和對(duì)一般內(nèi)存的訪問(wèn)沒有區(qū)別。它由程序員分配和回收。

 

棧就是一個(gè)桶，后放進(jìn)去的先拿出來(lái)，它下面本來(lái)有的東西要等它出來(lái)之后才能出來(lái)。（后進(jìn)先出）由系統(tǒng)自動(dòng)分配和回收。

 

堆棧緩存方式

 

棧使用的是一級(jí)緩存， 他們通常都是被調(diào)用時(shí)處于存儲(chǔ)空間中，調(diào)用完畢立即釋放。

 

堆則是存放在二級(jí)緩存中，生命周期由虛擬機(jī)的垃圾回收算法來(lái)決定（并不是一旦成為孤兒對(duì)象就能被回收）。所以調(diào)用這些對(duì)象的速度要相對(duì)來(lái)得低一些。棧的優(yōu)勢(shì)是，存取速度比堆要快，僅次于直接位于CPU中的寄存器。

 

棧：在Windows下,棧是向低地址擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)，是一塊連續(xù)的內(nèi)存的區(qū)域。意思是棧頂?shù)牡刂泛蜅５淖畲笕萘渴窍到y(tǒng)預(yù)先規(guī)定好的，在 WINDOWS下，棧的大小是2M（也有的說(shuō)是1M，總之是一個(gè)編譯時(shí)就確定的常數(shù)），如果申請(qǐng)的空間超過(guò)棧的剩余空間時(shí)，將提示overflow。因此，能從棧獲得的空間較小。

 

堆：堆是向高地址擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)，是不連續(xù)的內(nèi)存區(qū)域。這是由于系統(tǒng)是用鏈表來(lái)存儲(chǔ)的空閑內(nèi)存地址的，自然是不連續(xù)的，而鏈表的遍歷方向是由低地址向高地址。堆的大小受限于計(jì)算機(jī)系統(tǒng)中有效的虛擬內(nèi)存。由此可見，堆獲得的空間比較靈活，也比較大。

 

作為“堆”的數(shù)據(jù)空間，必須是靈活的，因?yàn)槌汕先f(wàn)的程序員在寫什么程序是未知的。但可知道的一點(diǎn)，就是他們是跑在確定的某個(gè)OS里面的。因此，也不過(guò)就是給系統(tǒng)管理的數(shù)據(jù)空間起了個(gè)名字，叫棧；給程序員使用的空間，起了個(gè)名，叫堆。