利用C++ vector如何实现数据结构

在 C++ 中，vector 是一种动态数组，它可以很方便地实现常见的数据结构，如队列、栈和链表。以下是使用 vector 实现这些数据结构的示例：

队列（Queue）

使用 vector 实现队列，可以使用 push_back() 在队尾添加元素，使用 front() 和 pop_front() 获取和移除队首元素。为了模拟队列的先进先出（FIFO）特性，可以使用 insert() 和 erase() 函数在指定位置插入和删除元素。

#include <iostream>
#include <vector>
#include <algorithm>

class Queue {
public:
    void enqueue(int value) {
        data.push_back(value);
    }

    int dequeue() {
        if (isEmpty()) {
            throw std::runtime_error("Queue is empty");
        }
        int frontValue = data.front();
        data.erase(data.begin());
        return frontValue;
    }

    bool isEmpty() const {
        return data.empty();
    }

private:
    std::vector<int> data;
};

栈（Stack）

使用 vector 实现栈，可以使用 push_back() 在栈顶添加元素，使用 back() 和 pop_back() 获取和移除栈顶元素。

#include <iostream>
#include <vector>
#include <algorithm>

class Stack {
public:
    void push(int value) {
        data.push_back(value);
    }

    int pop() {
        if (isEmpty()) {
            throw std::runtime_error("Stack is empty");
        }
        int topValue = data.back();
        data.pop_back();
        return topValue;
    }

    bool isEmpty() const {
        return data.empty();
    }

private:
    std::vector<int> data;
};

链表（Linked List）

使用 vector 实现链表，可以创建一个包含 pair<int, int> 的 vector，其中第一个元素表示节点值，第二个元素表示指向下一个节点的索引。这样可以方便地实现链表的插入、删除和查找操作。

#include <iostream>
#include <vector>
#include <algorithm>

class LinkedList {
public:
    void insert(int value, int index) {
        if (index < 0 || index > data.size()) {
            throw std::runtime_error("Invalid index");
        }
        data.insert(data.begin() + index, std::make_pair(value, -1));
    }

    void remove(int index) {
        if (index < 0 || index >= data.size()) {
            throw std::runtime_error("Invalid index");
        }
        data[index].second = -1; // Mark as removed
    }

    int find(int value) const {
        for (const auto& node : data) {
            if (node.first == value) {
                return node.second;
            }
        }
        return -1; // Not found
    }

private:
    std::vector<std::pair<int, int>> data;
};

这些示例展示了如何使用 vector 实现队列、栈和链表。注意，这些实现仅用于演示目的，实际应用中可能需要根据具体需求进行优化和调整。