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

Question

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?

Answer 1

Ben's version is a stack instead of a queue, so i tweaked it a bit:

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 

Just import the .h file wherever you want to use your new methods, and call them like you would any other NSMutableArray methods.

Good luck and Keep on Coding!

Answer 2

I wouldn't say that using NSMutableArray is necessarily the best solution, 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.

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, CHCircularBufferQueue is significantly faster (i.e. provable with benchmarks) and more readable (admittedly subjective) than using an 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.

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.