2.21
Stack and Queue extensions to NSMutableArray
This is all out there on the web, but I’m putting everything here all in one place so as not to forget. Just a simple Stack and Queue implementation as a category on NSMutableArray
. It works and it doesn’t suck, and that’s all I’ll say about it.
Stack
A very basic Stack implementation with just push
, pop
, and peek
.
@interface NSMutableArray (Stack) - (void) push: (id)item; - (id) pop; - (id) peek; @end
@implementation NSMutableArray (Stack) - (void) push: (id)item { [self addObject:item]; } - (id) pop { id item = nil; if ([self count] != 0) { item = [[[self lastObject] retain] autorelease]; [self removeLastObject]; } return item; } - (id) peek { id item = nil; if ([self count] != 0) { item = [[[self lastObject] retain] autorelease]; } return item; } @end
No real magic above, just Objective-C’s annoying retain
& autorelease
dance to get an item out of NSMutableArray
correctly.
Queue
Much like Stack above, here’s a very basic Queue implementation with just enqueue
, dequeue
, and peek
.
@interface NSMutableArray (Queue) - (void) enqueue: (id)item; - (id) dequeue; - (id) peek; @end
@implementation NSMutableArray (Queue) - (void) enqueue: (id)item { [self addObject:item]; } - (id) dequeue { id item = nil; if ([self count] != 0) { item = [[[self objectAtIndex:0] retain] autorelease]; [self removeObjectAtIndex:0]; } return item; } - (id) peek { id item = nil; if ([self count] != 0) { item = [[[self objectAtIndex:0] retain] autorelease]; } return item; } @end
Note that we need the same retain
& autorelease
dance as above.
michelle
2.18.2012
Thanks for this! I’ve been trying to figure this out all morning.
Chet Harrison
4.25.2012
So how do you alloc and init the array?
Luca
5.6.2012
The dance retain autorelease is totally redundant and gives rise to an absurd code, like the one above.
[self lastObject] is already an autoreleased object.
Luca
5.6.2012
Sorry, it is justified in this case. removeObject decreases the retain count and cause an anticipated release of the object. It’s fine.
Luca
5.6.2012
But in peek method: item = [[[self objectAtIndex:0] retain] autorelease];
is wrong. it is sufficient:[self objectAtIndex:0]
Daniel Skinner
9.23.2012
Thanks, this is a nice tidy extension that was exactly what I needed.
Assad Khan
2.10.2013
Luca is right
There is no need for retain autorelease in peek.
Assad Khan
2.10.2013
And rather than writing a category on NSMutableArray create a class yourself and use composition rather than inheritance or categories.