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

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

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

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.

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

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

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

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

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

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

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

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

 @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 

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

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

re: Wolfcow – Здесь скорректированная реализация метода вторжения Вольфкова

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

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

StdQueue.h

 #import  @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 

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

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

 @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 

Используйте NSMutableArray.

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

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

Давайте будем гением компьютера.