数据结构：循环数组详解

什么是循环数组

循环数组（Circular Array），也称为环形数组或环形缓冲区（Ring Buffer），是一种特殊的数组结构。它在逻辑上将数组的首尾相连，形成一个环形结构。当数组索引到达末尾时，会自动回到数组的开头，实现循环访问。

循环数组的核心思想是：通过取模运算，让索引在固定范围内循环。

为什么需要循环数组？

在传统的线性数组中，当我们需要在数组头部插入或删除元素时，需要移动大量元素，时间复杂度为 O(n)。而循环数组通过维护头尾指针，可以高效地在两端进行操作，实现 O(1) 的时间复杂度。

循环数组的核心概念

1. 基本结构

循环数组通常需要维护以下几个关键元素：

• data[]: 底层数组，用于存储实际数据
• front: 头指针，指向队列的第一个元素
• rear: 尾指针，指向队列最后一个元素的下一个位置
• capacity: 数组容量
• size: 当前元素个数

2. 索引计算

循环数组最关键的操作是索引的循环计算：

实际索引 = (逻辑索引) % 数组长度

例如，在长度为 5 的数组中：

• 索引 0 的下一个位置是 (0 + 1) % 5 = 1
• 索引 4 的下一个位置是 (4 + 1) % 5 = 0（回到开头）

3. 判空与判满

判空条件：

isEmpty = (size == 0) 或 (front == rear)

判满条件：

isFull = (size == capacity) 或 ((rear + 1) % capacity == front)

注意：有些实现会预留一个空位来区分满和空的状态。

循环数组的实现

下面我们分别用 Swift、Objective-C 和 Python 实现一个完整的循环数组（以循环队列为例）：

• Swift
• Objective-C
• Python

class CircularArray<T> {
    private var data: [T?]
    private var front: Int
    private var rear: Int
    private let capacity: Int
    private var size: Int
    
    init(capacity: Int) {
        self.capacity = capacity
        self.data = Array(repeating: nil, count: capacity)
        self.front = 0
        self.rear = 0
        self.size = 0
    }
    
    // 判断是否为空
    func isEmpty() -> Bool {
        return size == 0
    }
    
    // 判断是否已满
    func isFull() -> Bool {
        return size == capacity
    }
    
    // 获取当前元素个数
    func count() -> Int {
        return size
    }
    
    // 在尾部添加元素
    func enqueue(_ element: T) -> Bool {
        if isFull() {
            print("队列已满，无法添加元素")
            return false
        }
        
        data[rear] = element
        rear = (rear + 1) % capacity
        size += 1
        return true
    }
    
    // 从头部移除元素
    func dequeue() -> T? {
        if isEmpty() {
            print("队列为空，无法移除元素")
            return nil
        }
        
        let element = data[front]
        data[front] = nil
        front = (front + 1) % capacity
        size -= 1
        return element
    }
    
    // 查看队首元素（不移除）
    func peek() -> T? {
        if isEmpty() {
            return nil
        }
        return data[front]
    }
    
    // 获取指定索引的元素
    func get(_ index: Int) -> T? {
        if index < 0 || index >= size {
            return nil
        }
        let actualIndex = (front + index) % capacity
        return data[actualIndex]
    }
    
    // 打印所有元素
    func printElements() {
        if isEmpty() {
            print("队列为空")
            return
        }
        
        var elements: [T] = []
        for i in 0..<size {
            if let element = get(i) {
                elements.append(element)
            }
        }
        print("队列元素: \(elements)")
    }
}

// CircularArray.h
@interface CircularArray<ObjectType> : NSObject

- (instancetype)initWithCapacity:(NSUInteger)capacity;
- (BOOL)isEmpty;
- (BOOL)isFull;
- (NSUInteger)count;
- (BOOL)enqueue:(ObjectType)element;
- (ObjectType)dequeue;
- (ObjectType)peek;
- (ObjectType)getElementAtIndex:(NSUInteger)index;
- (void)printElements;

@end

// CircularArray.m
@implementation CircularArray {
    NSMutableArray *_data;
    NSUInteger _front;
    NSUInteger _rear;
    NSUInteger _capacity;
    NSUInteger _size;
}

- (instancetype)initWithCapacity:(NSUInteger)capacity {
    self = [super init];
    if (self) {
        _capacity = capacity;
        _data = [NSMutableArray arrayWithCapacity:capacity];
        for (NSUInteger i = 0; i < capacity; i++) {
            [_data addObject:[NSNull null]];
        }
        _front = 0;
        _rear = 0;
        _size = 0;
    }
    return self;
}

- (BOOL)isEmpty {
    return _size == 0;
}

- (BOOL)isFull {
    return _size == _capacity;
}

- (NSUInteger)count {
    return _size;
}

- (BOOL)enqueue:(id)element {
    if ([self isFull]) {
        NSLog(@"队列已满，无法添加元素");
        return NO;
    }
    
    _data[_rear] = element;
    _rear = (_rear + 1) % _capacity;
    _size++;
    return YES;
}

