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

Question

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 / hago estallar elementos?

Answer 1

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 quiera usar sus nuevos métodos, y llámelos como lo haría con cualquier otro método NSMutableArray.

¡Buena suerte y siga codificando!

Answer 2

No diría que el uso de NSMutableArray es necesariamente la mejor solución , especialmente si agrega 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, lo más probable es que desee una clase de cola dedicada.

Cocoa no tiene uno incorporado, pero hay otras opciones, y tampoco tiene que escribir uno desde cero. Para una cola real que solo agrega y elimina de los extremos, una matriz de búfer circular es una implementación extremadamente rápida. Vea CHDataStructures.framework , una biblioteca / marco en Objective-C en el que he estado trabajando . Tiene una variedad de implementaciones de colas, así como pilas, calcas, 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 (aunque sea subjetivo) que usar un NSMutableArray.

Una gran ventaja de usar una clase nativa de Objective-C en lugar de una clase C ++ STL es que se integra perfectamente con el código Cocoa y funciona mucho mejor con la codificación / decodificación (serialización). También funciona perfectamente con la recolección de basura y la enumeración rápida (ambas presentes en 10.5+, pero solo la última en el iPhone) y no tiene que preocuparse por lo que es un objeto Objective-C y lo que 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 las líneas de caché en funcionamiento) puede desbaratar fácilmente un NSMutableArray.

Answer 3

Por lo que 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 clase NSMutableArray . Las categorías le permiten agregar funciones dinámicamente a las 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 una cola. Ver 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

Answer 4

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

Answer 5

Sí, use NSMutableArray. NSMutableArray es en realidad implementado como un árbol 2-3 ; normalmente no necesita preocuparse por las características de rendimiento de agregar o quitar objetos de NSMutableArray en índices arbitrarios.

Answer 6

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

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

Answer 7

Las soluciones que usan una categoría en NSMutableArray no son colas verdaderas, porque NSMutableArray expone operaciones que son un superconjunto de colas. Por ejemplo, no se le debe permitir eliminar un elemento de la mitad de una cola (ya que las 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

Answer 8

esta es mi implementación, espero que ayude.

Es un poco minimalista, por lo que debes mantener el rastro de la cabeza guardando la nueva cabeza en el pop y descartando la antigua cabeza

@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

Answer 9

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

Un problema de usar la cola / vector / lista STL, etc. con objetos de Objective C es que, por lo general, no son compatibles con la administración de memoria de retener / liberar / liberar automáticamente. Esto se soluciona fácilmente con una clase de contenedor de puntero inteligente C ++ que retiene su objeto Objetivo C cuando se construye y lo libera cuando se destruye. Dependiendo de lo que coloque en la cola STL, esto no suele ser necesario.

Answer 10

Utilice NSMutableArray.