資料結構筆記【基礎篇】——棧、隊列、遞歸

棧

• 棧
  • 記憶體中的堆棧和資料結構堆棧不是一個概念，可以說記憶體中的堆棧是真實存在的實體區，資料結構中的堆棧是抽象的資料存儲結構。
  • 記憶體空間在邏輯上分為三部分：代碼區、靜态資料區和動态資料區，動态資料區又分為棧區和堆區。
    • 代碼區：存儲方法體的二進制代碼。進階排程（作業排程）、中級排程（記憶體排程）、低級排程（程序排程）控制代碼區執行代碼的切換。
    • 靜态資料區：存儲全局變量、靜态變量、常量，常量包括final修飾的常量和String常量。系統自動配置設定和回收。
    • 棧區：存儲運作方法的形參、局部變量、傳回值。由系統自動配置設定和回收。
    • 堆區：new一個對象的引用或位址存儲在棧區，指向該對象存儲在堆區中的真實資料。

隊列

• 隊列
  • 比如高性能隊列 Disruptor、Linux 環形緩存，都用到了循環并發隊列；Java concurrent 并發包利用 ArrayBlockingQueue 來實作公平鎖等。
  • 阻塞隊列
    • 阻塞隊列其實就是在隊列基礎上增加了阻塞操作。簡單來說，就是在隊列為空的時候，從隊頭取資料會被阻塞。因為此時還沒有資料可取，直到隊列中有了資料才能傳回；如果隊列已經滿了，那麼插入資料的操作就會被阻塞，直到隊列中有空閑位置後再插入資料，然後再傳回。
  • 并發隊列
    • 線程安全的隊列我們叫作并發隊列。最簡單直接的實作方式是直接在 enqueue()、dequeue() 方法上加鎖，但是鎖粒度大并發度會比較低，同一時刻僅允許一個存或者取操作。實際上，基于數組的循環隊列，利用 CAS 原子操作，可以實作非常高效的并發隊列。這也是循環隊列比鍊式隊列應用更加廣泛的原因。在實戰篇講 Disruptor 的時候，我會再詳細講并發隊列的應用。
  • 基于連結清單的實作方式，可以實作一個支援無限排隊的無界隊列（unbounded queue），但是可能會導緻過多的請求排隊等待，請求處理的響應時間過長。是以，針對響應時間比較敏感的系統，基于連結清單實作的無限排隊的線程池是不合适的。
  • 而基于數組實作的有界隊列（bounded queue），隊列的大小有限，是以線程池中排隊的請求超過隊列大小時，接下來的請求就會被拒絕，這種方式對響應時間敏感的系統來說，就相對更加合理。不過，設定一個合理的隊列大小，也是非常有講究的。隊列太大導緻等待的請求太多，隊列太小會導緻無法充分利用系統資源、發揮最大性能。

遞歸

• 遞歸
  • 遞歸需要滿足的三個條件
    • 1. 一個問題的解可以分解為幾個子問題的解
    • 1. 這個問題與分解之後的子問題，除了資料規模不同，求解思路完全一樣
    • 1. 存在遞歸終止條件
  • 寫遞歸代碼的關鍵就是找到如何将大問題分解為小問題的規律，并且基于此寫出遞推公式，然後再推敲終止條件，最後将遞推公式和終止條件翻譯成代碼。