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

There's no real queue collections class, but NSMutableArray can be used for effectively the same thing. You can define a category to add pop/push methods as a convenience if you want.

Answer 2

Use NSMutableArray.

Answer 3

As far as I know, Objective-C does not provide a Queue data structure. Your best bet is to create an NSMutableArray, and then use [array lastObject], [array removeLastObject] to fetch the item, and [array insertObject:o atIndex:0]...

If you're doing this a lot, you might want to create an Objective-C category to extend the functionality of the NSMutableArray class. Categories allow you to dynamically add functions to existing classes (even the ones you don't have the source for) - you could make a queue one like this:

(NOTE: This code is actually for a stack, not a queue. See comments below)

@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

Answer 4

Yes, use NSMutableArray. NSMutableArray is actually implemented as 2-3 tree; you typically need not concern yourself with the performance characteristics of adding or removing objects from NSMutableArray at arbitrary indices.

Answer 5

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 6

Is there some particular reason you cannot just use the STL queue? Objective C++ is a superset of C++ (just use .mm as the extension instead of .m to use Objective C++ instead of Objective C). Then you can use the STL or any other C++ code.

One issue of using the STL queue/vector/list etc with Objective C objects is that they do not typically support retain/release/autorelease memory management. This is easily worked around with a C++ Smart Pointer container class which retains its Objective C object when constructed and releases it when destroyed. Depending on what you are putting in the STL queue this is often not necessary.

Answer 7

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.

Answer 8

re:Wolfcow -- Here is a corrected implementation of Wolfcow's dequeue method

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

Answer 9

People need to read the apple documentation more. What you're looking for is an NSProxy. it'll automatically queue up anything you send it.

-edit: On second thought just use an NSOperationQueue.