iOS 队列的两种实现：循环数组 vs 链表

Table of contents

前言

队列（Queue）是一种遵循先进先出（FIFO，First In First Out）原则的线性数据结构。在 iOS 开发中，我们经常需要使用队列来处理各种场景，比如：任务调度、消息队列、事件处理等。

在上一篇文章《数据结构：循环数组详解》中，我们详细介绍了循环数组的原理。本文将基于实际项目中的代码，深入对比循环数组实现的队列和链表实现的队列这两种方案，帮助你在实际开发中做出正确的选择。

队列的基本概念

什么是队列？

队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，在表的后端（rear）进行插入操作。

入队 (enqueue)          出队 (dequeue)
      ↓                      ↑
    +---+---+---+---+---+
    | 5 | 4 | 3 | 2 | 1 |  ← 队列
    +---+---+---+---+---+
    队尾 (tail)      队头 (front)

队列的基本操作

• enqueue（入队）：在队尾添加一个元素
• dequeue（出队）：移除并返回队头元素
• peek（查看队头）：查看队头元素但不移除
• isEmpty（判空）：判断队列是否为空
• count（计数）：获取队列中元素的个数

方案一：基于循环数组的队列实现

设计思路

循环数组实现的队列（LitQueue）使用固定大小的数组作为底层存储，通过维护 front 指针和 count 计数器来管理队列状态。

核心数据结构

@interface LitQueue ()

/// 循环数组，存储队列元素
@property (nonatomic, strong) NSMutableArray *items;

/// 队头索引
@property (nonatomic, assign) NSInteger front;

/// 队列元素数量
@property (nonatomic, assign) NSInteger count;

/// 当前容量
@property (nonatomic, assign) NSInteger capacity;

@end

关键设计要点

1. 预分配空间：创建队列时预先分配固定容量，用 NSNull 填充占位
2. 循环索引计算：通过取模运算实现循环访问
3. 动态扩容/缩容：满时扩容为 2 倍，使用率低于 25% 时缩容为一半

核心实现代码

1. 初始化

- (instancetype)initWithCapacity:(NSInteger)capacity {
    if (self = [super init]) {
        _capacity = capacity;
        _items = [NSMutableArray arrayWithCapacity:capacity];
        
        // 预填充 NSNull 占位，避免后续插入时数组自动扩容
        // 这样可以直接用下标访问，避免 Crash
        for (NSInteger i = 0; i < capacity; i++) {
            [_items addObject:[NSNull null]];
        }
        
        _front = 0;
        _count = 0;
    }
    return self;
}

设计细节：

• 预填充 NSNull 是为了让数组达到指定容量，后续可以直接用下标访问
• 如果不预填充，使用 items[index] = obj 会 Crash
• 不预填充的话只能用 addObject，会导致数组频繁扩容

2. 入队操作

- (void)enqueue:(id)object {
    if (!object) {
        @throw [NSException exceptionWithName:NSInvalidArgumentException
                                       reason:@"Cannot enqueue nil object"
                                     userInfo:nil];
        return;
    }
    
    // 检查是否需要扩容
    if (self.count == self.capacity) {
        [self resize:self.capacity * 2];
    }
    
    // 计算队尾位置（循环数组的核心）
    NSInteger tail = (self.front + self.count) % self.capacity;
    self.items[tail] = object;
    self.count++;
}

关键点：

• 队尾位置计算公式：tail = (front + count) % capacity
• 满时触发扩容，扩容为原容量的 2 倍
• 时间复杂度：O(1) 摊销（扩容时为 O(n)）

3. 出队操作

- (id)dequeue {
    if (self.isEmpty) {
        @throw [NSException exceptionWithName:NSInternalInconsistencyException
                                       reason:@"Cannot dequeue from an empty queue"
                                     userInfo:nil];
        return nil;
    }
    
    // 取出队头元素
    id object = self.items[self.front];
    
    // 清空位置（避免内存泄漏）
    self.items[self.front] = [NSNull null];
    
    // 移动队头指针（循环）
    self.front = (self.front + 1) % self.capacity;
    self.count--;
    
    // 缩容策略（当使用率低于 25% 且容量大于默认值时）
    if (self.count > 0 && self.count == self.capacity / 4 && self.capacity > kDefaultCapacity) {
        [self resize:self.capacity / 2];
    }
    
    return object;
}

关键点：

