2.2　抽象數據類型

通常來說，抽象是一個概念，用來定義復雜系統中常見的核心功能。利用這個概念來創建通用的數據結構，就產生了抽象數據類型（ADT）。通過隱藏實現層上的細節，給用戶提供一個通用的、與實現無關的數據結構，抽象數據類型將使得算法的代碼更加簡潔和清晰。抽象數據類型可以使用任何編程語言進行實現，如C++、Java和Scala。在此，我們使用Python實現抽象數據類型，先從向量（vector）開始。

2.2.1　向量

向量是一種存儲數據的單維結構，這是Python中最流行的數據結構之一。在Python中創建向量有以下兩種方法：

• 使用Python列表：創建向量的最簡單方法是使用Python的列表，如下所示：

這段代碼創建了一個有四個元素的列表。

• 使用numpy數組：另一種流行的創建向量的方法是使用NumPy的array函數，如下所示：

注意，在這段代碼中我們使用np.array創建了名為myVector的向量。

2.2.2　棧

棧是一種用于存儲一維列表的線性數據結構。它可以通過后進先出（LIFO）或先進后出（FILO）的方式存儲各項元素。棧所定義的特征是元素的添加和刪除方式，新來的元素會被添加在棧的一端，如果要刪除一個元素，也只能從該端進行。

以下是與棧有關的操作：

• isEmpty：如果棧為空，則返回true。
• push：添加一個新的元素。
• pop：返回最近添加的元素，并將其從棧中刪除。

圖2-4展示了如何使用push和pop操作分別在棧中添加和刪除數據。

圖2-4的上半部分展示了如何使用push操作向棧中添加元素，在步驟1.1、步驟1.2和步驟1.3中，分別使用了三次push操作向棧中添加了三個元素。圖2-4的下半部分展示了從棧中取出所存儲的值，在步驟2.2和步驟2.3中，pop操作以LIFO方式從棧中取出了兩個元素。

下面我們在Python中創建一個名為Stack的類，并在這里定義所有與棧相關的操作。這個類的代碼如下：

要將四個元素壓入棧中，可以使用如圖2-5所示的代碼。

注意，圖2-5的代碼創建了一個有四個數據元素的棧。

棧的時間復雜度

我們看看棧的時間復雜度（使用大O記號）：

需要注意的是，上表中提到的四種操作，其性能都不取決于棧的規模。

實例

在很多用例中，棧都被當作數據結構來使用。例如，當用戶想在Web瀏覽器中瀏覽所有歷史記錄時，這是一種LIFO數據訪問模式，可以使用棧來存儲歷史記錄。另一個例子是當用戶想在文字處理軟件中進行Undo操作時，也可以使用棧來存儲歷史記錄。

2.2.3　隊列

同棧一樣，隊列也用一維結構來存儲n個元素，元素是以先進先出的形式進行添加和刪除的。隊列的一端稱為隊尾（rear），另一端稱為隊首（front）。當元素從隊首被移出時，這種操作稱為出隊（dequeue）。當在隊尾添加元素時，這種操作稱為入隊（enqueue）。

圖2-6的上半部分展示了入隊操作。步驟1.1、步驟1.2、步驟1.3為隊列添加了三個元素，最后得到的隊列如步驟1.4所示。此時，Yellow為隊尾，Red為隊首。

圖2-6的下半部分展示了出隊操作。步驟2.2、步驟2.3和步驟2.4從隊列的隊首逐一移出隊列中的元素。

圖2-6所展示的隊列可以使用如下代碼來實現：

我們在圖2-7的幫助下，理解圖2-6所展示的元素的入隊和出隊操作。

在圖2-7中，前一部分的代碼（[2]～[6]）先創建一個隊列，然后將四個元素分別加入隊列。

2.2.4　棧和隊列背后的基本思想

我們通過類比來討論棧和隊列背后的基本思想。假設有一個桌子，用來存放從郵政服務收到的郵件，例如來自加拿大的郵件。我們將郵件堆疊起來，直到空閑時逐一打開并查看郵件。有兩種可能的方法可以完成這個工作：

• 把信件疊成一堆，每當我們收到新的信，就把它放在郵件堆的最上面。當我們要讀信時，就從最上面的那封信開始讀，這里的信件堆就是我們所說的棧。需要注意的是，最新到達的信件總會在最上面，并且會優先被處理。從信件列表頂部取信稱為pop操作，每當新的信件到達時，將其放在列表頂部的操作稱為push操作。如果我們最終有一個相當大的信件堆，并且不斷有大量的信件到達，則可能永遠沒有機會處理在信件堆的底端的非常重要的信件。
• 把信件疊成一堆，但要先處理最早的信件：每次要閱讀信件時，都要先處理最早到達的那封信，這就是我們所說的隊列。將一封信件添加到信件堆中稱為入隊操作，從信件堆中移除信件稱為出隊操作。

2.2.5　樹

在算法的背景中，樹是非常有用的數據結構之一，因為它具有層次化的數據存儲能力。在設計算法時，我們使用樹來表示需要存儲或處理的數據元素之間的層次關系。

我們深入了解一下這個有趣且相當重要的數據結構。

每棵樹都有有限個節點，起始數據元素對應的節點稱為根節點（root），所有節點通過鏈接關系組織在一起，鏈接也稱為分支（branch）。

術語

我們來看看與樹這種數據結構相關的一些術語：

樹的類型

樹有不同的類型，下面分別進行解釋：

• 二叉樹：如果一棵樹的度是2，那么這棵樹稱為二叉樹。例如，圖2-8所展示的樹就是一棵二叉樹，因為它的度是2。

圖2-8所展示的是一棵有4層和8個節點的樹。

• 滿樹：滿樹是指所有非葉節點的度都相同的樹，這個值就是樹的度。圖2-9展示了前面討論的樹的類型。

請注意，最左邊的二叉樹不是滿樹，因為節點C的度是1，其他節點的度都是2。中間的樹和右邊的樹都是滿樹。

• 完美樹：完美樹是一種特殊類型的滿樹，其中所有的葉節點都位于同一層。例如，圖2-9中右側的二叉樹就是一棵完美的滿樹，因為所有的葉節點都在同一層，即第2層。
• 有序樹：如果一個節點的子節點按照特定的標準以某種順序排列，則稱為有序樹。例如，一棵樹可以從左到右按升序排列，其中同一層的節點在從左到右遍歷時，其值會遞增。

實例

樹這種抽象數據類型是開發決策樹的主要數據結構之一，這一點將在第7章中討論。由于樹的層次結構，它在網絡分析的相關算法中也很受歡迎，這一點將在第6章中詳細討論。樹也用于各種需要實現分治策略的查找和排序算法中。