Jak utworzyć i używać kolejki w Objective-C?

Chcę użyć struktury danych kolejki w moim programie Objective-C. W C ++ użyłbym kolejki STL. Jaka jest równoważna struktura danych w Objective-C? Jak mogę wypchnąć / wyrzucić przedmioty?

Wersja Bena to stos zamiast kolejki, więc trochę ją poprawiłem:

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

Po prostu zaimportuj plik .h tam, gdzie chcesz użyć nowych metod i wywołaj je tak, jak każdą inną metodę NSMutableArray.

Powodzenia i kontynuuj kodowanie!

Nie powiedziałbym, że używanie NSMutableArray jest koniecznie najlepsze rozwiązaniem, szczególnie jeśli dodajesz metody z kategoriami, ze względu na kruchość, jaką mogą powodować kolizja nazw metod. W przypadku kolejki szybkiego i brudnego użyłbym metod dodawania i usuwania na końcu mutowalnej tablicy. Jeśli jednak planujesz ponowne użycie kolejki lub chcesz, aby kod był bardziej czytelny i zrozumiały, prawdopodobnie potrzebujesz dedykowanej klasy kolejki.

Cocoa nie ma wbudowanego, ale są inne opcje i nie musisz też pisać od zera. W przypadku prawdziwej kolejki, która tylko dodaje i usuwa z końców, cykliczna tablica buforów jest niezwykle szybką implementacją. Sprawdź CHDataStructures.framework , bibliotekę / framework w Objective-C, nad którym pracowałem. Ma wiele implementacji kolejek, a także stosów, deques, posortowanych zestawów itp. Do twoich celów CHCircularBufferQueue jest znacznie szybsze (tj. Możliwe do udowodnienia za pomocą testów porównawczych) i bardziej czytelne (wprawdzie subiektywne) niż użycie NSMutableArray.

Dużą zaletą korzystania z natywnej klasy Objective-C zamiast klasy C ++ STL jest to, że integruje się ona bezproblemowo z kodem Cocoa i działa znacznie lepiej z kodowaniem / dekodowaniem (serializacja). Działa również doskonale ze zbieraniem śmieci i szybkim wyliczaniem (oba obecne w 10.5+, ale tylko w tym drugim na iPhonie) i nie musisz się martwić, co jest obiektem Objective-C, a co obiektem C ++.

Wreszcie, chociaż NSMutableArray jest lepsze niż standardowa tablica C podczas dodawania i usuwania z dowolnego końca, nie jest również najszybszym rozwiązaniem dla kolejki. W przypadku większości aplikacji jest to zadowalające, ale jeśli potrzebujesz szybkości, cykliczny bufor (lub w niektórych przypadkach lista połączona zoptymalizowana pod kątem utrzymywania gorących linii pamięci podręcznej) może z łatwością przebić NSMutableArray.

O ile wiem, Objective-C nie zapewnia struktury danych kolejki. Najlepiej jest utworzyć plik NSMutableArray, a następnie użyć go [array lastObject], [array removeLastObject]aby pobrać przedmiot i [array insertObject:o atIndex:0]...

Jeśli często to robisz, możesz chcieć utworzyć kategorię Cel-C, aby rozszerzyć funkcjonalność NSMutableArrayklasy. Kategorie pozwalają dynamicznie dodawać funkcje do istniejących klas (nawet tych, dla których nie masz źródła) - możesz utworzyć kolejkę w ten sposób:

(UWAGA: ten kod w rzeczywistości dotyczy stosu, a nie kolejki. Zobacz komentarze poniżej)

@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

Nie ma prawdziwej klasy kolekcji kolejek, ale NSMutableArray można skutecznie wykorzystać do tego samego. Jeśli chcesz, możesz zdefiniować kategorię, aby dodać metody pop / push jako wygodę.

Tak, użyj NSMutableArray. NSMutableArray jest faktycznie zaimplementowany jako 2-3 drzewo; zazwyczaj nie musisz zajmować się charakterystyką wydajności dodawania lub usuwania obiektów z NSMutableArray w dowolnych indeksach.

re: Wolfcow - Oto poprawiona implementacja metody dequeue Wolfcowa

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

Rozwiązania, które używają kategorii na, NSMutableArraynie są prawdziwymi kolejkami, ponieważ NSMutableArrayujawniają operacje, które są nadzbiorem kolejek. Na przykład nie powinieneś mieć możliwości usunięcia pozycji ze środka kolejki (ponieważ te rozwiązania kategorii nadal pozwalają). Najlepiej jest hermetyzować funkcjonalność, główną zasadę projektowania obiektowego.

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

to jest moja realizacja, mam nadzieję, że to pomoże.

Jest trochę minimalistyczny, więc musisz śledzić głowę, zapisując nową głowę w popie i odrzucając starą

@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

Czy jest jakiś szczególny powód, dla którego nie możesz po prostu użyć kolejki STL? Objective C ++ jest nadzbiorem języka C ++ (po prostu użyj .mm jako rozszerzenia zamiast .m, aby użyć Objective C ++ zamiast Objective C). Następnie możesz użyć kodu STL lub dowolnego innego kodu C ++.

Jednym z problemów związanych z używaniem kolejki / wektora / listy STL itp. Z obiektami celu C jest to, że zazwyczaj nie obsługują one zarządzania pamięcią typu retain / release / autorelease. Można to łatwo obejść dzięki klasie kontenera C ++ Smart Pointer, która zachowuje swój obiekt Objective C po skonstruowaniu i zwalnia go po zniszczeniu. W zależności od tego, co umieszczasz w kolejce STL, często nie jest to konieczne.

Użyj NSMutableArray.