• 队头指针循环移动：front = (front + 1) % capacity
• 清空旧位置防止对象被强引用导致内存泄漏
• 智能缩容：使用率低于 25% 时缩容，避免频繁缩容导致的性能抖动
• 时间复杂度：O(1)（大部分情况），缩容时为 O(n)

4. 扩容/缩容实现

- (void)resize:(NSInteger)newCapacity {
    // 创建新数组
    NSMutableArray *newItems = [NSMutableArray arrayWithCapacity:newCapacity];
    
    // 预填充 NSNull
    for (NSInteger i = 0; i < newCapacity; i++) {
        [newItems addObject:[NSNull null]];
    }
    
    // 按顺序复制元素到新数组
    for (NSInteger i = 0; i < self.count; i++) {
        NSInteger oldIndex = (self.front + i) % self.capacity;
        newItems[i] = self.items[oldIndex];
    }
    
    // 更新状态
    self.items = newItems;
    self.capacity = newCapacity;
    self.front = 0;  // 重置队头到 0
}

设计亮点：

• 扩容时将所有元素按顺序重新排列到新数组
• 重置 front 为 0，简化后续操作
• 时间复杂度：O(n)

内存布局示意

初始状态（capacity = 5, count = 0, front = 0）:
   0    1    2    3    4
[null][null][null][null][null]
  ↑
 front

入队 A, B, C 后（count = 3, front = 0）:
   0    1    2    3    4
 [ A ][ B ][ C ][null][null]
   ↑              ↑
 front          tail

出队 A, B 后，入队 D, E, F（count = 4, front = 2）:
   0    1    2    3    4
 [ E ][ F ][ C ][ D ][null]
             ↑         ↑
           front     tail (循环到 1)

此时队列逻辑顺序是：C -> D -> E -> F

方案二：基于链表的队列实现

设计思路

链表实现的队列（LitLinkedQueue）使用单向链表作为底层存储，通过维护 head 和 tail 两个指针来管理队列。

核心数据结构

// 链表节点
@interface LitLinkedQueueNode : NSObject
@property (nonatomic, strong) id value;
@property (nonatomic, strong, nullable) LitLinkedQueueNode *next;
@end

// 队列
@interface LitLinkedQueue ()
@property (nonatomic, strong, nullable) LitLinkedQueueNode *head;  // 队头（出队）
@property (nonatomic, strong, nullable) LitLinkedQueueNode *tail;  // 队尾（入队）
@property (nonatomic, assign) NSInteger count;
@end

关键设计要点

1. 双指针管理：维护队头和队尾指针，实现 O(1) 的入队和出队
2. 按需分配：不需要预分配空间，动态增长
3. 简单高效：无需扩容操作，所有操作都是 O(1)

核心实现代码

1. 入队操作

- (void)enqueue:(id)object {
    if (!object) {
        @throw [NSException exceptionWithName:NSInvalidArgumentException
                                       reason:@"Cannot enqueue nil object"
                                     userInfo:nil];
        return;
    }
    
    LitLinkedQueueNode *newNode = [LitLinkedQueueNode nodeWithValue:object];
    
    if (self.tail) {
        // 队列不为空，添加到队尾
        self.tail.next = newNode;
        self.tail = newNode;
    } else {
        // 队列为空，新节点既是队头也是队尾
        self.head = newNode;
        self.tail = newNode;
    }
    
    _count++;
}

关键点：

• 始终在队尾添加新节点
• 特殊处理空队列的情况
• 时间复杂度：O(1)，无扩容开销

2. 出队操作

- (id)dequeue {
    if (self.isEmpty) {
        @throw [NSException exceptionWithName:NSInternalInconsistencyException
                                       reason:@"Cannot dequeue from an empty queue"
                                     userInfo:nil];
        return nil;
    }
    
    // 取出队头元素
    id value = self.head.value;
    
    // 移动队头指针
    self.head = self.head.next;
    
    // 如果队列变空，清空队尾指针
    if (!self.head) {
        self.tail = nil;
    }
    
    _count--;
    
    return value;
}

关键点：

• 直接移动 head 指针，旧节点会被 ARC 自动回收
• 队列变空时需要同步清空 tail 指针
• 时间复杂度：O(1)，真正的常数时间

3. 清空队列

- (void)removeAllObjects {
    // 断开所有节点连接，帮助 ARC 回收
    LitLinkedQueueNode *current = self.head;
    while (current) {
        LitLinkedQueueNode *next = current.next;
        current.next = nil;
        current.value = nil;
        current = next;
    }
    
    self.head = nil;
    self.tail = nil;
    _count = 0;
}

