C++抽象数据类型介绍

什么是抽象数据类型？

抽象数据类型（Abstract Data Type，ADT），是数据类型的一个数学模型。它实现了数据类型的抽象过程，将数据与操作分离，使得操作具有独立性，而数据只作为函数参数和返回值存在。

举个例子，ADT可以定义一个栈(Stack)，栈的实现需要以下操作：

• 初始化栈
• 压入数据
• 弹出数据
• 获取栈顶数据
• 检查栈是否为空

具体的实现方式可以是使用数组、链表等数据结构来存储数据，但是对于使用栈这种操作来说，实现细节并不关键，关键是栈操作的语义。

C++中如何实现ADT？

C++中可以使用类( Class) 和模板(Template) 实现ADT。下面分别介绍。

使用类实现ADT

类的私有成员变量表示数据，公有成员函数表示操作：

class Stack {
public:
    void push(int val);     // 压入数据
    int pop();              // 弹出数据
    int top() const;        // 获取栈顶数据
    bool empty() const;     // 判断是否为空
    int size() const;       // 获取栈的大小
private:
    std::vector<int> data;
};

以上例子实现了一个基于vector的栈。注意，Stack类的成员操作只是定义了栈操作的语义，而对具体的实现并没有要求。

使用模板实现ADT

模板是一种泛型编程方法，可以在不知道数据类型的情况下实现一个类或函数。使用模板可以实现更加通用的ADT。

template <typename T>
class Stack {
public:
    void push(T val);
    T pop();
    T top() const;
    bool empty() const;
    int size() const;
private:
    std::vector<T> data;
};

使用模板实现的栈可以使用不同的数据类型作为其元素，而不限定于整数(int)类型。

示例说明

示例1：使用类实现栈

下面是一个使用Stack类的示例，实现了一个栈并使用该栈进行计算器操作：

#include <iostream>
#include <stack>

class Calculator {
public:
    int compute(std::string expr) {
        Stack<int> s;
        for (auto c : expr) {
            if (std::isdigit(c)) {
                s.push(c - '0');
            } else if (c == '+') {
                int a = s.pop();
                int b = s.pop();
                s.push(a + b);
            } else if (c == '-') {
                int a = s.pop();
                int b = s.pop();
                s.push(b - a);
            } else if (c == '*') {
                int a = s.pop();
                int b = s.pop();
                s.push(a * b);
            } else if (c == '/') {
                int a = s.pop();
                int b = s.pop();
                s.push(b / a);
            }
        }
        return s.top();
    }
};

示例2：使用模板实现通用栈

下面是一个使用Stack模板的示例，实现了一个通用的栈并使用该栈存储字符串：

#include <iostream>
#include <string>
#include <stack>

int main() {
    Stack<std::string> s;
    s.push("Hello");
    s.push(",");
    s.push("world");
    while (!s.empty()) {
        std::cout << s.pop();
    }
    std::cout << std::endl;
}

总结

本文介绍了抽象数据类型(ADT)的概念以及在C++中如何使用类和模板实现ADT。通过示例说明，我们可以看到ADT的使用带来了代码的通用性和可维护性。对于需要高度抽象的数据类型，使用ADT是非常合适的。