iPhone上是否有队列/先进先出（FIFO）的数据结构？

Question

在我使用NSMutableArray之前，我想知道是否有更标准的方式来实现队列。我在苹果文档中没有看到任何信息，但如果没有人们正在使用的队列实现，我会感到惊讶的。Java让我太宠了！

- George Armhold

Answer 1

使用NSMutableArray实现队列非常简单，可能不超过50行代码。

编辑：

在快速搜索中找到了这个：

@interface Queue:NSObject {
   NSMutableArray* objects;
}
- (void)addObject:(id)object;
- (id)takeObject;
@end

@implementation Queue

- (id)init {
   if ((self = [super init])) {
       objects = [[NSMutableArray alloc] init];    
   }
   return self;
}

- (void)dealloc {
    [objects release];
    [super dealloc];
}

- (void)addObject:(id)object {
   [objects addObject:object];
}

- (id)takeObject  {
   id object = nil;
   if ([objects count] > 0) {
       object = [[[objects objectAtIndex:0] retain] autorelease];
       [objects removeObjectAtIndex:0];
   }
   return object;
}

@end

- Matt Bridges

---

+1 我稍微整理了一下代码格式和-takeObject方法。 - Quinn Taylor

在你的dealloc方法中加入[objects release]，我会给你一个+1。 - slf

一种更好的实现方式是使用链表。通过使用链表，您可以将每个操作的时间优化为O(1)。使用NSMutableArray时，每个takeObject操作的复杂度为O(n)（removeObjectAtIndex会使所有元素下移）。 - George

缺少一个 { 来打开 takeObject 的代码块。不过回答很好 :) 谢谢！ - braden

Answer 2

Cocoa本身没有队列类，也没有标准的队列类，但有几个选项，其中一个最适合您的需求。请参见这个问题（以及我的回答）。

如你所说，您可以使用NSMutableArray自己编写队列。如果您只需要一个快速且不那么拘谨的队列（并且不用担心复制、编码/解码、枚举等等），那么@Matt建议的解决方案是一个简单的方法。您还应考虑通过分类向NSMutableArray添加队列方法，这样你的“队列”也是一个数组（因此你可以将其作为NSArray参数传递），而且你可以免费获得所有NS（Mutable）Array功能。

如果性能很重要，我建议使用更适合删除第一个元素的结构。出于这个原因，我为自己的框架编写了CHCircularBufferQueue。（不是要吹嘘自己，只是想帮助其他人节省时间。）

- Quinn Taylor

Answer 3

我根据Matt Bridges的代码创建了一个仅包含deque方法的类别。

@interface NSMutableArray (ShiftExtension)
// returns the first element of self and removes it
-(id)shift;
@end

@implementation NSMutableArray (ShiftExtension)
-(id)shift {
    if([self count] < 1) return nil;
    id obj = [[[self objectAtIndex:0] retain] autorelease];
    [self removeObjectAtIndex:0];
    return obj;
}
@end

- neoneye

Answer 4

你可以使用NSArray的:lastObject方法。这里是一个未经测试的示例：

Queue.h

#import <Foundation/Foundation.h>

@interface Queue : NSObject

-(void)enqueue:(id)object;
-(id)dequeue;

@end

Queue.m

#import "Queue.h"

@interface Queue()

@property(nonatomic, strong) NSMutableArray *backingArray;

@end

@implementation Queue

-(id)init {
    self = [super init];

    if (self) {
        self.backingArray = [NSMutableArray array];
    }
    return self;
}

-(void)enqueue:(id<NSObject>)object {
    [self.backingArray addObject:object];
}

-(id)dequeue {
    id object = [self.backingArray lastObject];
    [self.backingArray removeObject:object];
    return object;
}

@end

- Hurshai

Answer 5

你可以使用C++标准库中的STL队列。

- Nick Strupat

---

我发现在Xcode9（9.2）中，Objective C++存在迭代器问题。在我遇到的情况下，map的迭代器无法正确检测map->end()。我会尽量减少在纯iOS代码中使用C++ STL，并尝试将C++保留在与C++ API的接口层。另一个C++代码的复杂性将是内存管理，因为ARC无法处理C++对象。这不是一个阻碍，但如果你习惯了ARC为你清理，那么需要记住这一点。 - bduhbya

Answer 6

看看STL 优先队列。它不需要任何代码，而且是可移植的！你还想要什么呢？

- Rhythmic Fistman