導讀
為什麼要學習數據結構？
數據結構是關於如何組織（存儲）數據的！編程實踐中經常涉及到組織（存儲）數據，所以要學習數據結構。
那麼為啥還要學習抽象數據類型（Abstract Data Type，ADT）呢？
ADT描述了數據集、指明瞭在數據集上可能執行的操作。ADT是一種規範，它和具體的編程語言無關。儘管Java API提供多種數據結構，但是如果遇到不適用的情形，就需要針對這種情形定義ADT，然後使用Java實現它。況且如果不深入全面地掌握數據結構這方面的知識，就無法理解和合理的使用Java API提供的數據結構。
數據結構和ADT是什麼關係呢？
ADT是一個規範，用於一組值以及對這組值執行的操作。而數據結構是使用編程語言對ADT的實現。
那麼如何描述ADT呢？
我們僅描述數據和操作，不指明如何保存數據以及如何實現操作，會考慮一些實現的細節，但與具體編程語言無關。
我們藉助UML以及對他們的說明來描述ADT。還可以使用偽代碼，不過UML足以說明問題。
設計ADT的步驟是什麼呢？
確定行為，然後指定數據和操作，並且考慮特殊情況。
ADT Stack（棧）簡介
先讓我們看看新華字典對棧這個字的解釋：
儲存貨物或供旅客住宿的房屋：貨棧。客棧。棧房。
竹木編成的遮蔽物或其他東西：馬棧（養馬的竹木棚）。棧車（古代用竹木編成棚的車子）。
用木料或其他材料架設的通道：棧道。棧橋（一種形似橋樑的建築物，用於裝卸貨物、上下旅客等）。
生活中的棧不考慮對象進出順序，客人到了客棧，他什麼時候走可以，只要他交足了租金，住多久都行，他可能比其他人來的都晚，也比其他人住的久一些。而數據結構當中的棧是一種對象先進後出（Last-In First-Out，LIFO）的集合。
棧更像彈夾，最後壓入彈夾的子彈最先被射出。
我們稱棧中最上面的位置為棧頂，稱棧頂的對象為棧頂對象或棧頂項。
ADT Stack（棧）的規格說明
ADT Stack（棧）操作細節闡述
+push(newEntry:T):void
大家有沒有考慮過，如果待操作的棧滿了，無法再向裡面添加對象了，這時執行入棧操作，我們該如何提示客戶呢？是該拋出異常，還是該置之不理。
似乎都有道理，拋出異常可以提醒客戶，不要再作入棧操作了。但是，拋出異常後，客戶就要處理異常，似乎還不如置之不理，然後客戶在入棧前判斷是否棧滿。
+pop():T與+peek():T
如果出棧的時候，棧已空，怎麼辦呢？應該返回一個null值嗎？還是應該拋出異常，提示客戶呢？
如果棧中允許存儲null，那麼通過返回null來提示棧已空就不合適了，這樣作客戶無法區分是棧已空還是彈出的對象是null。這種情況下，拋出異常是好方法。
還有一種辦法就是先判斷棧是否為空，然後在決定是否作出棧操作，這樣就不必通過拋出異常來提示客戶了，不過要客戶自己調用isEmpty方法，這樣作等同於將部分實現細節暴露給客戶。
ADT Stack（棧）轉換為接口
讓我們將ADT Stack映射為接口，然後只要實現了這個接口，就可以使用棧這種數據結構了。
棧的應用-程序棧
讓我們來看一下棧在實際中的使用情況
程序棧在Java中被稱為Java棧，它有什麼用呢？
假如，在方法a中調用了方法b，當程序執行到調用方法b的語句時就開始執行方法b，這時b接管了控制權；當方法b執行完，控制權重新回到方法a中，繼續執行方法a中尚未執行的語句。那麼為了保證這種控制權轉換過程中，代碼依然能按預想的正確順序執行，使用了Java棧。
Java棧中的項是什麼呢？
Java棧中的項是一種被稱為活動記錄的對象。這種對象包含了方法的指向當前指令的引用、實參、局部變量，一般地，我們稱當前指令的地址為程序計數器。而活動記錄中包含的是對程序計數器的引用。
看下面的例子
假設我們以行號代表計數器（縮寫為PC），當開始執行main方法時，有一個活動記錄對象被壓入棧中，當執行到funcA時又有一個活動記錄對象被壓入棧中，當執行到funcB又有一個活動記錄對象被壓入棧中，如下圖，按時間順序從左到右的Java棧的變化。
閱讀更多 甜橙很酸 的文章
