Is there a Queue/FIFO data structure for the iPhone?

Question

Before I roll my own Queue using NSMutableArray, I'd like to know if there is something more standard available. I don't see anything in the Apple docs, but I'll be surprised if there is not a Queue implementation from somewhere that folks are using. Java spoils me!

Answer 1

Implementing a queue based on NSMutableArray is pretty easy, it's probably under 50 lines of code.

EDIT:

Found this with a quick google search:

@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

Answer 2

Cocoa itself doesn't have a Queue class, and there's not a standard per se, but there are several options, one of which may best fit your needs. See this question (and my answer).

Like you said, you can roll your own using NSMutableArray. If you just need a quick'n'dirty queue (and aren't worried about copying, encoding/decoding, enumeration, etc.) then the solution @Matt suggests is an easy approach. You should also consider adding queue methods to NSMutableArray via a category, which is nice in that your "queue" is also an array (so you can pass it for NSArray parameters), and you get all the NS(Mutable)Array functionality for free.

If performance is important, I recommend using a structure more ideally suited for removing the first element. I wrote CHCircularBufferQueue for my own framework for this very reason. (Not trying to toot my own horn, just trying to save others some time.)

Answer 3

I have made a category containing just the deque method, based on Matt Bridges code.

@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

Answer 4

You could use the :lastObject method of NSArray. Here is an untested example:

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

Answer 5

You can use the STL queue from the C++ Standard Library.

Answer 6

Check out the STL priority queue. It requires zero lines of code and it's portable! What more could you want?