如何在Objective-C中创建和使用队列？

Question

我想在我的Objective-C程序中使用队列数据结构。在C++中，我会使用STL队列。那么，在Objective-C中等价的数据结构是什么？如何进行push/pop操作？

- MrDatabase

Answer 1

Ben的版本使用的是堆栈而不是队列，所以我稍微调整了一下：

NSMutableArray+QueueAdditions.h

@interface NSMutableArray (QueueAdditions)
- (id) dequeue;
- (void) enqueue:(id)obj;
@end

NSMutableArray+QueueAdditions.m

@implementation NSMutableArray (QueueAdditions)
// Queues are first-in-first-out, so we remove objects from the head
- (id) dequeue {
    // if ([self count] == 0) return nil; // to avoid raising exception (Quinn)
    id headObject = [self objectAtIndex:0];
    if (headObject != nil) {
        [[headObject retain] autorelease]; // so it isn't dealloc'ed on remove
        [self removeObjectAtIndex:0];
    }
    return headObject;
}

// Add to the tail of the queue (no one likes it when people cut in line!)
- (void) enqueue:(id)anObject {
    [self addObject:anObject];
    //this method automatically adds to the end of the array
}
@end

只需在想要使用新方法的地方导入.h文件，并像使用任何其他NSMutableArray方法一样调用它们。

- Wolfcow

---

我已将此代码添加到 Github 存储库。随意分叉，或让我知道是否有什么问题：https://github.com/esromneb/ios-queue-object 谢谢!!! - benathon

@portforwardpodcast：好的，我终于开始分叉和拉取请求了，找到了一种方法，可以在有ARC和没有ARC的情况下都能工作。 - Claudiu

我是否漏掉了什么，或者这个实现在出队时具有O(n)的复杂度？那太糟糕了。你最好使用循环数组实现。这个实现可能会工作，但是O(n)出队的想法是令人痛苦的。 - ThatGuy

@Wolfcow，当你从索引0处移除一个对象时，数组中的每个对象都会向下移动一个位置。因此，要删除单个项目，其时间复杂度为O（n）。对于小型队列来说可能还好，这可能占移动应用程序99%的时间，但对于大型数据集和时间关键的情况来说，这将是糟糕的解决方案。再次强调，在大多数Objective C情况下，您不太可能遇到这种情况。 - ThatGuy

@ThatGuy 有点晚了，但NSArray是使用循环缓冲区实现的，因此运行时不会是theta(N)。 - hhanesand

Answer 2

我不会说使用NSMutableArray一定是最好的解决方案，特别是如果您正在添加具有类别的方法，由于方法名称冲突可能会导致脆弱性。对于一个快速而简单的队列，我会使用在可变数组末尾添加和删除元素的方法。但是，如果您计划重用队列，或者希望您的代码更易读和自明，则专用队列类可能是您想要的。

Cocoa没有内置队列，但还有其他选择，您也不必从头开始编写。对于仅从结尾添加和删除的真正队列，循环缓冲区数组是一种极快的实现。请查看CHDataStructures.framework，这是我正在开发的Objective-C库/框架。它具有各种队列实现、堆栈、双端队列、排序集等。对于您的目的，CHCircularBufferQueue比使用NSMutableArray更快（即基准证明）且更易读（诚然有主观性）。

使用本地Objective-C类而不是C++ STL类的一个巨大优势是它与Cocoa代码无缝集成，并且在编码/解码（序列化）方面工作得更好。它还可以完美地与垃圾回收和快速枚举配合使用（两者均在10.5+上存在，但仅iPhone上存在后者），您不必担心什么是Objective-C对象，什么是C++对象。

最后，尽管NSMutableArray在从任一端添加和删除时比标准的C数组更好，但它也不是队列的最快解决方案。对于大多数应用程序来说，它是令人满意的，但如果您需要速度，循环缓冲区（或在某些情况下优化以保持高速缓存行的链表）可以轻松击败NSMutableArray。

