[[440257]]

大家好，我是梁唐。

抽象數據類型

我們在學數據結構的時候，經常遇到的一個概念就是抽象數據類型(Abstract Data Type)，簡稱ADT。

維基百科中的定義是：抽象數據類型是計算機科學中具有類似行為的特定類別的數據結構的數學模型，或者具有類似語義的一種或多種程序設計語言的數據類型。

從這段定義來看，非常地費解，其實我們只需要抓住核心。核心就是接口和實現的分離。我們在使用一個ADT的時候，只需要和接口進行交互，而不必關心接口中的實現細節。同樣，數據也是隱藏不可見的，也需要通過接口進行交互。

也就是說接口是數據類型唯一的交互方式，除此之外，用戶無法接觸到ADT的數據以及實現細節。

舉個例子，以棧舉例，如果我們不將棧設計成ADT，那么用戶在使用棧的時候，可能就需要自己創建一個數組來存儲棧中的數據，通過調用一些方法來實現棧的功能。但這勢必需要用戶了解棧的原理，以及數據存儲的細節。ADT會做一個良好的封裝，用戶只需要了解每個接口的功能，調用對應的接口實現自己想要的邏輯即可。

我們來看一下C++ Primer當中實現的棧的例子。

首先，我們需要知道棧一共有哪些接口，大概有如下這么幾個：

• 創建空棧
• 可添加數據到棧頂
• 可從棧頂彈出數據
• 可查看棧是否為空
• 可查看棧是否已滿

然后，我們遵守C++中面向對象的設計思路，將它封裝在一個類當中。首先我們來定義這個類：

#ifndef STACK__H_ 
#define STACK__H_ 
 
typedef unsigned long Item; 
 
class Stack { 
 private: 
        enum {MAX=10}; 
        Item items[MAX]; 
        int top; 
    public: 
     Stack(); 
     bool isempty() const; 
     bool isfull() const; 
     bool push(const Item &item); 
     bool pop(Item &item); 
}; 
#endif 

我們來看下這個定義，會發現，其中的數據都被設定成了private，也就是用戶無法直接訪問到數據。只能通過public的接口進行交互，也無須關心其中的實現細節，可以當做黑盒使用。

最后， 我們再來看下C++ Primer當中給出的實現：

#include "stack.h" 
 
Stack::Stack() { 
    top = 0; 
} 
 
bool Stack::isempty() const { 
    return top == 0; 
} 
 
bool Stack::isfull() const { 
    return top == MAX; 
} 
 
bool Stack::push(const Item &item) { 
    if (top < MAX) { 
        items[top++] = item; 
        return true; 
    } 
    return false; 
} 
 
bool Stack::pop(Item &item) { 
    if (top > 0) { 
        item = items[--top]; 
        return true; 
    } 
    return false; 
} 

本文轉載自微信公眾號「Coder梁」，可以通過以下二維碼關注。轉載本文請聯系Coder梁公眾號。