[ACCEPTED]-How do I make and use a Queue in Objective-C?-queue

Ben's version is a stack instead of a queue, so 4 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 3 wherever you want to use your new methods, and 2 call them like you would any other NSMutableArray 1 methods.

Good luck and Keep on Coding!

I wouldn't say that using NSMutableArray 39 is necessarily the best solution, particularly 38 if you're adding methods with categories, due 37 to the fragility they can cause if method 36 names collide. For a quick-n-dirty queue, I'd 35 use the methods to add and remove at the 34 end of a mutable array. However, if you 33 plan to reuse the queue, or if you want 32 your code to be more readable and self-evident, a 31 dedicated queue class is probably what you 30 want.

Cocoa doesn't have one built in, but 29 there are other options, and you don't have 28 to write one from scratch either. For a 27 true queue that only adds and removes from 26 the ends, a circular buffer array is an 25 extremely fast implementation. Check out 24 CHDataStructures.framework, a library/framework in Objective-C that 23 I've been working on. It has a variety of 22 implementations of queues, as well as stacks, deques, sorted 21 sets, etc. For your purposes, CHCircularBufferQueue is significantly 20 faster (i.e. provable with benchmarks) and 19 more readable (admittedly subjective) than 18 using an NSMutableArray.

One big advantage 17 of using a native Objective-C class instead 16 of a C++ STL class is that it integrates 15 seamlessly with Cocoa code, and works much 14 better with encode/decode (serialization). It 13 also works perfectly with garbage collection 12 and fast enumeration (both present in 10.5+, but 11 only the latter on iPhone) and you don't 10 have to worry about what is an Objective-C 9 object and what is a C++ object.

Lastly, although 8 NSMutableArray is better than a standard 7 C array when adding and removing from either 6 end, it's also not the fastest solution 5 for a queue. For most applications it is 4 satisfactory, but if you need speed, a circular 3 buffer (or in some cases a linked list optimized 2 to keep cache lines hot) can easily trounce 1 an NSMutableArray.

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

If you're doing this a 6 lot, you might want to create an Objective-C 5 category to extend the functionality of 4 the NSMutableArray class. Categories allow you to dynamically 3 add functions to existing classes (even 2 the ones you don't have the source for) - you 1 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

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

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

re:Wolfcow -- Here is a corrected implementation 1 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;
}

The solutions that use a category on NSMutableArray are 7 not true queues, because NSMutableArray exposes operations 6 that are a superset of queues. For example, you 5 should not be allowed to remove an item 4 from the middle of a queue (as those category 3 solutions still let you do). It is best 2 to encapsulate functionality, a major principle 1 of object oriented design.

StdQueue.h

#import <Foundation/Foundation.h>

@interface StdQueue : NSObject

@property(nonatomic, readonly) BOOL empty;
@property(nonatomic, readonly) NSUInteger size;
@property(nonatomic, readonly) id front;
@property(nonatomic, readonly) id back;

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

@end

StdQueue.m

#import "StdQueue.h"

@interface StdQueue ()

@property(nonatomic, strong) NSMutableArray* storage;

@end

@implementation StdQueue

#pragma mark NSObject

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

#pragma mark StdQueue

- (BOOL)empty
{
    return self.storage.count == 0;
}

- (NSUInteger)size
{
    return self.storage.count;
}

- (id)front
{
    return self.storage.firstObject;
}

- (id)back
{
    return self.storage.lastObject;
}

- (void)enqueue:(id)object
{
    [self.storage addObject:object];
}

- (id)dequeue
{
    id firstObject = nil;
    if (!self.empty) {
        firstObject  = self.storage.firstObject;
        [self.storage removeObjectAtIndex:0];
    }
    return firstObject;
}

@end

this is my implementation, hope it helps.

Is 3 kind of minimalistic, so you must keep the 2 track of the head by saving the new head 1 at pop and discarding the old head

@interface Queue : NSObject {
    id _data;
    Queue *tail;
}

-(id) initWithData:(id) data;
-(id) getData;

-(Queue*) pop;
-(void) push:(id) data;

@end

#import "Queue.h"

@implementation Queue

-(id) initWithData:(id) data {
    if (self=[super init]) {
        _data = data;
        [_data retain];
    }
    return self;
}
-(id) getData {
    return _data;
}

-(Queue*) pop {
    return tail;
}
-(void) push:(id) data{
    if (tail) {
        [tail push:data];
    } else {
        tail = [[Queue alloc]initWithData:data];
    }
}

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

@end

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

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

Use NSMutableArray.

0