107

Objective-C プログラムでキュー データ構造を使用したいと考えています。C++ では、STL キューを使用します。Objective-C の同等のデータ構造は何ですか? アイテムをプッシュ/ポップするにはどうすればよいですか?

4

10 に答える 10

155

Ben のバージョンはキューではなくスタックなので、少し調整しました。

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 メソッドと同じように呼び出すだけです。

頑張ってコーディングを続けてください！

于 2009-06-01T20:03:30.247 に答える
33

NSMutableArray を使用することが必ずしも最良の解決策であるとは言えません。特に、メソッド名が衝突した場合に発生する可能性がある脆弱性のため、カテゴリを使用してメソッドを追加する場合はそうです。クイック アンド ダーティ キューの場合、メソッドを使用して可変配列の末尾に追加および削除します。ただし、キューを再利用する予定がある場合、またはコードをより読みやすく自明なものにしたい場合は、おそらく専用のキュー クラスが必要です。

Cocoa には組み込みのオプションはありませんが、他にもオプションがあり、最初から作成する必要もありません。端から追加および削除するだけの真のキューの場合、循環バッファー配列は非常に高速な実装です。私が取り組んでいる Objective-C のライブラリ/フレームワークであるCHDataStructures.frameworkを確認してください。スタック、デキュー、ソートされたセットなどと同様に、キューのさまざまな実装があります。あなたの目的のために、CHCircularBufferQueueはNSMutableArrayを使用するよりもはるかに高速であり（つまり、ベンチマークで証明可能です）、読みやすくなっています（確かに主観的です）。

C++ STL クラスの代わりにネイティブの Objective-C クラスを使用する大きな利点の 1 つは、Cocoa コードとシームレスに統合され、エンコード/デコード (シリアライゼーション) でより適切に機能することです。また、ガベージ コレクションと高速列挙 (どちらも 10.5 以降に存在しますが、iPhone では後者のみ) と完全に連携し、Objective-C オブジェクトとは何か、C++ オブジェクトとは何かを心配する必要はありません。

最後に、NSMutableArray は、どちらかの端から追加および削除する場合、標準の C 配列よりも優れていますが、キューの最速のソリューションでもありません。ほとんどのアプリケーションではこれで十分ですが、速度が必要な場合は、循環バッファー (場合によっては、キャッシュ ラインをホットに保つために最適化されたリンク リスト) を使用すると、NSMutableArray を簡単に打ち負かすことができます。

于 2009-06-10T05:06:20.337 に答える
29

私の知る限り、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
于 2009-05-03T17:07:08.177 に答える
8

実際のキュー コレクション クラスはありませんが、NSMutableArray を効果的に同じ目的で使用できます。必要に応じて、カテゴリを定義してpop/push メソッドを便利に追加できます。

于 2009-05-03T17:03:04.893 に答える
7

はい、NSMutableArray を使用します。NSMutableArray は実際には2-3 ツリーとして実装されています。通常、任意のインデックスで NSMutableArray からオブジェクトを追加または削除する際のパフォーマンス特性について気にする必要はありません。

于 2009-05-06T06:48:50.353 に答える
5

re:Wolfcow -- これは Wolfcow の dequeue メソッドの修正された実装です

- (id)dequeue {
    if ([self count] == 0) {
        return nil;
    }
    id queueObject = [[[self objectAtIndex:0] retain] autorelease];
    [self removeObjectAtIndex:0];
    return queueObject;
}
于 2009-11-10T00:49:22.130 に答える
4

カテゴリを使用するソリューションは、キューのスーパーセットである操作を公開する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
于 2014-07-07T23:59:15.130 に答える
3

これは私の実装です。

ミニマルなので、ポップ時に新しいヘッドを保存し、古いヘッドを破棄して、ヘッドを追跡する必要があります

@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
于 2012-08-30T21:22:18.537 に答える
1

NSMutableArray を使用します。

于 2009-05-03T17:04:30.820 に答える