Есть ли структура данных очереди/FIFO для iPhone?

Question

Прежде чем я скачу свой собственный Очередь с использованием NSMutableArray, я хотел бы знать, есть ли что-то более стандартное. Я ничего не вижу в документах Apple, но я буду удивлен, если не будет реализации Queue от того, что люди используют. Java портит меня!

Answer 1

Реализация очереди на основе NSMutableArray довольно проста, это, вероятно, менее 50 строк кода.

EDIT:

Нашел с быстрым поиском Google:

@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

сам по себе какао не имеет класс Queue, и это не стандарт сам по себе, но есть несколько вариантов, один которые могут наилучшим образом соответствовать вашим потребностям. См. this question (и my answer).

Как вы сказали, вы можете катить свой собственный, используя NSMutableArray. Если вам просто нужна быстрая 'грязная очередь (и не беспокоится о копировании, кодировании/декодировании, перечислении и т. Д.), То решение @Matt предлагает простой подход. Вы также должны рассмотреть adding queue methods to NSMutableArray via a category, что приятно в том, что ваша «очередь» также является массивом (чтобы вы могли передавать его для параметров NSArray), и вы бесплатно получаете всю функциональность NS (Mutable) Array.

Если производительность важна, я рекомендую использовать конструкцию, более подходящую для удаления первого элемента. Именно поэтому я написал CHCircularBufferQueue для своей собственной структуры. (Не пытайтесь использовать собственный рог, просто пытаясь сэкономить время на некоторое время.)

Answer 3

Я создал категорию, содержащую только метод deque, основанный на коде Мэтта Бриджеса.

@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

Вы можете использовать STL-очередь из стандартной библиотеки C++.

Answer 5

Проверьте STL priority queue. Он требует нулевых строк кода и переносится! Чего еще можно хотеть?

Answer 6

Вы можете использовать метод lastObject для NSArray. Вот непроверенный пример:

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