棧的特點之一是什麼

什麼是資料結構

棧是一種資料結構。那什麼是資料結構呢？我這裡不給出嚴格的定義，因為對於完全沒有基礎的新人而言，嚴格的定義說了等於沒說。我只從一個簡單的角度舉例說明一下。在初學階段，你可以認為資料結構就是關於資料在計算機中如何組織的一門課程。

比如，我要往一個數組中，存1，3，2這三個整數，那麼，我實際存的時候，是按照從小到大排著存呢，還是從大到小存，還是沒有順序隨便存，這要根據實際的需求來決定。根據需求決定資料儲存的方式。這就是資料結構要研究的內容。

什麼是棧

以前打了糧食，會放到一個筒形的容器裡，這個筒形的容器，大家叫它棧。它的特點是先放進去的糧食要最後才能取出來，後放進去的糧食是最先被取出來。所以中文就用棧這個詞翻譯英文的stack了。

想一想，生活中，還有很多棧的例子。比如疊在一起的碗盤，疊的時候我們是從底往高處疊，但是取的時候，我們是從最上面的一個依次向下取。這也是一個典型的棧：後進先出，先進後出。

那麼Java語言中如何模擬這一個過程呢？首先，我們定義一個名叫Stack的類：

public class Stack { private int［］ data； private int size； private int top = 0； // 指向棧的頂部 public Stack（int size） { this。size = size； this。data = new int［size］； } }

因為我們的課程裡還沒有涉及到泛型，為了簡單起見，我先用整型代替了。如果有些同學，已經有一定的基礎了，也可以看一下泛型版的程式碼：

import java。util。ArrayList；public class Stack { private ArrayList list； private int size； public Stack（int size） { this。size = size； this。list = new ArrayList（size）； } public static void main（String args） { Stack s = new Stack（10）； } }

本文中後面的例子，我還是會使用簡單版本的。

OK，接下來，就是要往類裡新增相關的操作了。先定義一個可以往棧裡寫資料的函式，叫做push：

public void push（int num） { data［top++］ = num； }

這個函式的意義就是，把資料num存到數組裡，並且把遊標向後指一位。邏輯比較簡單。

相對應的，我們還可以繼續定義以下三個方法，分別是取棧頂元素（getTop），出棧（pop），判斷棧是否為空（isEmpty）。

public int pop（int num） { return data［——top］； } public int getTop（int num） { return data［top-1］； } public boolean isEmpty（） { return top == 0； }

好了，一個棧就定義完了（當然，這裡是有問題的，因為我們在push裡，沒有檢查top是否越過了size規定的陣列，出棧的時候，也沒有判斷top是否等於0。這個做為今天的第一個作業，請讀者自行新增。）

棧的應用

這個資料結構看上去好簡單啊。肯定有很多人會這樣想，但其實，棧在計算機程式設計中可以說是最基礎也是最重要的資料結構了。其功能之強大，可能出乎很多人的意料。我們先透過一個小例子來體會一下。看這樣一道題目：

輸入一組括號，請判斷這些括號的匹配是否合法。例如

（（）］，不合法，左邊的小括號與右邊的中括號不能匹配。

{［（）］}，合法的，所有的括號都可以正確匹配。

{（}），不合法，順序是錯的。

（（（）），不合法，右括號少了一個。

大家可以先自己想一下，這個問題怎麼解決，自己寫一寫，看看能不能搞得定。如果不使用棧，自己窮舉所有情況，逐個去處理的話，好像有點麻煩。

我們來分析一下。如果遇到第一個右括號，那與之配對的一定是離它最近的那個左括號，如果離它最近的左括號的型別與這個右括號的型別是一樣的（比如都是小括號），那這就是一次成功的配對。把一組成功配對的括號從括號序列中刪去，不會影響原來序列是否合法這個屬性，就是說原來合法的，仍然合法，原來不合法的，仍然不合法。透過這樣的辦法就可以化簡題目了。

演算法是有了，怎麼實現呢？遇到右括號，只去檢查離它最近的，如果匹配上了，就把左右括號一起刪掉，這不就是棧嗎？每次都只檢查棧頂的左括號，如果與右括號匹配上了，就把左括號出棧（刪掉）。

好了，資料結構有了，演算法有了，寫成程式就太簡單了：

public static void main（String args［］） throws IOException { byte［］ buf = new byte［128］； int length = System。in。read（buf）； Stack s = new Stack（128）； for （int i = 0； i < length； i++） { if （buf［i］ == ‘（’ || buf［i］ == ‘［’ || buf［i］ == ‘{’） { s。push（buf［i］）； } else if （buf［i］ == ‘）’） { if （s。getTop（） == ‘（’） s。pop（）； else { System。out。println（“1 unmatch！”）； System。exit（1）； } } else if （buf［i］ == ‘］’） { if （s。getTop（） == ‘［’） s。pop（）； else { System。out。println（“2 unmatch！”）； System。exit（1）； } } else if （buf［i］ == ‘}’） { if （s。getTop（） == ‘{’） s。pop（）； else { System。out。println（“3 unmatch！”）； System。exit（1）； } } } if （！s。isEmpty（）） System。out。println（“4 unmatch！”）； else System。out。println（“matched~”）； }

雖然程式碼很長，但其實邏輯非常簡單易懂。這裡漏了一種情況，那就是左括號少，右括號多的情況。這個也留做作業（其實就是getTop和pop的時候要做檢查）

Java虛擬機器的實現是基於棧的

Java虛擬機器規範裡定義了Java所使用的位元組碼。我們知道Java檔案要先編譯成位元組碼檔案，也就是class檔案，但是大家有沒有想過，class檔案裡都是些什麼呢？class檔案的結構，我以後會專門講。今天只演示一個簡單的例子，讓大家有個初步的感覺。先看這樣一個原始檔：

public class Main { // Main。java public static int add（int a， int b）{ return a + b； } }

執行以下命令：

javac Main。javajavap -c Main

可以看到這樣的輸出：

public static int add（int， int）； Code： 0： iload_0 1： iload_1 2： iadd 3： ireturn

add 函式被編成了四條位元組碼指令，這四條位元組碼是什麼意思呢？

你可以認為Java的每一個函式都有一個運算元棧，每條指令就是在對這個運算元棧進行操作。比如 iload_0，就代表把第一個引數 push 進運算元棧，iload_1代表把第二個引數 push 進運算元棧，而 iadd 代表，從棧上連續pop兩次，取兩個數，將其相加，再把結果送到棧上。ireturn 則表示把棧頂的值做為返回值傳給呼叫者。Java位元組碼的整個執行過程都是在這樣一個棧上的。如果用圖來表示，這四個步驟就是：

iload_0，使a先進棧

iload_1， 使b進棧

iadd，做了三件事情，b 和 a 出棧，計算 a+b，將計算結果入棧：

ireturn 將當前棧頂的值返回出去。