- Quinn Taylor

---

很高兴有人真正回答了一个真正的队列解决方案。 - Casebash

所有的链接都失效了 - 我在哪里可以获取那个框架？我已经读了很多关于它的好东西，但是找不到实际的代码！ - amok

这个框架听起来很有前途，但是 SVN 的链接仍然无法使用。有没有可能在其他地方获取代码？编辑：我从 http://mac.softpedia.com/progDownload/CHDataStructures-Download-73842.html 获取了代码，但我看不出这是否是当前版本。 - Kay

Dave DeLong的Git repo clone 似乎是当今最受欢迎的代码库。 - Regexident

Answer 3

据我所知，Objective-C没有提供队列数据结构。你最好创建一个NSMutableArray，然后使用[array lastObject]、[array removeLastObject]来获取项目，以及[array insertObject:o atIndex:0]将项目插入到数组的开头。

如果您需要经常这样做，可以创建一个Objective-C分类来扩展NSMutableArray类的功能。分类允许您动态地向现有类（甚至是那些没有源代码的类）添加函数 - 您可以像这样创建一个队列： （注意：此代码实际上是用于堆栈而不是队列。请参见下面的注释）

@interface NSMutableArray (QueueAdditions)

- (id)pop;
- (void)push:(id)obj;

@end

@implementation NSMutableArray (QueueAdditions)

- (id)pop
{
    // nil if [self count] == 0
    id lastObject = [[[self lastObject] retain] autorelease];
    if (lastObject)
        [self removeLastObject];
    return lastObject;
}

- (void)push:(id)obj
{
     [self addObject: obj];
}

@end

- Ben Gotow

---

你是否意识到你实现了一个栈而不是队列？ - Jim Puls

啊 - 抱歉！请看Wolfcow的修改。 - Ben Gotow

如果你把“最佳选择”替换为“最简单的选项”，我会同意。 :-) 数据结构纯粹主义者和性能追求者更喜欢真正的队列，但NSMutableArray可以轻松地代替队列。 - Quinn Taylor

+1 给 Ben，因为我想要一个堆栈（stack）的解决方案，尽管要求使用队列（queue）。 :) - whitneyland

我唯一能想到的就是痛苦。如果你要在数组的开头插入一个对象，那么每次插入都需要将每个元素往后移动一位。在这种情况下，使用链表会更加有效。 - TheM00s3

Answer 4

虽然没有真正的队列集合类，但NSMutableArray可以用于实现类似的功能。如果需要方便地添加pop/push方法，可以定义一个category。

- Marc Charbonneau

---

一个NSMutableArray可以作为一个相当不错的队列，尽管从前面移除元素并不是数组结构擅长的。即便如此，对于小型队列来说，性能也不是一个主要问题。我的一个朋友之前在博客上写过这个话题...http://sg80bab.blogspot.com/2008/05/nsmutablearray-makes-awesome-cocoa.html - Quinn Taylor

Answer 5

是的，请使用NSMutableArray。NSMutableArray实际上是作为2-3树实现的；通常您不需要关心在任意索引处向NSMutableArray添加或删除对象的性能特征。

- the fridge owl

---

NSArray（以及通过扩展的NSMutableArray）是一个类簇，这意味着它有几个私有实现可以在幕后互换使用。你通常得到的取决于元素数量。此外，苹果公司随时可以更改任何给定实现的细节。但是，你是正确的，它通常比标准数组更灵活。 - Quinn Taylor

Answer 6

关于Wolfcow -- 这里是Wolfcow出列方法的修正实现

- (id)dequeue {
    if ([self count] == 0) {
        return nil;
    }
    id queueObject = [[[self objectAtIndex:0] retain] autorelease];
    [self removeObjectAtIndex:0];
    return queueObject;
}

- DougW

Answer 7