设计细节：

• 显式断开所有节点的 next 和 value 引用
• 帮助 ARC 更快地回收内存，避免循环引用
• 虽然只设置 head = nil 也能让 ARC 最终回收，但显式断开更高效

内存布局示意

空队列:
head → nil
tail → nil

入队 A 后:
head → [A | next:nil] ← tail
       
入队 B, C 后:
head → [A | next] → [B | next] → [C | next:nil] ← tail

出队 A 后:
       head → [B | next] → [C | next:nil] ← tail
       
注意：旧的节点 A 会被 ARC 自动回收

两种实现方式的深度对比

性能对比

内存特性对比

1. 内存占用

循环数组（LitQueue）：

基础开销：
- NSMutableArray 对象：约 32 字节
- 数组内存：capacity × 8 字节（每个指针）

实际占用示例（capacity = 100, count = 50）：
32 + 100 × 8 = 832 字节
空间利用率 = 50 / 100 = 50%

链表（LitLinkedQueue）：

基础开销：
- LitLinkedQueue 对象：约 32 字节
- 每个节点：约 32 字节（对象头 + value + next 指针）

实际占用示例（count = 50）：
32 + 50 × 32 = 1632 字节
空间利用率 = 100%（按需分配）

2. 缓存友好性

循环数组：

• ✅ 内存连续，CPU 缓存命中率高
• ✅ 适合现代 CPU 的预取机制
• ✅ 遍历性能优秀

链表：

• ❌ 内存分散，缓存命中率低
• ❌ 节点跳转导致缓存失效
• ⚠️ 遍历性能相对较差

3. 内存碎片

循环数组：

• ✅ 单次大块分配，碎片少
• ❌ 扩容时可能产生内存峰值

链表：

• ⚠️ 频繁小对象分配，可能产生碎片
• ✅ 无扩容峰值

优缺点总结

循环数组（LitQueue）

优点：

1. ✅ 缓存友好：连续内存，遍历性能优秀
2. ✅ 支持随机访问：可通过索引快速访问任意位置元素
3. ✅ 内存占用相对较小：没有额外的节点对象开销
4. ✅ 空间局部性好：对 CPU 缓存友好

缺点：

1. ❌ 需要预分配容量：初始化时需要指定大小
2. ❌ 扩容开销：满时需要 O(n) 的扩容操作，可能导致性能抖动
3. ❌ 空间浪费：容量大于实际元素数时会浪费空间
4. ❌ 扩容时内存峰值：扩容期间会同时存在新旧两个数组

链表（LitLinkedQueue）

优点：

1. ✅ 真正的 O(1) 操作：所有操作都是常数时间，无扩容
2. ✅ 无需预分配：按需分配，初始化快速
3. ✅ 动态增长：天然支持任意大小，不会满
4. ✅ 无内存峰值：没有扩容，内存增长平稳
5. ✅ 实现简单：代码更简洁，易于理解和维护

缺点：

1. ❌ 节点开销：每个元素需要额外的节点对象（约 32 字节）
2. ❌ 缓存不友好：内存分散，CPU 缓存命中率低
3. ❌ 不支持随机访问：访问第 n 个元素需要 O(n) 时间
4. ❌ 内存碎片：频繁分配小对象可能产生碎片

代码复杂度对比

循环数组：

• 代码量：约 210 行
• 需要处理：扩容、缩容、循环索引计算
• 维护成本：较高

链表：

• 代码量：约 190 行
• 逻辑简单：只需维护头尾指针
• 维护成本：较低

适用场景分析

选择循环数组（LitQueue）的场景

1. 队列大小可预估且相对固定

   // 示例：音频缓冲队列，固定 1024 个采样点
   LitQueue *audioBuffer = [LitQueue queueWithCapacity:1024];

2. 需要频繁遍历队列

   // 示例：需要定期检查队列中所有任务的状态
   NSArray *tasks = [queue toArray];
   for (Task *task in tasks) {
       [task checkStatus];
   }

3. 对内存占用敏感

   // 示例：嵌入式设备或内存受限环境
   // 循环数组比链表节省约 50% 的内存
   LitQueue *messageQueue = [LitQueue queueWithCapacity:100];

4. 对性能稳定性要求不高

   // 示例：非实时任务调度，可以容忍偶尔的扩容延迟
   LitQueue *backgroundTasks = [LitQueue queueWithCapacity:50];

