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

前言

队列（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 自动回收

两种实现方式的深度对比

性能对比

操作	循环数组 (LitQueue)	链表 (LitLinkedQueue)
入队 (enqueue)	O(1) 摊销 （扩容时 O(n)）	O(1) 真正常数时间
出队 (dequeue)	O(1) （缩容时 O(n)）	O(1) 真正常数时间
查看队头 (peek)	O(1)	O(1)
查看队尾 (last)	O(1)	O(1)
随机访问	O(1) 支持	O(n) 不支持
空间开销（每个元素）	8 字节（指针）	16 字节（对象+指针）
初始化	O(n) 需预分配	O(1) 无需预分配
清空队列	O(n)	O(n)

内存特性对比

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

总结

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

关键区别

维度	循环数组	链表
核心思想	预分配+循环索引	动态节点+指针
性能特点	O(1) 摊销	O(1) 真实
内存占用	较小但可能浪费	较大但按需分配
缓存友好	优秀	较差
代码复杂度	较高	较低

选择建议

选择循环数组（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