Stack的三種含義

        學習編程的時候，經常會看到 stack 這個詞，它的中文名字叫做"棧"。

        理解這個概念，對于理解程序的運行至關重要。容易混淆的是，這個詞其實有三種含義，適用于不同的場合，必須加以區分。

        含義一：數據結構

        stack 的第一種含義是一組數據的存放方式，特點為 LIFO，即后進先出（Last in, first out）。

        在這種數據結構中，數據像積木那樣一層層堆起來，后面加入的數據就放在最上層。使用的時候，最上層的數據第一個被用掉，這就叫做"后進先出"。

        與這種結構配套的，是一些特定的方法，主要為下面這些。

• push：在最頂層加入數據。
• pop：返回并移除最頂層的數據。
• top：返回最頂層數據的值，但不移除它。
• isempty：返回一個布爾值，表示當前 stack 是否為空棧。

        含義二：代碼運行方式

        stack 的第二種含義是"調用棧"（call stack），表示函數或子例程像堆積木一樣存放，以實現層層調用。

        下面以一段 Java 代碼為例（來源）。

class Student{    
int age;                  
String name;          
public Student (int Age, String Name)
    {
        this.age = Age;
        setName (Name);
    }
    public void setName (String Name)
    {
        this.name = Name;
    }
}public class Main
{
    public static void main (String[] args) {
            Student s;
            s = new Student (23,"Jonh");   }
}

        上面這段代碼運行的時候，首先調用 main 方法，里面需要生成一個 Student 的實例，于是又調用 Student 構造函數。在構造函數中，又調用到 setName 方法。

        這三次調用像積木一樣堆起來，就叫做"調用棧"。程序運行的時候，總是先完成最上層的調用，然后將它的值返回到下一層調用，直至完成整個調用棧，返回最后的結果。

        含義三：內存區域

        stack 的第三種含義是存放數據的一種內存區域。程序運行的時候，需要內存空間存放數據。一般來說，系統會劃分出兩種不同的內存空間：一種叫做 stack（棧），另一種叫做 heap（堆）。

        它們的主要區別是：stack 是有結構的，每個區塊按照一定次序存放，可以明確知道每個區塊的大小；heap 是沒有結構的，數據可以任意存放。因此，stack 的讀取速度要比 heap 快。

        其他的區別還有，一般來說，每個線程分配一個 stack，每個進程分配一個 heap，也就是說，stack 是線程獨占的，heap 是線程共用的。此外，stack 創建的時候，大小是確定的，數據超過這個大小，就發生 stack overflow 錯誤，而 heap 的大小是不確定的，需要的話可以不斷增加。

        根據上面這些區別，數據存放的規則是：只要是局部的、占用空間確定的數據，一般都存放在 stack 里面，否則就放在 heap 里面。請看下面這段代碼（來源）。

public void Method1(){
    int i=4;    
        int y=2;    
        class1 cls1 = new class1();
}

        上面代碼的 Method1 方法，共包含了三個變量：i, y 和 cls1。其中，i和y的值是整數，內存占用空間是確定的，而且是局部變量，只用在 Method1 區塊之內，不會用于區塊之外。cls1 是指針變量，指向一個對象的實例，指針變量占用的大小是確定的，但是對象實例以目前的信息無法確知所占用的內存空間大小。

        這三個變量和一個對象實例在內存中的存放方式如下。

        從上圖可以看到，i、y和 cls1 都存放在 stack，因為它們占用內存空間都是確定的，而且本身也屬于局部變量。但是，cls1 指向的對象實例存放在 heap，因為它的大小不確定。作為一條規則可以記住，所有的對象都存放在 heap。

        接下來的問題是，當 Method1 方法運行結束，會發生什么事？

        回答是整個 stack 被清空，i、y和 cls1 這三個變量消失，因為它們是局部變量，區塊一旦運行結束，就沒必要再存在了。而 heap 之中的那個對象實例繼續存在，直到系統的垃圾清理機制（garbage collector）將這塊內存回收。因此，一般來說，內存泄漏都發生在 heap，即某些內存空間不再被使用了，卻因為種種原因，沒有被系統回收。