5. 需要随机访问队列元素

   // 示例：消息队列中需要查看特定位置的消息
   // 只有循环数组支持 O(1) 随机访问

选择链表（LitLinkedQueue）的场景

1. 队列大小不可预估或变化剧烈

   // 示例：网络请求队列，请求数量不确定
   LitLinkedQueue *requestQueue = [LitLinkedQueue queue];

2. 对性能稳定性要求高

   // 示例：实时音视频处理，不能有性能抖动
   // 链表的所有操作都是真正的 O(1)
   LitLinkedQueue *frameQueue = [LitLinkedQueue queue];

3. 入队出队频繁，很少遍历

   // 示例：生产者-消费者模型
   LitLinkedQueue *workQueue = [LitLinkedQueue queue];
   
   // 生产者
   dispatch_async(producerQueue, ^{
       while (producing) {
           id work = [self produceWork];
           [workQueue enqueue:work];
       }
   });
   
   // 消费者
   dispatch_async(consumerQueue, ^{
       while (consuming) {
           if (!workQueue.isEmpty) {
               id work = [workQueue dequeue];
               [self consumeWork:work];
           }
       }
   });

4. 需要优先考虑代码简洁性

   // 链表实现更简单，易于维护和扩展
   LitLinkedQueue *eventQueue = [LitLinkedQueue queue];

5. 频繁创建和销毁队列

   // 示例：临时任务处理
   // 链表无需预分配，创建更快
   for (int i = 0; i < 100; i++) {
       LitLinkedQueue *tempQueue = [LitLinkedQueue queue];
       [self processWithQueue:tempQueue];
       // 销毁时也更快
   }

实际项目场景举例

场景 1：图片下载队列（推荐链表）

@interface ImageDownloader : NSObject
@property (nonatomic, strong) LitLinkedQueue<ImageDownloadTask *> *downloadQueue;
@end

@implementation ImageDownloader

- (instancetype)init {
    if (self = [super init]) {
        // 使用链表：任务数量不确定，频繁入队出队
        _downloadQueue = [LitLinkedQueue queue];
    }
    return self;
}

- (void)downloadImage:(NSURL *)url completion:(void(^)(UIImage *))completion {
    ImageDownloadTask *task = [[ImageDownloadTask alloc] initWithURL:url completion:completion];
    [self.downloadQueue enqueue:task];
    [self processNextTask];
}

- (void)processNextTask {
    if (!self.downloadQueue.isEmpty) {
        ImageDownloadTask *task = [self.downloadQueue dequeue];
        [self executeTask:task];
    }
}

@end

选择理由：

• 下载任务数量不可预估
• 频繁入队出队，很少遍历
• 需要性能稳定，避免扩容抖动

场景 2：音频环形缓冲（推荐循环数组）

@interface AudioRingBuffer : NSObject
@property (nonatomic, strong) LitQueue<AudioSample *> *sampleBuffer;
@end

@implementation AudioRingBuffer

- (instancetype)init {
    if (self = [super init]) {
        // 使用循环数组：固定 4096 个采样点
        _sampleBuffer = [LitQueue queueWithCapacity:4096];
    }
    return self;
}

- (void)writeSample:(AudioSample *)sample {
    if (self.sampleBuffer.count == 4096) {
        // 满了就丢弃最旧的样本
        [self.sampleBuffer dequeue];
    }
    [self.sampleBuffer enqueue:sample];
}

- (AudioSample *)readSample {
    if (!self.sampleBuffer.isEmpty) {
        return [self.sampleBuffer dequeue];
    }
    return nil;
}

@end

选择理由：

• 缓冲区大小固定（4096）
• 对缓存友好性要求高（音频处理）
• 内存占用小
• 永远不会触发扩容（满了就覆盖）

场景 3：消息队列（推荐链表）

@interface MessageQueue : NSObject
@property (nonatomic, strong) LitLinkedQueue<Message *> *pendingMessages;
@end

@implementation MessageQueue

- (instancetype)init {
    if (self = [super init]) {
        // 使用链表：消息数量波动大
        _pendingMessages = [LitLinkedQueue queue];
    }
    return self;
}

- (void)sendMessage:(Message *)message {
    [self.pendingMessages enqueue:message];
    [self processMessages];
}

- (void)processMessages {
    while (!self.pendingMessages.isEmpty) {
        Message *message = [self.pendingMessages dequeue];
        [self handleMessage:message];
    }
}

@end

选择理由：

