Как создать и использовать очередь в Objective-C?

Question

Я хочу использовать структуру данных очереди в моей программе Objective-C. В C ++ я бы использовал очередь STL. Какова эквивалентная структура данных в Objective-C? Как пушить / высовывать предметы?

Answer 1

Версия Бена - это стек, а не очередь, поэтому я немного подправил:

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

Просто импортируйте файл .h, где бы вы ни хотели использовать ваши новые методы, и вызывайте их так же, как и любые другие методы NSMutableArray.

Удачи и продолжайте кодировать!

Answer 2

Я бы не сказал, что использование NSMutableArray обязательно является лучшим решением, особенно если вы добавляете методы с категориями из-за хрупкости, которую они могут вызвать, если имена методов сталкиваются. Для быстрой-грязной очереди я бы использовал методы для добавления и удаления в конце изменяемого массива. Однако, если вы планируете повторно использовать очередь или хотите, чтобы ваш код был более читабельным и самоочевидным, вероятно, вам нужен выделенный класс очереди.

Какао не имеет встроенного, но есть и другие варианты, и вам не нужно писать с нуля. Для истинной очереди, которая только добавляет и удаляет с концов, кольцевой буферный массив является чрезвычайно быстрой реализацией. Посмотрите CHDataStructures.framework , библиотеку / фреймворк в Objective-C, над которой я работал. Он имеет множество реализаций очередей, а также стеков, запросов, отсортированных наборов и т. Д. Для ваших целей CHCircularBufferQueue значительно быстрее (то есть доказуемо с помощью тестов) и более читабельно (предположительно субъективно), чем при использовании NSMutableArray.

Одним большим преимуществом использования нативного класса Objective-C вместо класса C ++ STL является то, что он легко интегрируется с кодом Какао и намного лучше работает с кодированием / декодированием (сериализацией). Он также отлично работает с сборкой мусора и быстрым перечислением (оба представлены в 10.5+, но только в последних на iPhone), и вам не нужно беспокоиться о том, что является объектом Objective-C и чем является объектом C ++.

Наконец, хотя NSMutableArray лучше, чем стандартный массив C, при добавлении и удалении с любого конца, это также не самое быстрое решение для очереди. Для большинства приложений это удовлетворительно, но если вам нужна скорость, циклический буфер (или в некоторых случаях связанный список, оптимизированный для поддержания горячих строк кэша) может легко нарушить NSMutableArray.

Answer 3

Насколько я знаю, Objective-C не предоставляет структуру данных Queue. Лучше всего создать NSMutableArray, а затем использовать [array lastObject], [array removeLastObject] для извлечения элемента и [array insertObject:o atIndex:0] ...

Если вы делаете это много, вы можете создать категорию Objective-C, чтобы расширить функциональность класса NSMutableArray. Категории позволяют динамически добавлять функции в существующие классы (даже те, для которых у вас нет источника) - вы можете создать очередь, подобную этой:

(ПРИМЕЧАНИЕ. Этот код фактически предназначен для стека, а не очереди. См. Комментарии ниже)

@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

Реального класса коллекций очередей нет, но NSMutableArray можно эффективно использовать для одной и той же вещи. Вы можете определить категорию , чтобы добавить методы pop / push для удобства, если хотите.

Answer 5

Да, используйте NSMutableArray. NSMutableArray на самом деле реализован как 2-3 дерева; вам обычно не нужно беспокоиться о характеристиках производительности добавления или удаления объектов из NSMutableArray по произвольным индексам.

Answer 6

re: Wolfcow - Вот исправленная реализация метода удаления Wolfcow

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

Answer 7

Решения, использующие категорию в NSMutableArray, не являются истинными очередями, поскольку NSMutableArray предоставляет операции, представляющие собой расширенный набор очередей. Например, вам не должно быть разрешено удалять элемент из середины очереди (так как решения с категориями все еще позволяют это делать). Лучше всего инкапсулировать функциональность, основной принцип объектно-ориентированного проектирования.

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

это моя реализация, надеюсь, это поможет.

Является минималистичным, поэтому вы должны следить за головой, сохраняя новую голову на месте и отбрасывая старую голову

@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

Есть ли какая-то особая причина, по которой вы не можете просто использовать очередь STL? Objective C ++ - это расширенный набор C ++ (просто используйте .mm в качестве расширения вместо .m, чтобы использовать Objective C ++ вместо Objective C). Затем вы можете использовать STL или любой другой код C ++.

Одной из проблем использования очереди / вектора / списка STL и объектов Objective C является то, что они обычно не поддерживают управление сохранением / разблокированием / автоматическим выпуском памяти. Это легко обойти с помощью контейнера C ++ Smart Pointer, который сохраняет свой объект Objective C при создании и освобождает его при уничтожении. В зависимости от того, что вы помещаете в очередь STL, это часто не требуется.

Answer 10

Использовать NSMutableArray.