三个不变式

基本不变式

在执行方法之前和之后,队列必须要保持的不变式:

  • 当入队插入新节点之后,队列中有一个 next 域为 null 的(最后)节点
  • 从 head 开始遍历队列,可以访问所有 item 域不为 null 的节点

head 的不变式和可变式

在执行方法之前和之后,head 必须保持的不变式:

  • 所有”活着”的节点(指未删除节点),都能从 head 通过调用 succ() 方法遍历可达。
  • head 不能为 null。
  • head 节点的 next 域不能引用到自身。

在执行方法之前和之后,head 的可变式:

  • head 节点的 item 域可能为 null,也可能不为 null。
  • 允许 tail 滞后(lag behind)于 head,也就是说:从 head 开始遍历队列,不一定能到达 tail。

tail 的不变式和可变式

在执行方法之前和之后,tail 必须保持的不变式:

  • 通过 tail 调用 succ() 方法,最后节点总是可达的。
  • tail 不能为 null。

在执行方法之前和之后,tail 的可变式:

  • tail 节点的 item 域可能为 null,也可能不为 null。
  • 允许 tail 滞后于 head,也就是说:从 head 开始遍历队列,不一定能到达 tail
  • tail 节点的 next 域可以引用到自身。

在接下来的源代码分析中,在初始化 ConcurrentLinkedQueue 之后及调用入队 / 出队方法之前和之后,我们都会参照上面三个不变式来分析它们的正确性

论读书
睁开眼,书在面前
闭上眼,书在心里
原文地址:https://www.cnblogs.com/YC-L/p/14438735.html