• 消息数量完全不可预估
• 可能突然涌入大量消息
• 需要快速入队出队
• 避免扩容带来的延迟

性能测试对比

下面是一个简单的性能测试，对比两种实现在不同操作下的表现：

- (void)performanceTest {
    NSInteger testCount = 10000;
    
    // 测试 1：连续入队
    {
        LitQueue *arrayQueue = [LitQueue queueWithCapacity:10];
        LitLinkedQueue *linkedQueue = [LitLinkedQueue queue];
        
        // 循环数组：会触发多次扩容
        CFTimeInterval start1 = CACurrentMediaTime();
        for (NSInteger i = 0; i < testCount; i++) {
            [arrayQueue enqueue:@(i)];
        }
        CFTimeInterval time1 = CACurrentMediaTime() - start1;
        
        // 链表：无扩容
        CFTimeInterval start2 = CACurrentMediaTime();
        for (NSInteger i = 0; i < testCount; i++) {
            [linkedQueue enqueue:@(i)];
        }
        CFTimeInterval time2 = CACurrentMediaTime() - start2;
        
        NSLog(@"入队 %ld 个元素:", testCount);
        NSLog(@"  循环数组: %.4f 秒 (含扩容)", time1);
        NSLog(@"  链表:     %.4f 秒", time2);
    }
    
    // 测试 2：入队+出队混合
    {
        LitQueue *arrayQueue = [LitQueue queueWithCapacity:1000];
        LitLinkedQueue *linkedQueue = [LitLinkedQueue queue];
        
        CFTimeInterval start1 = CACurrentMediaTime();
        for (NSInteger i = 0; i < testCount; i++) {
            [arrayQueue enqueue:@(i)];
            if (i % 2 == 0 && !arrayQueue.isEmpty) {
                [arrayQueue dequeue];
            }
        }
        CFTimeInterval time1 = CACurrentMediaTime() - start1;
        
        CFTimeInterval start2 = CACurrentMediaTime();
        for (NSInteger i = 0; i < testCount; i++) {
            [linkedQueue enqueue:@(i)];
            if (i % 2 == 0 && !linkedQueue.isEmpty) {
                [linkedQueue dequeue];
            }
        }
        CFTimeInterval time2 = CACurrentMediaTime() - start2;
        
        NSLog(@"\n混合操作 %ld 次:", testCount);
        NSLog(@"  循环数组: %.4f 秒", time1);
        NSLog(@"  链表:     %.4f 秒", time2);
    }
    
    // 测试 3：遍历性能
    {
        LitQueue *arrayQueue = [LitQueue queueWithCapacity:testCount];
        LitLinkedQueue *linkedQueue = [LitLinkedQueue queue];
        
        for (NSInteger i = 0; i < testCount; i++) {
            [arrayQueue enqueue:@(i)];
            [linkedQueue enqueue:@(i)];
        }
        
        CFTimeInterval start1 = CACurrentMediaTime();
        NSArray *array1 = [arrayQueue toArray];
        for (id obj in array1) {
            // 模拟访问
            [obj description];
        }
        CFTimeInterval time1 = CACurrentMediaTime() - start1;
        
        CFTimeInterval start2 = CACurrentMediaTime();
        NSArray *array2 = [linkedQueue toArray];
        for (id obj in array2) {
            // 模拟访问
            [obj description];
        }
        CFTimeInterval time2 = CACurrentMediaTime() - start2;
        
        NSLog(@"\n遍历 %ld 个元素:", testCount);
        NSLog(@"  循环数组: %.4f 秒", time1);
        NSLog(@"  链表:     %.4f 秒", time2);
    }
}

典型测试结果：

入队 10000 个元素:
  循环数组: 0.0023 秒 (含扩容)
  链表:     0.0018 秒

混合操作 10000 次:
  循环数组: 0.0015 秒
  链表:     0.0012 秒

遍历 10000 个元素:
  循环数组: 0.0008 秒
  链表:     0.0012 秒

测试结论：

1. 链表在频繁入队时性能更稳定（无扩容抖动）
2. 循环数组在遍历时性能更优（缓存友好）
3. 混合操作下两者性能接近
4. 实际差异在微秒级别，选择时应更关注适用场景

线程安全考虑

上述两种实现都不是线程安全的。在多线程环境下使用时，需要添加同步机制：

方案 1：使用锁

@interface ThreadSafeQueue : NSObject
@property (nonatomic, strong) LitLinkedQueue *queue;
@property (nonatomic, strong) NSLock *lock;
@end

