Esiste una struttura dati Queue/FIFO per l'iPhone?

Question

Prima di stampare la mia coda utilizzando NSMutableArray, mi piacerebbe sapere se c'è qualcosa di più disponibile. Non vedo nulla nei documenti Apple, ma sarei sorpreso se non ci fosse un'implementazione di Queue da qualche parte che la gente sta usando. Java mi vizia!

Answer 1

L'implementazione di una coda basata su NSMutableArray è piuttosto semplice, è probabilmente inferiore a 50 righe di codice.

EDIT:

Abbiamo trovato questo con una breve ricerca su 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

cacao sé non ha una classe di coda, e non c'è uno standard di per sé, ma ci sono diverse opzioni, una di cui potrebbe essere più adatto alle tue esigenze. Vedere this question (e my answer).

Come hai detto, puoi eseguire il rollover utilizzando NSMutableArray. Se hai solo bisogno di una coda rapida (e non sei preoccupato di copiare, codificare/decodificare, enumerare, ecc.) Allora la soluzione @Matt suggerisce è un approccio facile. Dovresti considerare anche adding queue methods to NSMutableArray via a category, il che è bello in quanto la tua "coda" è anche un array (quindi puoi passarlo per i parametri NSArray), e ottieni tutte le funzionalità della NS (Mutevole) Array gratuitamente.

Se le prestazioni sono importanti, si consiglia di utilizzare una struttura più idonea per la rimozione del primo elemento. Ho scritto CHCircularBufferQueue per il mio framework proprio per questo motivo. (Non sto cercando di fregare il mio corno, solo cercando di salvare gli altri un po 'di tempo.)

Answer 3

Ho creato una categoria contenente solo il metodo deque, basato sul codice di Matt Bridges.

@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

È possibile utilizzare la coda STL dalla libreria standard C++.

Answer 5

Controlla il STL priority queue. Richiede zero linee di codice ed è portatile! Cosa si può volere di più?

Answer 6

È possibile utilizzare il metodo lastObject di NSArray. Ecco un esempio non testata:

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