数据结构：循环数组详解

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}")

// 创建容量为 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]