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

I want to use a queue data structure in my Objective-C program. In C++ I'd use the STL queue. What is the equivalent data structure in Objective-C? How do I push/pop items?

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

10 个解决方案

#1

151

Ben's version is a stack instead of a queue, so i tweaked it a bit:

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

NSMutableArray+QueueAdditions.h

NSMutableArray + QueueAdditions.h

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

NSMutableArray+QueueAdditions.m

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

Just import the .h file wherever you want to use your new methods, and call them like you would any other NSMutableArray methods.

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

Good luck and Keep on Coding!

祝你好运，继续编码!

#2

I wouldn't say that using NSMutableArray is necessarily the best solution, particularly if you're adding methods with categories, due to the fragility they can cause if method names collide. For a quick-n-dirty queue, I'd use the methods to add and remove at the end of a mutable array. However, if you plan to reuse the queue, or if you want your code to be more readable and self-evident, a dedicated queue class is probably what you want.

我不会说使用NSMutableArray是最好的解决方案，特别是如果你添加了类别的方法，因为如果方法名称发生冲突，它们可能会造成脆弱性。对于快速-n-dirty队列，我将使用这些方法在可变数组的末尾添加和删除。但是，如果您计划重用队列，或者希望您的代码更易于阅读和不言自明，则可能需要一个专用的队列类。

Cocoa doesn't have one built in, but there are other options, and you don't have to write one from scratch either. For a true queue that only adds and removes from the ends, a circular buffer array is an extremely fast implementation. Check out CHDataStructures.framework, a library/framework in Objective-C that I've been working on. It has a variety of implementations of queues, as well as stacks, deques, sorted sets, etc. For your purposes, CHCircularBufferQueue is significantly faster (i.e. provable with benchmarks) and more readable (admittedly subjective) than using an NSMutableArray.

Cocoa没有内置的，但是还有其他的选项，你也不用从头开始写。对于只添加和从末尾删除的真正队列，循环缓冲数组是一种非常快速的实现。查看CHDataStructures.framework, Objective-C中的库/框架，我一直在研究它。它有各种各样的队列实现，以及堆栈、deques、排序集等等。出于您的目的，CHCircularBufferQueue比使用NSMutableArray要快得多(例如，可以用基准测试)，也比使用NSMutableArray更容易读(当然是主观的)。

One big advantage of using a native Objective-C class instead of a C++ STL class is that it integrates seamlessly with Cocoa code, and works much better with encode/decode (serialization). It also works perfectly with garbage collection and fast enumeration (both present in 10.5+, but only the latter on iPhone) and you don't have to worry about what is an Objective-C object and what is a C++ object.

使用本机Objective-C类而不是c++ STL类的一大优点是，它与Cocoa代码无缝集成，并且与编码/解码(串行化)更好。它还可以很好地处理垃圾收集和快速枚举(都在10.5+中出现，但在iPhone中只有后者)，您不必担心什么是Objective-C对象，什么是c++对象。

Lastly, although NSMutableArray is better than a standard C array when adding and removing from either end, it's also not the fastest solution for a queue. For most applications it is satisfactory, but if you need speed, a circular buffer (or in some cases a linked list optimized to keep cache lines hot) can easily trounce an NSMutableArray.

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

#3

As far as I know, Objective-C does not provide a Queue data structure. Your best bet is to create an NSMutableArray, and then use [array lastObject], [array removeLastObject] to fetch the item, and [array insertObject:o atIndex:0]...

据我所知，Objective-C不提供队列数据结构。最好的方法是创建一个NSMutableArray，然后使用[array lastObject]、[array removeLastObject]来获取项，[array insertObject:o atIndex:0]……

If you're doing this a lot, you might want to create an Objective-C category to extend the functionality of the NSMutableArray class. Categories allow you to dynamically add functions to existing classes (even the ones you don't have the source for) - you could make a queue one like this:

如果您经常这样做，您可能希望创建一个Objective-C类别来扩展NSMutableArray类的功能。类别允许您动态地将函数添加到现有的类中(即使是那些您没有源代码的类)——您可以创建一个这样的队列:

(NOTE: This code is actually for a stack, not a queue. See comments below)

(注意:这段代码实际上是一个堆栈，而不是一个队列。请参见下面的评论)

@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

#4

There's no real queue collections class, but NSMutableArray can be used for effectively the same thing. You can define a category to add pop/push methods as a convenience if you want.

没有真正的队列集合类，但是NSMutableArray可以有效地用于相同的事情。如果您愿意，您可以定义一个类别来添加pop/push方法，作为一种方便。

#5

Yes, use NSMutableArray. NSMutableArray is actually implemented as 2-3 tree; you typically need not concern yourself with the performance characteristics of adding or removing objects from NSMutableArray at arbitrary indices.

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

#6

re:Wolfcow -- Here is a corrected implementation of Wolfcow's dequeue method

re:Wolfcow——这里是对Wolfcow的dequeue方法的修正实现

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

#7

this is my implementation, hope it helps.

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

Is kind of minimalistic, so you must keep the track of the head by saving the new head at pop and discarding the old head

是一种极简主义，所以你必须保持头脑的轨迹，把新脑袋保存在流行音乐中，丢弃旧的脑袋?

@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

#8

The solutions that use a category on NSMutableArray are not true queues, because NSMutableArray exposes operations that are a superset of queues. For example, you should not be allowed to remove an item from the middle of a queue (as those category solutions still let you do). It is best to encapsulate functionality, a major principle of object oriented design.

在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

#9

Use NSMutableArray.

使用NSMutableArray。

#10

Is there some particular reason you cannot just use the STL queue? Objective C++ is a superset of C++ (just use .mm as the extension instead of .m to use Objective C++ instead of Objective C). Then you can use the STL or any other C++ code.

有什么特别的原因让你不能仅仅使用STL队列吗?Objective c++是c++的超集(只是使用.mm作为扩展而不是.m来使用Objective C++而不是Objective C)，然后您可以使用STL或任何其他c++代码。

One issue of using the STL queue/vector/list etc with Objective C objects is that they do not typically support retain/release/autorelease memory management. This is easily worked around with a C++ Smart Pointer container class which retains its Objective C object when constructed and releases it when destroyed. Depending on what you are putting in the STL queue this is often not necessary.

对目标C对象使用STL队列/向量/列表等的一个问题是，它们通常不支持保留/释放/自动释放内存管理。使用c++智能指针容器类很容易做到这一点，该类在构造时保留目标C对象，在销毁时释放目标C对象。根据您放入STL队列的内容，这通常是不必要的。

#1

151