Java語言中的棧(stack)與堆(heap)都是java用來在Ram中存放數(shù)據(jù)的地方，屬于計(jì)算機(jī)的內(nèi)存區(qū)域，與C++不同，java自動(dòng)管理?xiàng)：投眩琷ava程序員不能直接地設(shè)置?；蚨?，相關(guān)的java堆棧的知識在前面的文章中都有學(xué)習(xí)過，今天我們來看看堆棧兩種實(shí)現(xiàn)方式，下面來介紹一下兩種java堆棧實(shí)現(xiàn)方式。

Java堆棧兩種實(shí)現(xiàn)方式分別是基于向量和基于列表的：

堆棧兩種實(shí)現(xiàn)方式之一：基于向量的堆棧

可以先來考慮一個(gè)傳統(tǒng)的基于堆棧的比擬：快餐店中盤子的存放。用餐開始的時(shí)候，獲得從堆棧中取出的盤子。刪除一個(gè)盤子的過程就是從堆棧中彈出一個(gè)盤子的過程。當(dāng)盤子歸還后，它們被壓回到堆棧中?，F(xiàn)在，假設(shè)盛放盤子的容器被標(biāo)上刻度，可能是用來計(jì)算堆棧中盤子的數(shù)量。觀察一下，這看起來像一個(gè)斜向一邊的向量(如圖)

采用這個(gè)比擬，基于向量的堆棧實(shí)現(xiàn)可以通過將堆棧的“頂”與向量的“尾”對齊來完成，可以參見上圖。我們提供了兩個(gè)構(gòu)造函數(shù)，其中一個(gè)提供向量的初始容量：

下面這個(gè)圖說明一個(gè)包含n個(gè)元素的基于向量的堆棧，棧頂是由底層向量的長度隱含說明的，箭頭表明增長方向。

為了向堆棧中添加元素，只需要簡單地使用Vector類的add方法。當(dāng)需要從堆棧中刪除一個(gè)元素的時(shí)候，將最后一個(gè)元素刪除，并返回它的值。

add方法將元素添加到向量的尾部，如果必要的話對向量大小進(jìn)行擴(kuò)展。注意，如果向量具有n個(gè)元素，這個(gè)元素被加入到第n個(gè)位置，并將元素的數(shù)量增加到n+l。刪除一個(gè)元素的過程與此相反：它刪除并返回最后一個(gè)元素(我們在這里使用了對稱的原理。我們將基于這個(gè)概念設(shè)計(jì)幾對增加和刪除方法)。除了不修改堆棧之外，get方法與remove類似。通過查詢底層向量的大小信息，堆棧的大小很容易確定。當(dāng)然，當(dāng)向量為空的時(shí)候，它所支持的堆棧也是空的。

堆棧兩種實(shí)現(xiàn)方式之二：基于列表的堆棧

只有棧頂一端可以被修改。因此，使用單鏈表尋求一個(gè)堆棧的高效實(shí)現(xiàn)是明智的選擇。因?yàn)閱捂湵硖幚砹斜眍^的效率比處理列表尾的效率要高，我們將棧頂與單鏈表的頭對齊(見下圖)。

add方法僅僅執(zhí)行addFirst,remove 操作僅僅執(zhí)行removeFirst。因?yàn)橐呀?jīng)實(shí)現(xiàn)了列表的remove操作，使之返回被刪除的值，所以這個(gè)值可以通過堆棧的remove方法被傳遞。

其余的方法就是來自于單鏈表的類似方法的包裝器。由于堆棧操作是鏈表操作的平凡表示，它們的復(fù)雜度與鏈表中對應(yīng)的操作是相同的，每一個(gè)方法的運(yùn)行時(shí)間都是常量時(shí)間。

應(yīng)該注意，任何實(shí)現(xiàn)List接口的結(jié)構(gòu)都足以實(shí)現(xiàn)堆棧。然而，已經(jīng)見過的各種列表之間的區(qū)別集中體現(xiàn)在提供對列表尾的快速訪問上。由于不需要訪問堆棧的棧底，列表的其他實(shí)現(xiàn)不會(huì)有優(yōu)越性，因此使用單鏈表實(shí)現(xiàn)。

總之基于向量和列表就是java堆棧兩種實(shí)現(xiàn)方式，希望大家可以好好學(xué)習(xí)上面對堆棧兩種實(shí)現(xiàn)方式的內(nèi)容，相信有了以上實(shí)際例子的列舉，會(huì)對大家理解學(xué)習(xí)這兩種堆棧實(shí)現(xiàn)方式有所幫助。另外可以在java教程中更深入的學(xué)習(xí)堆棧的實(shí)現(xiàn)方式。