约瑟夫问题-队列

如果说我比别人看得更远些,那是因为我站在了巨人的肩上。
---牛顿

先前是用数组解决的，很不容易看懂！两层循环、位置 和 删除很迷糊！

现在站在队列的肩上来看！

创建队列，没有移除的数据放到队尾，直到队列中的元素只有两个，就是约瑟夫和他的朋友位置！

代码示例

#import <Foundation/Foundation.h>
@interface JPQueue : NSObject
/// 队列：头部删除，队尾添加
@property (nonatomic, strong) NSMutableArray *array;
- (void)enqueue:(id)item; //入队
- (id)dequeue; //出队
- (NSInteger)size; //返回队列的大小
//下面3个方法并未用到，只是保证了队列概念的完整
- (id)head; //返回队列头部的元素
- (void)clear; //清空队列
- (BOOL)isEmpty; //isEmpty判断是否为空队列
@end

@implementation JPQueue
//初始化array，或者懒加载
- (instancetype)init {
    if (self = [super init]) {
        self.array = [NSMutableArray array];
    }
    return self;
}
- (void)enqueue:(id)item {
    [self.array addObject:item];
}
- (id)dequeue {
    id item;
    if (self.array.count > 0) {
        item = self.array[0];
        [self.array removeObjectAtIndex:0];
    }
    return item;
}
- (NSInteger)size {
    return self.array.count;
}

- (id)head {
    return self.array.firstObject;
}
- (void)clear {
    [self.array removeAllObjects];
}
- (BOOL)isEmpty {
    return self.array.count == 0;
}
@end

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        JPQueue *queue = [[JPQueue alloc] init];
        //创建包含1~41的数组
        for (NSInteger i = 1; i <= 41; i++) {
            [queue enqueue:@(i)];
        }
        //从1开始数
        NSInteger index = 1;
        while (queue.size > 2) {
            id item = [queue dequeue];
            if (index % 3 != 0) {
                //不是3的倍数重新排队
                [queue enqueue:item];
            }
            index++;
        }
        
        //剩余约瑟夫和他的朋友
        NSLog(@"剩下：%@", queue.array);
    }
    return 0;
}

/*
剩下：(
    16,
    31
)
*/