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

Question

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

Answer 1

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

NSmutableArray+QueueAdditions.h

@interface NSMutableArray (QueueAdditions)
- (id) dequeue;
- (void) enqueue:(id)obj;
@end

Нсмутаблеаррай+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] для получения элемента и [массив 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.