数据结构—环形缓冲区

2024-01-03 14:53:53

写在前面,2023年11月开始进入岗位,工作岗位是嵌入式软件工程师。2024年是上班的第一年的,希望今年收获满满,增长见闻。

数据结构—环形缓冲区

为什么要使用环形数组,环形数组比起原来的常规数组的优势是什么?

环形数组(Circular Array)是一种特殊类型的数组,其元素在内存中首尾相接,形成一个环形。环形数组具有一些独特的优势和用途,使其在某些应用场景中比常规数组更为适用。以下是一些使用环形数组的原因和优势:

空间利用率高:由于环形数组的元素在内存中是首尾相接的,因此不需要为数组的头部和尾部留出额外的空间。这使得环形数组的空间利用率比常规数组更高。

高效的数据访问:在环形数组中,可以通过简单的模运算来确定一个元素在数组中的位置。这使得数据访问操作更加高效。

连续的数据结构:环形数组保持了数据的连续性,这有助于提高数据访问的局部性,从而优化CPU缓存的性能。

避免数组越界问题:由于环形数组的特性,当索引超出数组的界限时,会自动回到数组的开头或结尾,避免了常规数组越界访问导致的错误。

循环队列和缓冲区实现:环形数组可以方便地实现循环队列或缓冲区,无需移动大量数据即可进行队首和队尾的添加与删除操作。

减少内存碎片:由于环形数组的连续存储特性,它可以更有效地利用内存空间,减少内存碎片的产生。
易于实现动态扩展:当需要增加更多元素时,环形数组可以通过简单地扩展现有数组的大小来实现动态扩展,而无需重新分配和复制原有数据。

c代码实现

#include <stdio.h>  
#include <stdlib.h>  
#include <stdbool.h>  
  
#define BUFFER_SIZE 5 // 定义环形缓冲区的大小  
  
typedef struct {  
    int buffer[BUFFER_SIZE]; // 缓冲区数组  
    int head; // 指向缓冲区中第一个元素的位置  
    int tail; // 指向缓冲区中下一个要写入元素的位置  
} CircularBuffer;  
  
// 初始化环形缓冲区  
void init_circular_buffer(CircularBuffer *cb) {  
    cb->head = 0;  
    cb->tail = 0;  
    for (int i = 0; i < BUFFER_SIZE; i++) {  
        cb->buffer[i] = 0; // 可以选择性地初始化缓冲区的内容  
    }  
}  
  
// 检查环形缓冲区是否为空  
bool is_circular_buffer_empty(CircularBuffer *cb) {  
    return cb->head == cb->tail && cb->buffer[cb->head] == 0; // 如果头和尾相等且头部元素为空,则认为缓冲区为空  
}  
  
// 检查环形缓冲区是否已满  
bool is_circular_buffer_full(CircularBuffer *cb) {  
    return (cb->tail + 1) % BUFFER_SIZE == cb->head; // 如果下一个要写入的位置是头部,则认为缓冲区已满  
}  
  
// 向环形缓冲区中插入一个元素  
bool insert_into_circular_buffer(CircularBuffer *cb, int value) {  
    if (is_circular_buffer_full(cb)) {  
        return false; // 缓冲区已满,无法插入新元素  
    }  
    cb->buffer[cb->tail] = value; // 在尾部插入新元素  
    cb->tail = (cb->tail + 1) % BUFFER_SIZE; // 更新尾部指针到下一个位置  
    return true; // 插入成功  
}  
  
// 从环形缓冲区中移除一个元素并返回它  
int remove_from_circular_buffer(CircularBuffer *cb) {  
    if (is_circular_buffer_empty(cb)) {  
        return -1; // 缓冲区为空,无法移除元素,返回错误代码或特殊值  
    }  
    int value = cb->buffer[cb->head]; // 获取头部元素的值  
    cb->buffer[cb->head] = 0; // 可选:将移除的元素置零(根据具体需求决定是否需要这一步)  
    cb->head = (cb->head + 1) % BUFFER_SIZE; // 更新头部指针到下一个位置  
    return value; // 返回被移除的元素值  
}  
  
int main() {  
    CircularBuffer cb; // 声明一个环形缓冲区变量  
    init_circular_buffer(&cb); // 初始化环形缓冲区  
      
    // 向缓冲区中插入一些元素并检查其状态  
    for (int i = 1; i <= 6; i++) { // 尝试插入6个元素,但缓冲区大小只有5,所以会有一个插入失败  
        if (!insert_into_circular_buffer(&cb, i)) {  
            printf("Failed to insert element %d because the buffer is full.\n", i);  
        }  
    }  
      
    // 从缓冲区中移除一些元素并打印它们的值  
    for (int i = 0; i < 6; i++) { // 尝试移除6个元素,但只插入了5个,所以会有一个移除返回特殊值(这里是-1)  
        int value = remove_from_circular_buffer(&cb);  
        if (value == -1) {  
            printf("Failed to remove element because the buffer is empty.\n");  
        } else {  
            printf("Removed element: %d\n", value);  
        }  
    }  
      
    return 0;  
}

运行结果

在这里插入图片描述

文章来源:https://blog.csdn.net/m0_46152793/article/details/135361731
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。