問題：
給你一個嵌套的 NSArray 數(shù)據(jù)，實現(xiàn)一個迭代器類瑰抵，該類提供一個 next() 方法，可以依次的取出這個 NSArray 中的數(shù)據(jù)。
比如 NSArray 如果是 [1,[4,3],6,[5,[1,0]]]局荚， 則最終應該輸出：1, 4, 3, 6, 5, 1, 0 。
另外愈污，實現(xiàn)一個 allObjects 方法耀态，可以一次性取出所有元素。
給你一個嵌套的 NSArray 數(shù)據(jù)暂雹，實現(xiàn)一個迭代器類首装，該類提供一個 next() 方法，可以依次的取出這個 NSArray 中的數(shù)據(jù)杭跪。
解答：
本題的代碼稍長仙逻，完整的代碼我放在git上了，以下是講解涧尿。
先說第二問吧系奉，第二問比較簡單：實現(xiàn)一個 allObjects 方法，可以一次性取出所有元素姑廉。
對于此問缺亮，我們可以實現(xiàn)一個遞歸函數(shù)，在函數(shù)中判斷數(shù)組中的元素是否又是數(shù)組桥言，如果是的話瞬内，就遞歸調(diào)用自己迷雪，如果不是數(shù)組，則加入到一個 NSMutableArray 中即可虫蝶。下面是示例代碼：
- (NSArray*)allObjects {NSMutableArray*result= [NSMutableArrayarray];
[self fillArray:_originArray into:result];returnresult;
}
- (void)fillArray:(NSArray*)arrayinto:(NSMutableArray*)result{for(NSUIntegeri =0; i
[self fillArray:array[i] into:result];
}else{
[resultaddObject:array[i]];
}
}
}
如果你還在糾結(jié)掌握遞歸有什么意義的話章咧，歡迎翻翻我半年前寫的另一篇文章：遞歸的故事（上），遞歸的故事（下）能真。
接下來讓我們來看第一問赁严，在同學的回復中，我看到很多人用第二問的辦法粉铐，把數(shù)組整個另外保存一份疼约，然后再記錄一個下標，每次返回其中一個蝙泼。這個方法當然是可行的程剥，但是大部分的迭代器通常都不會這么實現(xiàn)。因為這么實現(xiàn)的話汤踏，數(shù)組需要整個復制一遍织鲸，空間復雜度是 O(N)。
所以溪胶，我個人認為本題第一問更好的解法是：
記錄下遍歷的位置搂擦，然后每次遍歷時更新位置。由于本題中元素是一個嵌套數(shù)組哗脖，所以我們?yōu)榱擞涗浵挛恢闷偬撸托枰獌蓚€變量：一個是當前正在遍歷的子數(shù)組，另一個是這個數(shù)組遍歷到的位置才避。
我在實現(xiàn)的時候橱夭，定義了一個名為 NSArrayIteratorCursor 的類來記錄這些內(nèi)容，NSArrayIteratorCursor 的定義和實現(xiàn)如下：
@interface ? NSArrayIteratorCursor:NSObject
@property(nonatomic)NSArray*array;
@property(nonatomic)NSUIntegerindex;
@end
@implementation ?NSArrayIteratorCursor
- (id)initWithArray:(NSArray*)array?
{self= [superinit];
if(self) {
_array = array;
_index =0;
}
return ?self;
}
@end
由于數(shù)組在遍歷的時候可能產(chǎn)生遞歸桑逝，就像我們實現(xiàn) allObjects 方法那樣徘钥。所以我們需要處理遞歸時的 NSArrayIteratorCursor 的保存，我在實現(xiàn)的時候肢娘，拿數(shù)組當作棧呈础，來實現(xiàn)保存遍歷時的狀態(tài)。
最終橱健，我實現(xiàn)了一個迭代器類而钞，名字叫 NSArrayIterator，用于最終提供 next 方法的實現(xiàn)拘荡。這個類有兩個私有變量臼节，一個是剛剛說的那個棧，另一個是原數(shù)組的引用。
@interface ?NSArrayIterator:NSObject
- (id)initWithArray:(NSArray*)array;
- (id)next;
- (NSArray*)allObjects;
@end
@implementation NSArrayIterator
{NSMutableArray*_stack;
NSArray*_originArray;
}
在初使化的時候网缝，我們初始化遍歷位置的代碼如下：
- (id)initWithArray:(NSArray*)array?{
self= [super init];
if(self) {? ? ? ?
?_originArray = array;? ? ? ?
?_stack = [NSMutableArray ?array];? ? ?
? [self ?setupStack];??
? }
return ?self;
}
- (void)setupStack?{
NSArray ?IteratorCursor*c = [[NSArray IteratorCursoralloc] initWithArray:_originArray];?
? [_stack addObject:c];
}
接下來就是最關(guān)鍵的代碼了巨税，即實現(xiàn) next 方法，在 next 方法的實現(xiàn)邏輯中粉臊，我們需要：
判斷棧是否為空草添，如果為空則返回 nil。
從棧中取出元素扼仲，看是否遍歷到了結(jié)尾远寸，如果是的話，則出棧屠凶。
判斷第 2 步是否使棧為空驰后，如果為空，則返回 nil矗愧。
終于拿到元素了灶芝，這一步判斷拿到的元素是否是數(shù)組。
如果是數(shù)組唉韭，則重新生成一個遍歷的 NSArrayIteratorCursor 對象夜涕，放到棧中。
重新從棧中拿出第一個元素纽哥，循環(huán)回到第 4 步的判斷钠乏。
如果到了這一步栖秕，說明拿到了一個非數(shù)組的元素春塌，這樣就可以把元素返回，同時更新索引到下一個位置簇捍。
以下是相關(guān)的代碼只壳，對于沒有算法基礎(chǔ)的同學，可能讀起來還是比較累暑塑，其實我寫起來也不快吼句，所以希望你能多理解一下，其實核心思想就是手工操作棧的入棧和出棧：
- (id)next {
//? 1. 判斷棧是否為空事格，如果為空則返回 nil惕艳。
if([_stackcount] ==0)?{
return nil;
}
// 2. 從棧中取出元素，看是否遍歷到了結(jié)尾驹愚，如果是的話远搪，則出棧。
NSArray IteratorCursor*c;
c= [_stack lastObject];
while(c.index ==c.array.count&& _stack.count>0) {
[_stack removeLastObject];
c= [_stack lastObject];
}
// 3. 判斷第 2 步是否使棧為空逢捺，如果為空谁鳍，則返回 nil。
if(_stack.count==0) {
returnnil;
}
// 4. 終于拿到元素了，這一步判斷拿到的元素是否是數(shù)組倘潜。
id item =c.array[c.index];
while([item isKindOfClass:[NSArrayclass]]){
c.index++;
// 5. 如果是數(shù)組绷柒，則重新生成一個遍歷的 NSArrayIteratorCursor 對象，放到棧中涮因。
NSArrayIteratorCursor *nc = [[NSArrayIteratorCursor alloc] initWithArray:item];
[_stack addObject:nc];
// 6. 重新從棧中拿出第一個元素废睦，循環(huán)回到第 4 步的判斷。c= nc;
item =c.array[c.index];
}
// 7. 如果到了這一步蕊退，說明拿到了一個非數(shù)組的元素郊楣，這樣就可以把元素返回，同時更新索引到下一個位置瓤荔。
c.index++;returnitem;
}
在讀者回復中净蚤，聽榆大叔 和 yiplee 同學用了類似的做法，他們的代碼在：
最終今瀑，我想說這個只是我個人想出來的解法，很可能不是最優(yōu)的点把，甚至可能也有很多問題橘荠，比如，這個代碼有很多可以進一步 challenge 的地方：
這個代碼是線程安全的嗎郎逃？如果我們要實現(xiàn)一個線程安全的迭代器哥童，應該怎么做？
如果在使用迭代器的時候褒翰，數(shù)組被修改了贮懈，會怎么樣？
如何檢測在遍歷元素的時候优训，數(shù)組被修改了朵你？
如何避免在遍歷元素的時候，數(shù)組被修改揣非？
如果大家有想出更好的解法抡医，歡迎留言告訴我。
