阅读量:0
在 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 实现队列、栈和链表。注意，这些实现仅用于演示目的，实际应用中可能需要根据具体需求进行优化和调整。
