¿Cómo hago y uso una cola en Objective-C?

Quiero usar una estructura de datos de cola en mi programa Objective-C. En C ++ usaría la cola STL. ¿Cuál es la estructura de datos equivalente en Objective-C? ¿Cómo empujo / saco artículos?

La versión de Ben es una pila en lugar de una cola, así que la modifiqué un poco:

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

Simplemente importe el archivo .h donde desee utilizar sus nuevos métodos y llámelos como lo haría con cualquier otro método NSMutableArray.

¡Buena suerte y sigue codificando!

No diría que usar NSMutableArray es necesariamente la mejor solución, particularmente si está agregando métodos con categorías, debido a la fragilidad que pueden causar si los nombres de los métodos chocan. Para una cola rápida y sucia, usaría los métodos para agregar y eliminar al final de una matriz mutable. Sin embargo, si planea reutilizar la cola, o si desea que su código sea más legible y evidente, probablemente lo que desee sea una clase de cola dedicada.

Cocoa no tiene uno integrado, pero hay otras opciones, y tampoco es necesario que escriba uno desde cero. Para una verdadera cola que solo agrega y quita de los extremos, una matriz de búfer circular es una implementación extremadamente rápida. Consulte CHDataStructures.framework , una biblioteca / marco en Objective-C en el que he estado trabajando. Tiene una variedad de implementaciones de colas, así como pilas, deques, conjuntos ordenados, etc. Para sus propósitos, CHCircularBufferQueue es significativamente más rápido (es decir, demostrable con puntos de referencia) y más legible (ciertamente subjetivo) que usar un NSMutableArray.

Una gran ventaja de usar una clase Objective-C nativa en lugar de una clase STL de C ++ es que se integra perfectamente con el código Cocoa y funciona mucho mejor con codificación / decodificación (serialización). También funciona perfectamente con la recolección de basura y la enumeración rápida (ambos presentes en 10.5+, pero solo el último en iPhone) y no tiene que preocuparse por qué es un objeto Objective-C y qué es un objeto C ++.

Por último, aunque NSMutableArray es mejor que una matriz C estándar al agregar y eliminar desde cualquier extremo, tampoco es la solución más rápida para una cola. Para la mayoría de las aplicaciones es satisfactorio, pero si necesita velocidad, un búfer circular (o en algunos casos una lista enlazada optimizada para mantener activas las líneas de caché) puede derrotar fácilmente un NSMutableArray.

Hasta donde yo sé, Objective-C no proporciona una estructura de datos de cola. Su mejor opción es crear un NSMutableArray, y luego usar [array lastObject], [array removeLastObject]para buscar el artículo y [array insertObject:o atIndex:0]...

Si está haciendo esto mucho, es posible que desee crear una categoría Objective-C para ampliar la funcionalidad de la NSMutableArrayclase. Las categorías le permiten agregar funciones dinámicamente a clases existentes (incluso aquellas para las que no tiene la fuente); podría hacer una cola como esta:

(NOTA: este código es en realidad para una pila, no para una cola. Consulte los comentarios a continuación)

@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

No hay una clase de colecciones de cola real, pero NSMutableArray se puede usar para lo mismo de manera efectiva. Puede definir una categoría para agregar métodos pop / push como una conveniencia si lo desea.

Sí, use NSMutableArray. NSMutableArray se implementa realmente como árbol 2-3; normalmente no es necesario que se preocupe por las características de rendimiento de agregar o eliminar objetos de NSMutableArray en índices arbitrarios.

re: Wolfcow - Aquí hay una implementación corregida del método de eliminación de cola de Wolfcow

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

Las soluciones que usan una categoría en NSMutableArrayno son colas verdaderas, porqueNSMutableArray exponen operaciones que son un superconjunto de colas. Por ejemplo, no se le debería permitir eliminar un elemento de la mitad de una cola (ya que esas soluciones de categoría aún le permiten hacerlo). Es mejor encapsular la funcionalidad, un principio fundamental del diseño orientado a objetos.

StdQueue.h

#import <Foundation/Foundation.h>

@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 es mi implementación, espero que ayude.

Es un poco minimalista, por lo que debes seguir el rastro de la cabeza guardando la nueva cabeza en el momento del estallido y descartando la vieja.

@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

¿Hay alguna razón en particular por la que no puede usar la cola STL? Objective C ++ es un superconjunto de C ++ (solo use .mm como extensión en lugar de .m para usar Objective C ++ en lugar de Objective C). Entonces puede usar el STL o cualquier otro código C ++.

Un problema del uso de la cola / vector / lista STL, etc. con objetos Objective C es que normalmente no admiten la gestión de memoria de retención / liberación / liberación automática. Esto se soluciona fácilmente con una clase contenedora C ++ Smart Pointer que retiene su objeto Objective C cuando se construye y lo libera cuando se destruye. Dependiendo de lo que esté poniendo en la cola STL, esto a menudo no es necesario.

Utilice NSMutableArray.