利用C++ vector如何實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)

c++
小樊
82
2024-10-16 12:31:12

在 C++ 中，vector 是一種動(dòng)態(tài)數(shù)組，它可以很方便地實(shí)現(xiàn)常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，如隊(duì)列、棧和鏈表。以下是使用 vector 實(shí)現(xiàn)這些數(shù)據(jù)結(jié)構(gòu)的示例：

隊(duì)列（Queue）

使用 vector 實(shí)現(xiàn)隊(duì)列，可以使用 push_back() 在隊(duì)尾添加元素，使用 front() 和 pop_front() 獲取和移除隊(duì)首元素。為了模擬隊(duì)列的先進(jìn)先出（FIFO）特性，可以使用 insert() 和 erase() 函數(shù)在指定位置插入和刪除元素。

#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 實(shí)現(xiàn)棧，可以使用 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 實(shí)現(xiàn)鏈表，可以創(chuàng)建一個(gè)包含 pair<int, int> 的 vector，其中第一個(gè)元素表示節(jié)點(diǎn)值，第二個(gè)元素表示指向下一個(gè)節(jié)點(diǎn)的索引。這樣可以方便地實(shí)現(xiàn)鏈表的插入、刪除和查找操作。

#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 實(shí)現(xiàn)隊(duì)列、棧和鏈表。注意，這些實(shí)現(xiàn)僅用于演示目的，實(shí)際應(yīng)用中可能需要根據(jù)具體需求進(jìn)行優(yōu)化和調(diào)整。

0 踩