C++ 数据结构实现

一、数据结构概述

数据结构是计算机科学的基本概念之一，是指数据的组织、管理和存储方式。在计算机科学中，数据结构是一种特殊的格式，用于组织和存储数据。数据结构可分为线性结构、树结构、图结构等不同类型。在 C++ 语言中，可以通过类和模板来实现各种不同类型的数据结构。

二、链表实现

链表是一种常见的数据结构，可以在任意节点处插入或删除数据，而无需移动其他数据。在 C++ 中，可以使用类实现链表。下面是一个简单的链表实现，包括节点和链表类：

// 链表节点类
class ListNode {
public:
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(NULL) {}
};

// 链表类
class LinkedList {
public:
    ListNode *head;

    LinkedList() {
        head = NULL;
    }

    // 在头部插入一个节点
    void insert(int x) {
        ListNode *node = new ListNode(x);
        node->next = head;
        head = node;
    }

    // 删除第一个节点
    void remove() {
        if (head == NULL) return;
        ListNode *node = head;
        head = head->next;
        delete node;
    }

    // 打印链表
    void print() {
        ListNode *node = head;
        while (node != NULL) {
            cout val next;
        }
        cout  1 -> NULL
list.remove();     // 删除 3
list.print();      // 输出 2 -> 1 -> NULL

三、栈实现

栈是一种后进先出（LIFO）的数据结构，可以在栈顶插入和删除数据，非栈顶数据不能访问。在 C++ 中，可以使用类和模板实现栈。下面是一个简单的栈实现：

template
class Stack {
private:
    vector data;
public:
    // 入栈
    void push(T x) {
        data.push_back(x);
    }
    
    // 取栈顶元素
    T top() {
        if (data.empty()) return -1;  // 栈为空
        return data.back();
    }
    
    // 出栈
    void pop() {
        if (data.empty()) return;     // 栈为空
        data.pop_back();
    }
    
    // 判断栈是否为空
    bool empty() {
        return data.empty();
    }
    
    // 返回栈中元素个数
    int size() {
        return data.size();
    }
};

使用该栈类可以很方便地进行栈操作：

Stack<int> s;
s.push(1);    // 入栈 1
s.push(2);    // 入栈 2
s.push(3);    // 入栈 3
cout