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

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

本的版本是一个堆栈,而不是一个队列,所以我调整了一下:

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方法那样调用它们。

祝你好运,并继续编码!

我不会说,使用NSMutableArray必然是最好的解决scheme,特别是如果你添加类别的方法,由于如果方法名称相撞,他们可以导致的脆弱性。 对于一个快速的n-dirty队列,我会使用方法来添加和删除一个可变数组的末尾。 但是,如果您打算重用队列,或者希望自己的代码更具可读性和自理性,则可能需要专门的队列类。

cocoa没有一个内置的,但也有其他的select,你不必从头开始写一个。 对于只添加和删除两端的真正队列,循环缓冲区数组是一个非常快速的实现。 查看CHDataStructures.framework ,这是我一直在研究的Objective-C中的一个库/框架。 它有各种各样的队列实现,以及栈,deques,sorting集等。为了您的目的, CHCircularBufferQueue比使用NSMutableArray更快(即可以基准testing),并且更具可读性(当然是主观的)。

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

最后,虽然从两端添加和删除NSMutableArray比标准的C数组要好,但它也不是队列中最快的解决scheme。 对于大多数应用程序来说,这是令人满意的,但是如果你需要速度的话,一个循环缓冲区(或者在某些情况下为了保持高速caching线而优化的链表)可能会轻易地给NSMutableArray带来麻烦。

据我所知,Objective-C不提供队列数据结构。 最好的select是创build一个NSMutableArray ,然后使用[array lastObject][array removeLastObject]来获取该项目, [array insertObject:o atIndex:0]

如果你这样做了很多,你可能需要创build一个Objective-C类来扩展NSMutableArray类的function。 类别允许你dynamic添加函数到现有的类(甚至是你没有的源代码) – 你可以像这样创build一个队列:

(注意:这个代码实际上是一个堆栈,而不是一个队列,见下面的注释)

 @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 

没有真正的队列集合类,但NSMutableArray可以有效地用于相同的事情。 如果需要,可以定义一个类别来添加popup/推送方法。

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

回复:Wolfcow – 下面是Wolfcow的出列方法的更正实现

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

这是我的实现,希望它有帮助。

是一种简约,所以你必须保持头部的轨道,通过保存新的头部stream行和丢弃旧的头部

 @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 

NSMutableArray上使用类别的解决scheme不是真正的队列,因为NSMutableArray公开了作为队列超集的操作。 例如,您不应该被允许从队列中间删除一个项目(因为这些类别的解决scheme仍然允许)。 封装function是最好的,这是面向对象devise的一个主要原则。

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 

使用NSMutableArray。

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

与Objective C对象一起使用STL队列/向量/列表等的一个问题是,它们通常不支持保留/释放/自动释放内存pipe理。 这很容易与C ++智能指针容器类一起使用,它在构build时保留其Objective C对象,并在销毁时释放它。 根据你在STL队列中input的内容,这往往是不必要的。