@implementation ThreadSafeQueue

- (instancetype)init {
    if (self = [super init]) {
        _queue = [LitLinkedQueue queue];
        _lock = [[NSLock alloc] init];
    }
    return self;
}

- (void)enqueue:(id)object {
    [self.lock lock];
    [self.queue enqueue:object];
    [self.lock unlock];
}

- (id)dequeue {
    [self.lock lock];
    id object = nil;
    if (!self.queue.isEmpty) {
        object = [self.queue dequeue];
    }
    [self.lock unlock];
    return object;
}

@end

方案 2：使用 GCD 串行队列

@interface ConcurrentQueue : NSObject
@property (nonatomic, strong) LitLinkedQueue *queue;
@property (nonatomic, strong) dispatch_queue_t syncQueue;
@end

@implementation ConcurrentQueue

- (instancetype)init {
    if (self = [super init]) {
        _queue = [LitLinkedQueue queue];
        _syncQueue = dispatch_queue_create("com.example.queue", DISPATCH_QUEUE_SERIAL);
    }
    return self;
}

- (void)enqueue:(id)object {
    dispatch_sync(self.syncQueue, ^{
        [self.queue enqueue:object];
    });
}

- (id)dequeue {
    __block id object = nil;
    dispatch_sync(self.syncQueue, ^{
        if (!self.queue.isEmpty) {
            object = [self.queue dequeue];
        }
    });
    return object;
}

@end

最佳实践建议

1. 根据场景选择

// ✅ 好的选择
// 场景：固定大小的音频缓冲
LitQueue *audioBuffer = [LitQueue queueWithCapacity:4096];

// ✅ 好的选择
// 场景：网络请求队列，数量不确定
LitLinkedQueue *requestQueue = [LitLinkedQueue queue];

// ❌ 不好的选择
// 场景：任务数量不确定，但用了固定容量
LitQueue *taskQueue = [LitQueue queueWithCapacity:10]; // 可能频繁扩容

2. 合理设置初始容量

// ✅ 好的做法：根据历史数据设置合理的初始容量
// 假设 90% 的情况下任务数不超过 100
LitQueue *taskQueue = [LitQueue queueWithCapacity:100];

// ❌ 不好的做法：容量过小，频繁扩容
LitQueue *taskQueue = [LitQueue queueWithCapacity:2];

// ❌ 不好的做法：容量过大，浪费内存
LitQueue *taskQueue = [LitQueue queueWithCapacity:100000];

3. 注意内存管理

// ✅ 好的做法：及时清空不再使用的队列
[queue removeAllObjects];
queue = nil;

// ✅ 好的做法：使用弱引用避免循环引用
@weakify(self);
[queue enqueue:^{
    @strongify(self);
    [self doSomething];
}];

4. 异常处理

// ✅ 好的做法：检查队列状态
if (!queue.isEmpty) {
    id obj = [queue dequeue];
    [self process:obj];
}

// ❌ 不好的做法：不检查直接出队（会抛异常）
id obj = [queue dequeue]; // 队列为空时 Crash

总结

通过本文的详细对比，我们可以得出以下结论：

关键区别

选择建议

选择循环数组（LitQueue）当：

• ✅ 队列大小可预估
• ✅ 需要频繁遍历
• ✅ 内存受限
• ✅ 需要随机访问

选择链表（LitLinkedQueue）当：

• ✅ 队列大小不确定
• ✅ 对性能稳定性要求高
• ✅ 频繁入队出队
• ✅ 很少遍历队列

最终建议

在实际项目中，链表实现（LitLinkedQueue）是更通用的选择，因为：

1. 真正的 O(1) 性能，无扩容抖动
2. 实现简单，易于维护
3. 适应性强，适合大多数场景

只有在以下明确需求时，才考虑使用循环数组：

1. 队列大小固定或可准确预估
2. 需要高频遍历或随机访问
3. 对内存占用极度敏感

记住：过早优化是万恶之源。如果不确定，就选择更简单、更通用的链表实现。等到真正遇到性能瓶颈时，再根据 Profiling 结果进行针对性优化。

参考资料

• Apple Developer Documentation - NSMutableArray
• 数据结构：循环数组详解
• Thomas H. Cormen et al. 《算法导论》（第3版）
• Robert Sedgewick, Kevin Wayne. 《算法》（第4版）
• Queue (abstract data type) - Wikipedia