Bagaimana cara membuat dan menggunakan Antrian di Objective-C?

Saya ingin menggunakan struktur data antrian dalam program Objective-C saya. Di C ++ saya akan menggunakan antrian STL. Apa struktur data ekuivalen di Objective-C? Bagaimana cara mendorong / meletuskan item?

Versi Ben adalah tumpukan, bukan antrian, jadi saya mengubahnya sedikit:

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

Cukup impor file .h di mana pun Anda ingin menggunakan metode baru Anda, dan panggil mereka seperti yang Anda lakukan pada metode NSMutableArray lainnya.

Semoga berhasil dan Terus Coding!

Saya tidak akan mengatakan bahwa menggunakan NSMutableArray tentu merupakan solusi terbaik , terutama jika Anda menambahkan metode dengan kategori, karena kerapuhan yang dapat mereka sebabkan jika nama metode bertabrakan. Untuk antrian quick-n-dirty, saya akan menggunakan metode untuk menambah dan menghapus di akhir array yang bisa berubah. Namun, jika Anda berencana untuk menggunakan kembali antrian, atau jika Anda ingin kode Anda lebih mudah dibaca dan jelas, kelas antrian khusus mungkin yang Anda inginkan.

Kakao tidak memiliki satu bawaan, tetapi ada opsi lain, dan Anda juga tidak perlu membuatnya dari awal. Untuk antrian benar yang hanya menambah dan menghapus dari ujung, array buffer melingkar adalah implementasi yang sangat cepat. Lihat CHDataStructures.framework , perpustakaan / kerangka kerja di Objective-C yang sedang saya kerjakan. Ini memiliki berbagai implementasi antrian, serta tumpukan, deques, set yang diurutkan, dll. Untuk tujuan Anda, CHCircularBufferQueue secara signifikan lebih cepat (yaitu dapat dibuktikan dengan tolok ukur) dan lebih mudah dibaca (diakui subjektif) daripada menggunakan NSMutableArray.

Satu keuntungan besar menggunakan kelas Objective-C asli daripada kelas C ++ STL adalah ia terintegrasi secara mulus dengan kode Cocoa, dan bekerja jauh lebih baik dengan encode / decode (serialisasi). Ini juga berfungsi sempurna dengan pengumpulan sampah dan pencacahan cepat (keduanya ada di 10.5+, tetapi hanya yang terakhir di iPhone) dan Anda tidak perlu khawatir tentang apa itu objek Objective-C dan apa itu objek C ++.

Terakhir, meskipun NSMutableArray lebih baik daripada array C standar saat menambahkan dan menghapus dari kedua ujung, ini juga bukan solusi tercepat untuk antrian. Untuk sebagian besar aplikasi, ini memuaskan, tetapi jika Anda membutuhkan kecepatan, buffer melingkar (atau dalam beberapa kasus daftar tertaut yang dioptimalkan untuk menjaga agar baris cache tetap panas) dapat dengan mudah merusak NSMutableArray.

Sejauh yang saya tahu, Objective-C tidak menyediakan struktur data Antrian. Taruhan terbaik Anda adalah membuat NSMutableArray, dan kemudian menggunakan [array lastObject], [array removeLastObject]untuk mengambil item, dan [array insertObject:o atIndex:0]...

Jika Anda sering melakukan ini, Anda mungkin ingin membuat kategori Objective-C untuk memperluas fungsionalitas NSMutableArraykelas. Kategori memungkinkan Anda untuk menambahkan fungsi secara dinamis ke kelas yang ada (bahkan yang tidak Anda miliki sumbernya) - Anda dapat membuat antrean seperti ini:

(CATATAN: Kode ini sebenarnya untuk tumpukan, bukan antrian. Lihat komentar di bawah)

@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

Tidak ada kelas koleksi antrian yang sebenarnya, tetapi NSMutableArray dapat digunakan secara efektif untuk hal yang sama. Anda dapat menentukan kategori untuk menambahkan metode pop / push sebagai kemudahan jika Anda mau.

Ya, gunakan NSMutableArray. NSMutableArray sebenarnya diimplementasikan sebagai 2-3 pohon; Anda biasanya tidak perlu menyibukkan diri dengan karakteristik kinerja penambahan atau penghapusan objek dari NSMutableArray pada indeks arbitrer.

re: Wolfcow - Berikut adalah implementasi yang diperbaiki dari metode dequeue Wolfcow

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

Solusi yang menggunakan kategori pada NSMutableArrayantrian tidak benar, karenaNSMutableArray mengekspos operasi yang merupakan superset antrian. Misalnya, Anda tidak boleh menghapus item dari tengah antrian (karena solusi kategori tersebut masih memungkinkan Anda melakukannya). Yang terbaik adalah merangkum fungsionalitas, prinsip utama desain berorientasi objek.

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

ini adalah implementasi saya, semoga membantu.

Agak minimalis, jadi Anda harus tetap melacak kepala dengan menyimpan kepala baru di pop dan membuang kepala lama

@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

Apakah ada alasan tertentu mengapa Anda tidak dapat menggunakan antrian STL begitu saja? Objective C ++ adalah superset dari C ++ (cukup gunakan .mm sebagai ekstensi, bukan .m untuk menggunakan Objective C ++, bukan Objective C). Kemudian Anda dapat menggunakan STL atau kode C ++ lainnya.

Satu masalah menggunakan antrian STL / vektor / daftar dll dengan objek Objective C adalah bahwa mereka biasanya tidak mendukung manajemen memori retensi / rilis / rilis otomatis. Ini mudah dikerjakan dengan kelas kontainer C ++ Smart Pointer yang mempertahankan objek Objective C-nya saat dibangun dan melepaskannya saat dihancurkan. Tergantung pada apa yang Anda masukkan ke dalam antrian STL ini seringkali tidak diperlukan.

Gunakan NSMutableArray.