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

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

1> Wolfcow..：

---

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

祝你好运,继续编码!

---

@ Wolffow,当你从索引0中删除一个对象时,数组中的每个对象都向下移动一个.因此,要删除单个项目,则为O(n).对于小型队列来说可能很好,这在移动应用程序中可能占99%,但对于时间紧迫的情况下的大型数据集来说,这将是一个糟糕的解决方案.同样,并非你在大多数客观C情境中都能找到它.

---

我已将此代码添加到github仓库中.如果我出错了,请随意分叉或告诉我:https://github.com/esromneb/ios-queue-object谢谢!

---

我是否缺少某些东西，或者此实现在出队时是否具有O（n）复杂性？这太可怕了。使用圆形数组实现会更好。此实现可能有效，但是O（n）出队的想法很痛苦。

---

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

2> Quinn Taylor..：

---

我不会说使用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.

---

很高兴有人真的回复了真正的队列解决方案

3> Ben Gotow..：

---

据我所知,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

---

你知道你在这里实现了堆栈,而不是队列吗？

---

类别非常有用.

---

+1到本,因为我想要一个堆栈解决方案,即使队列被要求:)

4> Marc Charbon..：

---

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

5> 小智..：

---

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

6> DougW..：

---

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

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