[資料結構] 棧 java中的Stack 棧和隊列的差別

棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和删除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧删除元素又稱作出棧或退棧，它是把棧頂元素删除掉，使其相鄰的元素成為新的棧頂元素。

棧的示意圖：

　　stack 類表示後進先出（lifo）的對象堆棧。它通過五個操作對類 vector 進行了擴充 ，允許将向量視為堆棧。它提供了通常的 push 和 pop 操作，以及取堆棧頂點的 peek 方法、測試堆棧是否為空的 empty 方法、在堆棧中查找項并确定到堆棧頂距離的 search 方法。首次建立堆棧時，它不包含項。

deque 接口及其實作提供了 lifo 堆棧操作的更完整和更一緻的 set，應該優先使用此 set，而非此類。例如：

<code>deque&lt;integer&gt; stack = new arraydeque&lt;integer&gt;(); </code>　

成員方法：

e push(e item)  把項壓入堆棧頂部。 　 e pop()  移除堆棧頂部的對象，并作為此函數的值傳回該對象。 　 e peek()  檢視堆棧頂部的對象，但不從堆棧中移除它。 　 boolean empty()  測試堆棧是否為空。 　 int search(object o)  傳回對象在堆棧中的位置，以 1 為基數。　

stack繼承于vector，vector本身是一個可增長的對象數組。 

stack并不要求其中儲存資料的唯一性，當stack中有多個相同的item時，調用search方法，隻傳回與查找對象equal并且離棧頂最近的item與棧頂間距離。

　　判斷stack是否為空，就需要有一個變量來計算目前棧的長度，如果該變量為0，則表示該棧為空。

源碼：

size()方法在父類vector中實作了，在vector裡面有一個變量elementcount來表示容器裡元素的個數。如果為0，則表示容器空。

　　傳回棧頂端的元素，如果棧為空的話，則要抛出異常。

elementat方法也是在vector裡面實作的，實際上是用一個elementdata的object數組來存儲元素的。

　　将棧頂的元素彈出來，如果棧裡有元素，就取最頂端的那個，否則就要抛出異常。

　　通過peek()取到頂端的元素之後，我們需要用removeelementat()方法将最頂端的元素移除。 

removeelementat()方法定義在vector中。

　　這裡用待删除元素的後面元素依次覆寫前面一個元素。這樣，就相當于将數組的實際元素長度給縮短了。

　　将資料入棧

　　将要入棧的元素放到數組的末尾，再将數組長度加1就可以了。addelement（）方法也在vector中（好父親啊）。

　　找到一個最靠近棧頂端的比對元素，然後傳回這個元素到棧頂的距離

對應在vector裡面的實作也相對容易了解：

lastindexof是從數組的末端往前周遊，如果找到這個對象就傳回。如果到頭了，還未找到就傳回個-1。

隊列是fifo的（先進先出），堆棧是filo的（現今後出）

棧是限定隻能在表的一端進行插入和删除操作的線性表。 隊列是限定隻能在表的一端進行插入和在另一端進行删除操作的線性表

棧隻能從頭部取資料，也就最先放入的需要周遊整個棧最後才能取出來，而且在周遊資料的時候還得為資料開辟臨時空間；