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

Question

我想在Objective-C程序中使用队列数据结构.在C++中,我使用STL队列.Objective-C中的等效数据结构是什么？如何推送/弹出项目？

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方法一样调用它们.

祝你好运,继续编码!

Answer 2

我不会说使用NSMutableArray必然是最好的解决方案,特别是如果你要添加类别的方法,因为如果方法名称冲突会导致它们的脆弱性.对于快速n-dirty队列,我将使用这些方法在可变数组的末尾添加和删除.但是,如果您计划重用该队列,或者您希望您的代码更具可读性和不言而喻,那么可能就是您想要的专用队列类.

Cocoa没有内置的,但还有其他选项,你也不必从头开始编写.对于仅从末端添加和删除的真实队列,循环缓冲区阵列是一种非常快速的实现.查看CHDataStructures.framework,这是我一直在研究的Objective-C中的库/框架.它有各种各样的队列实现,以及堆栈,deques,排序集等.为了您的目的,CHCircularBufferQueue比使用NSMutableArray明显更快(即可用基准测试证明)和更可读(公认的主观).

使用本机Objective-C类而不是C++ STL类的一大优势是它可以与Cocoa代码无缝集成,并且在编码/解码(序列化)方面效果更好.它也可以完美地用于垃圾收集和快速枚举(两者都存在于10.5+中,但只有后者在iPhone上)并且您不必担心什么是Objective-C对象以及什么是C++对象.

最后,虽然NSMutableArray在从任一端添加和删除时比标准C阵列更好,但它也不是队列的最快解决方案.对于大多数应用程序来说它是令人满意的,但是如果你需要速度,循环缓冲区(或者在某些情况下优化的链表以保持缓存行热)可以很容易地破坏NSMutableArray.

Answer 3

据我所知,Objective-C不提供Queue数据结构.你最好的选择是创建一个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

Answer 4

没有真正的队列集合类,但NSMutableArray可以有效地用于相同的事情.您可以根据需要定义一个类别以添加弹出/推送方法.

Answer 5

是的,使用NSMutableArray.NSMutableArray实际上实现为2-3树; 您通常不必关心在任意索引处添加或删除NSMutableArray中的对象的性能特征.

Answer 6

re:Wolfcow - 这是Wolfcow的出列方法的更正实现

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