使用NSMutableArray类别的解决方案并不是真正的队列，因为NSMutableArray公开了超集的操作。例如，您不应该允许从队列中间删除项目（而这些类别解决方案仍然可以让您这样做）。封装功能是面向对象设计的一个重要原则，最好将其封装起来。

StdQueue.h

#import <Foundation/Foundation.h>

@interface StdQueue : NSObject

@property(nonatomic, readonly) BOOL empty;
@property(nonatomic, readonly) NSUInteger size;
@property(nonatomic, readonly) id front;
@property(nonatomic, readonly) id back;

- (void)enqueue:(id)object;
- (id)dequeue;

@end

StdQueue.m

#import "StdQueue.h"

@interface StdQueue ()

@property(nonatomic, strong) NSMutableArray* storage;

@end

@implementation StdQueue

#pragma mark NSObject

- (id)init
{
    if (self = [super init]) {
        _storage = [NSMutableArray array];
    }
    return self;
}

#pragma mark StdQueue

- (BOOL)empty
{
    return self.storage.count == 0;
}

- (NSUInteger)size
{
    return self.storage.count;
}

- (id)front
{
    return self.storage.firstObject;
}

- (id)back
{
    return self.storage.lastObject;
}

- (void)enqueue:(id)object
{
    [self.storage addObject:object];
}

- (id)dequeue
{
    id firstObject = nil;
    if (!self.empty) {
        firstObject  = self.storage.firstObject;
        [self.storage removeObjectAtIndex:0];
    }
    return firstObject;
}

@end

- Pwner

---

有人可能会认为，通过某些技术（例如KVC），可以直接访问和操作内部存储数组，但是这比使用类别要好得多。 - vikingosegundo

Answer 8

这是我的实现，希望能对你有所帮助。

这种实现方式比较简洁，所以需要通过在弹出元素时保存新的头部并丢弃旧的头部来跟踪头部。

@interface Queue : NSObject {
    id _data;
    Queue *tail;
}

-(id) initWithData:(id) data;
-(id) getData;

-(Queue*) pop;
-(void) push:(id) data;

@end

#import "Queue.h"

@implementation Queue

-(id) initWithData:(id) data {
    if (self=[super init]) {
        _data = data;
        [_data retain];
    }
    return self;
}
-(id) getData {
    return _data;
}

-(Queue*) pop {
    return tail;
}
-(void) push:(id) data{
    if (tail) {
        [tail push:data];
    } else {
        tail = [[Queue alloc]initWithData:data];
    }
}

-(void) dealloc {
    if (_data) {
        [_data release];
    }
    [super release];
}

@end

- Moxor

Answer 9

你为什么不能使用STL队列呢？Objective C++是C++的超集（只需使用.mm扩展名即可使用Objective C++而不是Objective C）。然后，您可以使用STL或任何其他C++代码。

使用STL队列/向量/列表等与Objective C对象存在一个问题，即它们通常不支持保留/释放/自动释放内存管理。这可以通过使用C++智能指针容器类轻松解决，该类在构造时保留其Objective C对象，并在销毁时释放它。根据您放入STL队列中的内容，通常不需要这样做。

- Peter N Lewis

---

这似乎不是一个好主意...仅仅因为你可以做某事并不意味着你应该这样做。为了队列类而拉入整个STL和C++生态系统绝对是杀鸡焉用牛刀。 - n s

自从这篇文章发布以来，这个想法已经变得更好了。Objective C++/ARC 意味着您可以使用 Objective C 对象指针与 STL 容器，并且一切都可以正常工作。ARC 会自动在 C++ 结构中处理内存管理。我通常也会认为 C++ 更好，因此在选择普通的 Objective C 时，Objective-C++ 是一个更好的选择（例如提供 enum class）。我非常怀疑添加 STL/C++ 会对任何真实应用程序的大小产生明显影响。 - Peter N Lewis

Answer 10

使用NSMutableArray。

- Nuoji