在 C++ 中实现循环数组

Jinku Hu 2021年10月2日
在 C++ 中实现循环数组

本文将介绍如何用 C++ 实现一个循环数组数据结构。

C++ 中循环缓冲区实现的用户数组实现

循环数组是一种通常用于实现类似队列的数据集合的数据结构。它也有其他名称,例如循环队列或环形缓冲区,但我们将在本文中将其称为循环数组。

循环数组具有用于元素插入和删除操作的 FIFO(先进先出)机制。通常,缓冲区将具有固定长度。如果达到最大容量,缓冲区可能会拒绝新的插入操作或开始覆盖最旧的元素。后一个功能是一种设计选择,应该针对手头的各个问题考虑好处。

在下面的例子中,我们使用 C 风格的数组实现了一个循环数组,并构造了一个插入函数,这样,完整的缓冲区就不会开始覆盖旧数据。

CircularArray 类包括 5 个数据成员,其中三个具有 T* 类型,用于存储第一个的地址。最后一个元素(分别是 headtail)。arr 成员仅用于使用 delete 运算符使内存释放更容易。其余两个数据成员是整数类型,用于存储圆形数组的容量和当前大小。

构造函数自动将 size 成员初始化为 0,而 cap 值被接受为函数参数,因此用于分配所需的内存区域。此时,tailhead 指针都指向同一个位置,即数组中的第一个元素。但是请记住,这些指针可以在对象的生命周期内循环移动,因此我们需要在调用插入和删除操作时控制正确的修改。

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

template<typename T>
class CircularArray {
public:
    explicit CircularArray(const size_t elems) {
        cap = elems;
        arr = new T[elems];
        tail = head = arr ;
        size = 0;
    };

    int enqueue(const T &data);
    T *dequeue();
    size_t getSize();

    ~CircularArray();
private:
    T *arr = nullptr;
    T *head = nullptr;
    T *tail = nullptr;
    size_t cap;
    size_t size;
};

template<typename T>
CircularArray<T>::~CircularArray() {
    delete [] arr;
}

template<typename T>
int CircularArray<T>::enqueue(const T &data) {
    if (size < cap) {
        if (size == 0) {
            head = tail = arr;
            *tail = data;
            size++;
            return 0;
        }

        if (tail == &arr[cap]) {
            tail = arr;
            *tail = data;
            size++;
        } else {
            tail = tail + 1;
            *tail = data;
            size++;
        }
        return 0;
    } else {
        return -1;
    }
}

template<typename T>
T *CircularArray<T>::dequeue() {
    if (size != 0) {
        auto ret = head;

        if (head == &arr[cap]) {
            head = arr;
        } else {
            head = head + 1;
        }

        size--;
        return ret;
    } else {
        cout << "Array is empty !" << endl;
        return nullptr;
    }
}

template<typename T>
size_t CircularArray<T>::getSize() {
    return size;
}

struct MyClass {
    int num;
    double num2;
};

int main() {
    CircularArray<MyClass> m1(4);

    m1.enqueue({1, 1.1});
    m1.enqueue({1, 1.2});
    m1.enqueue({1, 1.3});
    m1.enqueue({1, 1.4});
    m1.enqueue({1, 1.5});
    m1.enqueue({1, 1.6});

    auto size = m1.getSize();
    for (size_t i = 0; i < size; ++i) {
        auto elem = m1.dequeue();
        cout << elem->num << "," << elem->num2 << endl;
    }

    return EXIT_SUCCESS;
}

输出:

1,1.1
1,1.2
1,1.3
1,1.4

为了将新元素添加到循环数组 enqueue 成员函数应该被调用。此函数获取对通用对象的引用并将其存储在缓冲区的尾部。

如果插入不成功,enqueue 函数返回一个非零值,程序员负责检查相应的返回值。

另一方面,dequeue 函数处理从缓冲区的 head 删除元素的操作。它旨在返回指向已删除元素的指针。在访问它之前必须检查返回指针(取消引用),因为它可能具有 nullptr 值。返回 nullptr 以指示缓冲区为空且无法删除任何元素。

同时,可以使用 getSize 函数安全地访问缓冲区中的当前元素数量,并使用返回值迭代结构。尽管迭代不太可能用于现实世界的场景,但 size 成员可能是实现其他成员功能的重要数据。

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

template<typename T>
class CircularArray {
public:
    explicit CircularArray(const size_t elems) {
        cap = elems;
        arr = new T[elems];
        tail = head = arr ;
        size = 0;
    };

    int enqueue(const T &data);
    T *dequeue();
    size_t getSize();

    ~CircularArray();
private:
    T *arr = nullptr;
    T *head = nullptr;
    T *tail = nullptr;
    size_t cap;
    size_t size;
};

template<typename T>
CircularArray<T>::~CircularArray() {
    delete [] arr;
}

template<typename T>
int CircularArray<T>::enqueue(const T &data) {
    if (size < cap) {
        if (size == 0) {
            head = tail = arr;
            *tail = data;
            size++;
            return 0;
        }

        if (tail == &arr[cap]) {
            tail = arr;
            *tail = data;
            size++;
        } else {
            tail = tail + 1;
            *tail = data;
            size++;
        }
        return 0;
    } else {
        return -1;
    }
}

template<typename T>
T *CircularArray<T>::dequeue() {
    if (size != 0) {
        auto ret = head;

        if (head == &arr[cap]) {
            head = arr;
        } else {
            head = head + 1;
        }

        size--;
        return ret;
    } else {
        cout << "Array is empty !" << endl;
        return nullptr;
    }
}

template<typename T>
size_t CircularArray<T>::getSize() {
    return size;
}

struct MyClass {
    int num;
    double num2;
};

int main() {
    CircularArray<MyClass> m1(4);

    m1.dequeue();
    m1.enqueue({1, 1.9});
    auto elem = m1.dequeue();
    if (elem)
        cout << elem->num << "," << elem->num2 << endl;

    return EXIT_SUCCESS;
}

输出:

Array is empty !
1,1.9
Author: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn

相关文章 - C++ Data Structure