Como faço e uso uma fila em Objective-C?

Eu quero usar uma estrutura de dados de fila no meu programa Objective-C. Em C ++ eu usaria a fila STL. Qual é a estrutura de dados equivalente no Objective-C? Como faço para empurrar / pop itens?

A versão de Ben é uma pilha em vez de uma fila, então eu ajustei um pouco:

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 

Basta importar o arquivo .h para onde quiser usar seus novos methods e chamá-los como faria com qualquer outro método NSMutableArray.

Boa sorte e continue codificando!

Eu não diria que usar o NSMutableArray é necessariamente a melhor solução, particularmente se você estiver adicionando methods com categorias, devido à fragilidade que eles podem causar se os nomes dos methods colidirem. Para uma fila rápida, eu usaria os methods para adicionar e remover no final de uma matriz mutável. No entanto, se você planeja reutilizar a fila ou se quiser que seu código seja mais legível e óbvio, uma class de fila dedicada provavelmente é o que você deseja.

cocoa não tem um construído em, mas há outras opções, e você não tem que escrever um a partir do zero também. Para uma fila real que apenas adiciona e remove das extremidades, uma matriz de buffer circular é uma implementação extremamente rápida. Confira CHDataStructures.framework , uma biblioteca / framework em Objective-C que eu tenho trabalhado. Ele tem uma variedade de implementações de filas, assim como pilhas, deques, conjuntos de sorting, etc. Para seus propósitos, o CHCircularBufferQueue é significativamente mais rápido (isto é, provável com benchmarks) e mais legível (reconhecidamente subjetivo) do que usar um NSMutableArray.

Uma grande vantagem de usar uma class Objective-C nativa em vez de uma class STL em C ++ é que ela se integra perfeitamente ao código Cocoa e funciona muito melhor com codificação / decodificação (serialização). Ele também funciona perfeitamente com garbage collection e enumeração rápida (ambos presentes em 10.5+, mas apenas o último no iPhone) e você não precisa se preocupar com o que é um object Objective-C e o que é um object C ++.

Por fim, embora o NSMutableArray seja melhor que uma matriz C padrão ao adicionar e remover de qualquer uma das extremidades, ele também não é a solução mais rápida para uma fila. Para a maioria das aplicações é satisfatório, mas se você precisar de velocidade, um buffer circular (ou, em alguns casos, uma lista encadeada otimizada para manter as linhas de cache quentes) pode facilmente atrapalhar um NSMutableArray.

Tanto quanto eu sei, Objective-C não fornece uma estrutura de dados de fila. Sua melhor aposta é criar um NSMutableArray e, em seguida, usar [array lastObject] , [array removeLastObject] para buscar o item e [array insertObject:o atIndex:0]

Se você estiver fazendo muito isso, talvez queira criar uma categoria Objective-C para estender a funcionalidade da class NSMutableArray . As categorias permitem que você adicione dinamicamente funções a classs existentes (mesmo aquelas para as quais você não tem a fonte) – você poderia criar uma fila assim:

(NOTA: Este código é na verdade para uma pilha, não uma fila. Veja os comentários abaixo)

 @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 

Não existe uma class real de collections de filas, mas o NSMutableArray pode ser usado efetivamente para a mesma coisa. Você pode definir uma categoria para adicionar methods pop / push como uma conveniência, se desejar.

Sim, use NSMutableArray. NSMutableArray é realmente implementado como tree 2-3; você normalmente não precisa se preocupar com as características de desempenho de adicionar ou remover objects do NSMutableArray em índices arbitrários.

re: Wolfcow – Aqui está uma implementação corrigida do método de dequeue de Wolfcow

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

As soluções que usam uma categoria no NSMutableArray não são filas verdadeiras, porque o NSMutableArray expõe operações que são um superconjunto de filas. Por exemplo, você não deve ter permissão para remover um item do meio de uma fila (como essas soluções de categoria ainda permitem). É melhor encapsular a funcionalidade, um princípio importante do design orientado a objects.

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 

esta é minha implementação, espero que ajude.

É meio minimalista, então você deve manter o controle da cabeça salvando a nova cabeça no pop e descartando a cabeça antiga

 @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 

Use NSMutableArray.

Existe alguma razão específica pela qual você não pode simplesmente usar a fila STL? Objective C ++ é um superconjunto de C ++ (apenas use .mm como a extensão em vez de .m para usar Objective C ++ em vez de Objective C). Então você pode usar o STL ou qualquer outro código C ++.

Uma questão de usar a fila / vetor / lista STL, etc, com objects Objective C é que eles normalmente não suportam o gerenciamento de memory de retenção / liberação / autorelease. Isso é facilmente contornado com uma class de contêiner C ++ Smart Pointer que retém seu object Objective C quando construído e o libera quando destruído. Dependendo do que você está colocando na fila STL, isso geralmente não é necessário.