Comment créer et utiliser une queue dans Objective-C?

Je souhaite utiliser une structure de données de queue dans mon programme Objective-C. En C ++, j’utiliserais la queue STL. Quelle est la structure de données équivalente dans Objective-C? Comment est-ce que je pousse / pop les articles?

La version de Ben est une stack plutôt qu’une queue, donc je l’ai un peu modifiée:

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 

Importez simplement le fichier .h où vous voulez utiliser vos nouvelles méthodes, et appelez-les comme vous le feriez pour toute autre méthode NSMutableArray.

Bonne chance et continuez à coder!

Je ne dirais pas que l’utilisation de NSMutableArray est nécessairement la meilleure solution, surtout si vous ajoutez des méthodes avec des catégories, en raison de la fragilité qu’elles peuvent causer si des noms de méthodes entrent en collision. Pour une queue quick-n-dirty, j’utiliserais les méthodes pour append et supprimer à la fin d’un tableau mutable. Cependant, si vous prévoyez de réutiliser la queue ou si vous souhaitez que votre code soit plus lisible et plus clair, une classe de queue dédiée est probablement ce que vous voulez.

Cocoa n’en a pas un, mais il y a d’autres options, et vous n’avez pas à en écrire une à partir de rien non plus. Pour une véritable queue qui ajoute et supprime uniquement les extrémités, une masortingce de tampons circulaire est une implémentation extrêmement rapide. Découvrez CHDataStructures.framework , une bibliothèque / framework dans Objective-C sur lequel je travaille. Il a une variété d’implémentations de files d’attente, ainsi que des stacks, des deques, des ensembles sortingés, etc.

Un grand avantage d’utiliser une classe Objective-C native au lieu d’une classe C ++ C ++ est qu’il s’intègre parfaitement au code Cocoa et fonctionne beaucoup mieux avec l’encodage / décodage (sérialisation). Il fonctionne également parfaitement avec la récupération de place et l’énumération rapide (toutes deux présentes dans 10.5+, mais uniquement sur l’iPhone) et vous n’avez pas à vous soucier d’un object Objective-C et d’un object C ++.

Enfin, bien que NSMutableArray soit meilleur qu’un tableau C standard lors de l’ajout et de la suppression d’une extrémité, ce n’est pas non plus la solution la plus rapide pour une queue. Pour la plupart des applications, il est satisfaisant, mais si vous avez besoin de rapidité, un tampon circulaire (ou, dans certains cas, une liste chaînée optimisée pour conserver les lignes de cache à chaud) peut facilement lancer un object NSMutableArray.

À ma connaissance, Objective-C ne fournit pas de structure de données de queue. Votre meilleur pari est de créer un NSMutableArray , puis d’utiliser [array lastObject] , [array removeLastObject] pour récupérer l’élément, et [array insertObject:o atIndex:0]

Si vous faites cela beaucoup, vous pouvez créer une catégorie Objective-C pour étendre les fonctionnalités de la classe NSMutableArray . Les catégories vous permettent d’append dynamicment des fonctions aux classes existantes (même celles pour lesquelles vous n’avez pas la source) – vous pouvez créer une queue comme celle-ci:

(NOTE: Ce code est en fait pour une stack, pas une queue. Voir les commentaires ci-dessous)

 @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 

Il n’y a pas de véritable classe de collections de files d’attente, mais NSMutableArray peut être utilisé pour la même chose. Vous pouvez définir une catégorie pour append des méthodes pop / push si vous le souhaitez.

Oui, utilisez NSMutableArray. NSMutableArray est réellement implémenté en tant qu’arborescence 2-3; vous n’avez généralement pas besoin de vous préoccuper des caractéristiques de performances de l’ajout ou de la suppression d’objects de NSMutableArray à des indices arbitraires.

re: Wolfcow – Voici une implémentation corrigée de la méthode de dequeue de Wolfcow

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

Les solutions qui utilisent une catégorie sur NSMutableArray ne sont pas de véritables files d’attente, car NSMutableArray expose les opérations qui constituent un sur-ensemble de files d’attente. Par exemple, vous ne devriez pas être autorisé à supprimer un élément au milieu d’une queue (car ces solutions de catégorie vous permettent toujours de le faire). Il est préférable d’encapsuler les fonctionnalités, un principe majeur de la conception orientée object.

StdQueue.h

 #import  @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 

C’est ma mise en œuvre, j’espère que ça aide.

Est un peu minimaliste, donc vous devez garder la trace de la tête en sauvegardant la nouvelle tête au pop et en rejetant l’ancienne tête

 @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 

Utilisez NSMutableArray.

Y a-t-il une raison particulière pour laquelle vous ne pouvez pas simplement utiliser la queue STL? Objectif C ++ est un sur-ensemble de C ++ (utilisez simplement .mm comme extension au lieu de .m pour utiliser Objective C ++ au lieu d’Objective C). Ensuite, vous pouvez utiliser la STL ou tout autre code C ++.

Un problème lié à l’utilisation de la queue / vecteur / liste, etc. de la STL avec les objects Objective C est qu’ils ne prennent généralement pas en charge la gestion de la mémoire de restauration / libération / autorelease. Ceci est facilement contournable avec une classe de conteneur C ++ Smart Pointer qui conserve son object Objective C lors de sa construction et la libère lorsqu’elle est détruite. En fonction de ce que vous placez dans la queue STL, cela n’est souvent pas nécessaire.