《啊哈!算法》第 2 章第 1 节,队列的 Swift 实现
问题
给一个数字序列,解密方法是:删除第 1 个,将第 2 个放到这个序列末尾,再将第 3 个数删除,将第 4 个移至队尾,再将第 5 个数字删除……直到剩下最后一个数,把它也删除。然后把删除的数连在一起。
解决
head 标示序列首位,tail 表示序列尾部的下一个位置(无元素),移动 head 将队首出列,添加数字至队尾则将 tail + 1
var queue = [6, 3, 1, 7, 5, 8, 9, 2, 4]
var head = 0 //开始的时候指向队首
var tail = queue.count //tail 标示队尾的下一个位置
//当队列不为空时执行循环
while head < tail {
// print("\(queue[head])", term)
//打印队首并将队首出列
print("\(queue[head])", separator: " ", terminator: " ")
head += 1
//head 已经移到 tail 位置则中止(书中的 bug,head 会越界)
guard head < queue else { break }
//先将新队首的数添加到队尾
queue.append(queue[head])
tail += 1
//新队首出列
head += 1
}
GitHub 中的代码用结构体来实现同样的逻辑。