PriorityQueue 是線性結構嗎？90%的人都搞錯了！
文章首發於「陳樹義」公眾號及個人博客 shuyi.tech
其實這個問題的完整描述是：Java 中的 PriorityQueue 實現，其數據的邏輯結構是線性結構嗎？其數據的物理結構又是什麼？
估計很多人的答案是：PriorityQueue 是線性結構，因為 PriorityQueue 是優先級隊列的實現，隊列不就是線性結構的嗎？但在PriorityQueue 的實現中，其數據的邏輯結構是樹形結構，其物理結構是順序存儲結構。
要弄明白這個問題，我們必須先弄明白什麼是數據的邏輯結構，什麼是數據的物理結構。
顧名思義，數據的邏輯結構指的是數據是怎麼組織起來的，數據的物理結構指的是數據是怎麼存儲的。 數據的邏輯結構與物理結構，是數據結構兩個非常重要的要素。但你知道數據有幾種邏輯結構、幾種物理結構嗎？
數據的邏輯結構
數據的邏輯結構指的是數據是如何組織起來的，反映數據元素之間的邏輯關係，它更加貼近於現實。 例如現實生活中樹榦與樹葉就是樹形結構，排隊的隊伍就是線性關係。
數據的邏輯結構一般有四種，分別是：線性結構、集合結構、樹形結構、網絡結構。 其中，我們把集合、樹形結構、網絡結構統稱為非線性結構。
線性結構
線性結構指的是數據結構中的元素存在一對一的相互關係。 例如：數組是一種線性結構，其下標與元素一一對應。鏈表也是一種線性結構，其元素之間是一個接着一個的。生活中有很多類似的例子，例如排隊買票的隊伍就是一個線性結構。超市裡排布整齊的商品，也是一個線性結構。
集合結構
集合結構指的是元素之間除了「同屬一個集合」的關係之外，再無其他關係。 例如數學中的整數就是一個集合，所有小數也是一個集合。
樹形結構
樹形結構指的是元素存在一對多的關係。 例如水果有香蕉、草莓、西瓜等，這種邏輯結構就是樹形結構。
網絡結構
網絡結構指的是元素存在多對多的關係。 網絡結構也叫做網狀結構，它是多對多的關係。比如城市的交通網絡，每棟房子與其他房子都有許多條路。
數據的物理存儲結構
數據的物理結構指的是數據是如何存儲的，反映數據的存儲結構。 數據的存儲結構分為四種：順序存儲、鏈式存儲、索引存儲、散列存儲。 一般我們將這四種物理結構分為順序存儲結構與非順序存儲結構。順序存儲是順序存儲結構，鏈式存儲、索引存儲、散列存儲均屬於非順序存儲結構。
數據的順序存儲結構的特點是：藉助元素的相對位置來表示數據元素之間的邏輯關係。非順序存儲的特點是：藉助指示元素存儲地址的指針表示數據元素之間的邏輯關係。
註：有些朋友說數據的物理存儲結構只有順序存儲、鏈式存儲兩種，索引存儲和散列存儲是不存在的。對此，後續我專門寫篇文章來聊聊這個事情。
順序存儲
順序存儲指的是數據在內存當中是按照順序存儲的，邏輯結構上相鄰的元素在物理結構上也是相鄰的。Java 中的 ArrayList 就是通過順序存儲的方式實現的。
鏈式存儲
鏈式存儲指的是元素之間的邏輯順序，並不是通過內存順序來分配的，而是通過一個引用組織起來的。也就是說，邏輯上相鄰的元素，在物理存儲位置上是不相鄰的。Java 中的 LinkedList 就是通過鏈式存儲的方式實現的。
索引存儲
索引存儲指的是元素之間的邏輯關係，是通過一張索引表來存儲的。這張索引表有很多個索引項，每個索引項存儲兩個信息：關鍵字、數據存儲地址。我們通過關鍵字可以找到對應的數據存儲地址。這就像書籍的目錄一樣，關鍵字就是章節名，數據存儲地址就是頁碼。我們通過章節名可以快速地找到對應的頁碼，從而快速地找到書籍對應內容。
散列存儲
散列存儲也稱之為哈希存儲，其與索引存儲非常類似，都是通過索引值以及對應的值來實現快速查找。唯一不同的區別是，索引存儲會對索引值進行哈希。應該說散列存儲是索引存儲的一種更加複雜的實現。
辨別思路
看到這裡，我們對數據的邏輯結構、物理結構已經有了基本的認識，也知道它們的常見種類。那我們到底如何去判斷它們是屬於哪種邏輯結構、哪種物理結構呢？
拿 Java 中對於優先級隊列的 PriorityQueue 實現為例。通過閱讀源碼我們得知其底層使用了二叉堆實現，而二叉堆本身其實就是一顆二叉樹。即對於 PriorityQueue 來說，其數組最終是通過下圖這種邏輯結構組織起來的，因此 PriorityQueue 的邏輯結構是樹形結構。
從 PriorityQueue 的源碼，我們可以知道 PriorityQueue 的數據最終是通過一個對象數組存儲的，而數組的物理結構是順序存儲的。因此對於 PriorityQueue 來說，其物理結構是順序存儲結構。
通過 PriorityQueue 這個例子，我們可以總結出判斷數據的邏輯結構、物理結構的思路：判斷邏輯結構，要看數據是如何組織起來的。要判斷物理結構，則是要看數據最終是如何存儲的。
如果對 PriorityQueue 的源碼實現感興趣，可以閱讀：集合系列 Queue（九）：PriorityQueue – 陳樹義的博客
我們再用這個辦法來判斷一下 TreeMap 這個類。
TreeMap 是 Java 中非常經典的實現，其底層是基於紅黑樹的實現，即其最終會將所有數據組織成一顆紅黑樹，因此 TreeMap 的邏輯結構是樹形結構。通過閱讀 TreeMap 的源碼，我們知道 TreeMap 的數據最終是通過 Entry 這個類存儲的，因此 TreeMap 的物理結構是鏈式存儲結構。
如果對 TreeMap 的源碼實現感興趣，可以閱讀：集合系列 Map（十五）：TreeMap – 陳樹義的博客
最後我們拿比較複雜的 LinkedBlockingQueue 來分析一下。
很多人會說隊列就是一種特殊的數組，而數組是順序存儲的，因此隊列就是順序存儲的。如果將這個結論套用在 LinkedBlockingQueue 上，那是否可以得出同樣的結論，即 LinkedBlockingQueue 也是順序存儲的呢？
前面我們說過：不要用直覺去判斷，而要根據定義去判斷。 即判斷數據的邏輯結構、物理結構的思路是：判斷邏輯結構，要看數據是如何組織起來的。要判斷物理結構，則是要看數據最終是如何存儲的。
LinkedBlockingQueue 是 Java 中的阻塞隊列實現，其最終會將數組組織成一個隊列，因此其邏輯結構上屬於線性表。通過閱讀源碼，我們可以知道 LinkedBlockingQueue 的元素是存儲在 Node 節點上的，因此 LinkedBlockingQueue 的物理結構屬於鏈式存儲。
總結
本文一開始通過 PriorityQueue 的例子，引入了邏輯結構與物理結構這個話題。接着介紹了四種邏輯結構：線性表、集合、樹狀結構、網絡結構。
緊接着介紹了四種物理存儲結構，分別是：順序存儲、鏈式存儲、索引存儲、哈希存儲。
接着通過 PriorityQueue 的例子，得出判斷數據的邏輯結構和物理結構的思路：判斷邏輯結構，要看數據是如何組織起來的。要判斷物理結構，則是要看數據最終是如何存儲的。 最後再通過 TreeMap 和 LinkedBlockingQueue 這兩個例子，帶大家實踐判斷思路。
看到這裡文章就結束了，如果你喜歡本篇文章，歡迎點贊、在看、轉發、留言支持我，我們下次見~