- (id)dequeue {
    if ([self isEmpty]) {
        NSLog(@"队列为空，无法移除元素");
        return nil;
    }
    
    id element = _data[_front];
    _data[_front] = [NSNull null];
    _front = (_front + 1) % _capacity;
    _size--;
    return element;
}

- (id)peek {
    if ([self isEmpty]) {
        return nil;
    }
    return _data[_front];
}

- (id)getElementAtIndex:(NSUInteger)index {
    if (index >= _size) {
        return nil;
    }
    NSUInteger actualIndex = (_front + index) % _capacity;
    return _data[actualIndex];
}

- (void)printElements {
    if ([self isEmpty]) {
        NSLog(@"队列为空");
        return;
    }
    
    NSMutableArray *elements = [NSMutableArray array];
    for (NSUInteger i = 0; i < _size; i++) {
        id element = [self getElementAtIndex:i];
        if (element && element != [NSNull null]) {
            [elements addObject:element];
        }
    }
    NSLog(@"队列元素: %@", elements);
}

@end

class CircularArray:
    def __init__(self, capacity):
        """初始化循环数组"""
        self.capacity = capacity
        self.data = [None] * capacity
        self.front = 0
        self.rear = 0
        self.size = 0
    
    def is_empty(self):
        """判断是否为空"""
        return self.size == 0
    
    def is_full(self):
        """判断是否已满"""
        return self.size == self.capacity
    
    def count(self):
        """获取当前元素个数"""
        return self.size
    
    def enqueue(self, element):
        """在尾部添加元素"""
        if self.is_full():
            print("队列已满，无法添加元素")
            return False
        
        self.data[self.rear] = element
        self.rear = (self.rear + 1) % self.capacity
        self.size += 1
        return True
    
    def dequeue(self):
        """从头部移除元素"""
        if self.is_empty():
            print("队列为空，无法移除元素")
            return None
        
        element = self.data[self.front]
        self.data[self.front] = None
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return element
    
    def peek(self):
        """查看队首元素（不移除）"""
        if self.is_empty():
            return None
        return self.data[self.front]
    
    def get(self, index):
        """获取指定索引的元素"""
        if index < 0 or index >= self.size:
            return None
        actual_index = (self.front + index) % self.capacity
        return self.data[actual_index]
    
    def print_elements(self):
        """打印所有元素"""
        if self.is_empty():
            print("队列为空")
            return
        
        elements = []
        for i in range(self.size):
            element = self.get(i)
            if element is not None:
                elements.append(element)
        print(f"队列元素: {elements}")

使用示例

• Swift
• Python

// 创建容量为 5 的循环数组
let circularArray = CircularArray<Int>(capacity: 5)

// 添加元素
circularArray.enqueue(1)  // [1]
circularArray.enqueue(2)  // [1, 2]
circularArray.enqueue(3)  // [1, 2, 3]
circularArray.enqueue(4)  // [1, 2, 3, 4]
circularArray.enqueue(5)  // [1, 2, 3, 4, 5]

circularArray.printElements()
// 输出: 队列元素: [1, 2, 3, 4, 5]

// 尝试添加第6个元素（会失败）
circularArray.enqueue(6)
// 输出: 队列已满，无法添加元素

// 移除两个元素
print(circularArray.dequeue()!)  // 输出: 1
print(circularArray.dequeue()!)  // 输出: 2

// 此时可以继续添加元素
circularArray.enqueue(6)  // [3, 4, 5, 6]
circularArray.enqueue(7)  // [3, 4, 5, 6, 7]

circularArray.printElements()
// 输出: 队列元素: [3, 4, 5, 6, 7]

# 创建容量为 5 的循环数组
circular_array = CircularArray(5)

# 添加元素
circular_array.enqueue(1)  # [1]
circular_array.enqueue(2)  # [1, 2]
circular_array.enqueue(3)  # [1, 2, 3]
circular_array.enqueue(4)  # [1, 2, 3, 4]
circular_array.enqueue(5)  # [1, 2, 3, 4, 5]

circular_array.print_elements()
# 输出: 队列元素: [1, 2, 3, 4, 5]

# 尝试添加第6个元素（会失败）
circular_array.enqueue(6)
# 输出: 队列已满，无法添加元素

# 移除两个元素
print(circular_array.dequeue())  # 输出: 1
print(circular_array.dequeue())  # 输出: 2

# 此时可以继续添加元素
circular_array.enqueue(6)  # [3, 4, 5, 6]
circular_array.enqueue(7)  # [3, 4, 5, 6, 7]

circular_array.print_elements()
# 输出: 队列元素: [3, 4, 5, 6, 7]

循环数组的应用场景

1. 循环队列（Circular Queue）

这是循环数组最典型的应用。循环队列常用于：

