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

How do I make and use a Queue in Objective-C?

提问by MrDatabase

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 中的等效数据结构是什么？如何推送/弹出项目？

回答by Wolfcow

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!

祝你好运，继续编码！

回答by Quinn Taylor

I wouldn't say that using NSMutableArray is necessarily the bestsolution, 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 一定是最好的解决方案，特别是如果您添加带有类别的方法，因为如果方法名称冲突，它们可能会导致脆弱性。对于quick-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, CHCircularBufferQueueis significantly faster (i.e. provable with benchmarks) and more readable (admittedly subjective) than using an NSMutableArray.

Cocoa 没有内置，但还有其他选项，您也不必从头开始编写。对于仅从末端添加和删除的真正队列，循环缓冲区数组是一种非常快的实现。查看CHDataStructures.framework，这是我一直在研究的 Objective-C 库/框架。它有多种队列实现，以及堆栈、双端队列、排序集等。就您的目的而言，CHCircularBufferQueue比使用 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。

回答by Ben Gotow

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 没有提供 Queue 数据结构。最好的办法是创建一个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 NSMutableArrayclass. 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

回答by Marc Charbonneau

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

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

回答by the fridge owl

Yes, use NSMutableArray. NSMutableArray is actually implementedas 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 添加或删除对象的性能特征。

回答by DougW

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

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

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

回答by Pwner

The solutions that use a category on NSMutableArrayare not true queues, because NSMutableArrayexposes 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

回答by Moxor

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

回答by Peter N Lewis

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.

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

回答by Nuoji

Use NSMutableArray.

使用 NSMutableArray。