iOS SDK是否提供队列和栈？

Question

我正在编写一个iPhone应用程序，但我惊讶地发现在苹果的Foundation框架中似乎没有NSQueue或NSStack类。我看到使用NSMutableArray很容易自己实现这些功能，所以我会这么做，除非我漏掉了什么。我有漏掉了什么吗？

- Tommy Herbert

Answer 1

以下是我的Stack类，希望对后来的人有所帮助。可以看到，pop方法涉及足够多的代码，您需要将其分解。

Stack.h：

#import <Foundation/Foundation.h>

@interface Stack : NSObject {
    NSMutableArray *contents;
}

- (void)push:(id)object;
- (id)pop;

@end

Stack.m

：栈(Stack)的实现，通常用于数据结构和算法问题。

#import "Stack.h"

@implementation Stack

// superclass overrides

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

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

// Stack methods

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

- (id)pop {
    id returnObject = [[contents lastObject] retain];
    if (returnObject) {
            [contents removeLastObject];
    }
    return [returnObject autorelease];
}

@end

- Tommy Herbert

---

对于pop方法，你可以通过使用[contents lastObject]来节省一些打字。如果数组为空，它将返回nil。我最终将这些方法实现为NSMutableArray的类别。感谢提供代码！ - Eric Andres

个人而言，我可能会通过类别将 pop 方法添加到 NSMutableArray 中，并直接在需要堆栈的地方使用 NSMutableArray，而不是创建一个全新的 Stack 类。我以前使用过的大多数语言都没有专用的堆栈类，而是使用数组作为堆栈。虽然我可以从可读性的角度看到只能用作堆栈的类的优雅之处。 - Mark Amery

Answer 2

据我所知，目前没有通用的类可用。尝试使用NSMutableArray，通过addObject添加元素，使用objectAtIndex获取第一个或最后一个元素，使用removeObjectAtIndex删除元素。

- Michael W.

---

请注意，removeObjectAtIndex 是一个 O(n) 操作，因此当预期的项目数量较大时，这可能不是队列的最佳方法。使用链表（允许从任意点高效添加和删除）可能更好，但不幸的是，这是另一种常见的集合类型，缺少基础知识，因此您也必须实现它。 - Jules

Answer 3

另一种简单的方法是通过使用Objective C的分类扩展NSMutableArray的功能。您可以通过向项目添加两个文件来实现：

NSMutableArray+Stack.h

@interface NSMutableArray (StackExtension)

- (void)push:(id)object;
- (id)pop;

@end

NSMutableArray+Stack.m

#import "NSMutableArray+Stack.h"

@implementation NSMutableArray (StackExtension)

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

- (id)pop {
    id lastObject = [self lastObject];
    [self removeLastObject];
    return lastObject;
}

@end

现在，您可以像使用堆栈一样，在项目的其他文件中使用常规的NSMutableArray，并在该对象上调用push或pop。不要忘记在这些文件中#import NSMutableArray+Stack.h。以下是一些示例代码，演示如何将新的NSMutableArray用作堆栈：

NSMutableArray *myStack = [[NSMutableArray alloc] init]; // stack size = 0

NSString *aString = @"hello world";
[myStack push:myString];            // stack size = 1

NSString *anotherString = @"hello universe";
[myStack push:anotherString];       // stack size = 2

NSString *topMostStackObject; 

topMostStackObject = [myStack pop]; // stack size = 1
NSLog("%@",topMostStackObject);

topMostStackObject = [myStack pop]; // stack size = 0
NSLog("%@",topMostStackObject);

日志输出如下：

hello universe
hello world

- Mischa

Answer 4

我有点晚到这个聚会，但是你知道CHDataStructures吗？

http://cocoaheads.byu.edu/code/CHDataStructures

- occulus

Answer 5

我在GitHub上发布了一个可用的iOS Objective C队列对象。这段代码来自于不同的帖子，不是我的独创。

https://github.com/esromneb/ios-queue-object/

如果您发现任何问题，请fork一下，并提出pull request！

- benathon

Answer 6

ObjectiveSugar是一个非常流行的CocoaPod，它提供了许多其他很棒的功能，其中包括在NSMutableArray上调用push和pop API。当然，这不是iOS SDK中的内容，但我在这里分享它，因为我也在寻找同样的东西，而这正是我选择的解决方案（而且我们已经在我们的代码库中使用了这个CocoaPod，这当然没有伤害）。

- Gabe

Answer 7

是的，NSMutableArray可以同时充当栈或队列。（作为队列时效率稍低。）

你也可以使用C++的stack和queue适配器，但如果你想在其中存储Objective-C对象，那么内存管理会变得有些混乱。

- kennytm

Answer 8

没错，你没有漏掉什么。这就是全部。Objective-C 是一种高级语言，类似于 C 语言。不需要低级别的控制。

Cocoa 类设计用于更易于使用而不是效率。如果你想处理性能，可以选择原始的 C（或 C++）实现。否则，只需使用简单的方法即可。当然，过早地优化是有害的。

如果你想要一种封装，只需创建一个包含 NSMutableArray 的新类。隐藏内部的 NSMutableArray，并仅暴露你想要的。但是你会意识到这是不必要的。

- eonil

---

谢谢。我担心的是代码重复，而不是封装。 - Tommy Herbert

不使用队列是邪恶的！你有没有想过它会产生什么影响？NSMutable数组不仅仅是为了方便而设计的（顺便说一下，它们根本不容易使用！），它们实际上是高效的，并且像上面提到的那样，可以用来实现队列。 - Pizzaiola Gorgonzola

@PizzaiolaGorgonzola，很抱歉我不太理解你在这条评论中的真正意思。而且我从未说过Cocoa类是低效的。我的意思是相对于它们的C（或C ++）级别的同行来说，Cocoa类使用起来更加简单，但相对地效率较低。 - eonil