• 操作系统的进程调度
• 网络数据包的缓冲
• 生产者-消费者模型
• 键盘输入缓冲区

2. 循环缓冲区（Ring Buffer）

在音视频处理、网络通信等场景中广泛使用：

• 音频播放器的缓冲区
• 视频解码器的帧缓冲
• 网络数据的接收缓冲

3. LRU 缓存

结合循环数组和哈希表可以实现高效的 LRU（Least Recently Used）缓存。

4. 滑动窗口问题

在算法题中，很多滑动窗口问题可以用循环数组来优化。

性能分析

时间复杂度

操作	时间复杂度
入队（enqueue）	O(1)
出队（dequeue）	O(1)
查看队首（peek）	O(1)
判空/判满	O(1)
随机访问	O(1)

空间复杂度

空间复杂度为 O(n)，其中 n 是数组的容量。

优势

1. 高效的两端操作：在头尾插入删除都是 O(1)
2. 固定内存占用：预分配固定大小的内存，避免动态扩容
3. 缓存友好：连续的内存空间，对 CPU 缓存友好

劣势

1. 固定容量：容量固定，无法动态扩展（除非重新分配）
2. 空间浪费：某些实现需要预留一个空位来区分满和空

循环数组 vs 普通数组

特性	循环数组	普通数组
头部插入	O(1)	O(n)
头部删除	O(1)	O(n)
尾部插入	O(1)	O(1)
尾部删除	O(1)	O(1)
随机访问	O(1)	O(1)
空间利用	固定容量，可能浪费	可动态扩容

常见陷阱与注意事项

1. 索引计算错误

在进行索引计算时，特别是向前移动时，需要注意负数的处理：

// ❌ 错误：可能产生负数
front = (front - 1) % capacity

// ✅ 正确：确保结果为正
front = (front - 1 + capacity) % capacity

2. 满和空的判断

有两种常见的判断方法：

方法1：使用 size 变量

isEmpty = (size == 0)
isFull = (size == capacity)

方法2：预留一个空位

isEmpty = (front == rear)
isFull = ((rear + 1) % capacity == front)

3. 线程安全问题

在多线程环境下使用循环数组需要加锁：

class ThreadSafeCircularArray<T> {
    private var circularArray: CircularArray<T>
    private let lock = NSLock()
    
    init(capacity: Int) {
        self.circularArray = CircularArray<T>(capacity: capacity)
    }
    
    func enqueue(_ element: T) -> Bool {
        lock.lock()
        defer { lock.unlock() }
        return circularArray.enqueue(element)
    }
    
    func dequeue() -> T? {
        lock.lock()
        defer { lock.unlock() }
        return circularArray.dequeue()
    }
}

扩展：动态扩容的循环数组

虽然循环数组通常是固定容量的，但我们也可以实现动态扩容：

class DynamicCircularArray<T> {
    private var data: [T?]
    private var front: Int
    private var rear: Int
    private var capacity: Int
    private var size: Int
    
    init(capacity: Int = 10) {
        self.capacity = capacity
        self.data = Array(repeating: nil, count: capacity)
        self.front = 0
        self.rear = 0
        self.size = 0
    }
    
    func enqueue(_ element: T) {
        if isFull() {
            resize(newCapacity: capacity * 2)
        }
        
        data[rear] = element
        rear = (rear + 1) % capacity
        size += 1
    }
    
    private func resize(newCapacity: Int) {
        var newData: [T?] = Array(repeating: nil, count: newCapacity)
        
        // 将旧数据按顺序复制到新数组
        for i in 0..<size {
            let index = (front + i) % capacity
            newData[i] = data[index]
        }
        
        data = newData
        front = 0
        rear = size
        capacity = newCapacity
    }
    
    func isFull() -> Bool {
        return size == capacity
    }
    
    // 其他方法...
}

总结

循环数组是一种巧妙的数据结构，通过取模运算实现了数组的逻辑环形连接。它在以下场景中特别有用：

1. 需要高效的两端操作：O(1) 时间复杂度的头尾插入删除
2. 固定大小的缓冲区：音视频处理、网络通信等
3. 队列的实现：循环队列比用链表实现的队列更节省空间
4. 资源受限的环境：嵌入式系统、实时系统等

掌握循环数组的原理和实现，对于理解操作系统、网络编程、以及解决算法问题都有很大帮助。

延伸阅读

• Circular buffer - Wikipedia
• Circular Queue | Set 1 (Introduction and Array Implementation) - GeeksforGeeks
• Design Circular Queue - LeetCode
• Design Circular Deque - LeetCode

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. 《算法导论》（第3版）. 机械工业出版社, 2012
• Mark Allen Weiss. 《数据结构与算法分析：C++描述》（第4版）. 电子工业出版社, 2014
• 严蔚敏, 吴伟民. 《数据结构》（C语言版）. 清华大学出版社, 2011
• Robert Sedgewick, Kevin Wayne. 《算法》（第4版）. 人民邮电出版社, 2012