C++-----线性结构

C++线性结构模板

概念：线性结构是一种数据元素之间存在一对一线性关系的数据结构，如数组、链表、栈、队列等。C++中的模板可以让我们编写通用的代码，适用于不同的数据类型，而不必为每种数据类型都重复编写相同的代码结构。
作用：通过使用模板，我们可以创建出可重用、灵活的线性结构代码，提高代码的可维护性和效率。例如，我们可以编写一个通用的线性表模板类，然后根据需要实例化为存储不同类型数据的线性表，如整数线性表、字符串线性表等。

栈的实现

概念：栈是一种特殊的线性表，它只允许在表的一端进行插入和删除操作，这一端被称为栈顶，另一端则被称为栈底。栈遵循后进先出（LIFO）的原则，即最后插入的元素最先被删除。
实现方法：
- 顺序存储实现：可以使用数组来实现栈。定义一个数组来存储栈元素，以及一个变量来记录栈顶元素的位置。入栈操作就是将元素放入数组中栈顶位置的下一个位置，并更新栈顶位置；出栈操作则是取出栈顶元素，并将栈顶位置减1。
- 链式存储实现：通过链表来实现栈。定义一个链表节点结构体，包含数据域和指向下一个节点的指针域。入栈操作就是在链表头部插入新节点，出栈操作则是删除链表头部节点。

队列的实现

概念：队列也是一种线性表，它允许在表的一端进行插入操作，在另一端进行删除操作。插入元素的一端称为队尾，删除元素的一端称为队头。队列遵循先进先出（FIFO）的原则，即最先插入的元素最先被删除。
实现方法：
- 顺序存储实现：使用数组来实现队列时，需要定义两个指针，一个指向队头，一个指向队尾。入队操作就是将元素放入队尾指针所指的位置，并更新队尾指针；出队操作则是取出队头指针所指的元素，并更新队头指针。为了避免队列空间的浪费和实现循环队列，通常需要对数组进行一些特殊的处理。
- 链式存储实现：通过链表来实现队列，定义一个链表节点结构体，包含数据域和指向下一个节点的指针域。入队操作就是在链表尾部插入新节点，出队操作则是删除链表头部节点。

矢量类的实现

概念：矢量类通常指的是类似于C++标准库中的std::vector的类，它是一个动态大小的数组，可以方便地进行元素的插入、删除和访问等操作。
实现方法：
- 成员变量：通常需要定义一个指针来指向存储元素的数组，以及一个变量来记录当前数组的大小和容量。
- 构造函数和析构函数：构造函数用于初始化矢量类的对象，可能包括分配内存、设置初始大小等操作。析构函数则用于释放动态分配的内存。
- 元素访问：可以通过重载下标运算符[]来实现对矢量中元素的访问，还可以提供at()函数进行边界检查的访问。
- 插入和删除操作：提供push_back()函数在矢量末尾插入元素，insert()函数在指定位置插入元素，erase()函数删除指定位置的元素等。
- 其他操作：还可以实现获取矢量大小、容量、判断是否为空等操作，以及对矢量进行排序、查找等算法的封装。

下面是一个简单的栈的顺序存储实现示例代码：

template<typename T, int MAX_SIZE>
class Stack {
private:
    T data[MAX_SIZE];
    int top;

public:
    Stack() : top(-1) {}

    bool isEmpty() const {
        return top == -1;
    }

    bool isFull() const {
        return top == MAX_SIZE - 1;
    }

    void push(const T& value) {
        if (isFull()) {
            throw std::runtime_error("Stack is full");
        }
        data[++top] = value;
    }

    T pop() {
        if (isEmpty()) {
            throw std::runtime_error("Stack is empty");
        }
        return data[top--];
    }

    T peek() const {
        if (isEmpty()) {
            throw std::runtime_error("Stack is empty");
        }
        return data[top];
    }
};