查找循环队列中的项目？

Question

我有一个订购物品的循环队列。我想知道是否有一个值为“x”的项目在其中。

要做到这一点，最好的方法（算法）是什么？

Answer 1

如果您可以按索引访问每个项目，则可以使用二分查找。

如果您只能看到第一个项目，您需要从队列中弹出它们，直到搜索键低于刚刚弹出的项目的键。由于队列已排序，只要知道密钥不再在队列中，就可以立即停止。

[编辑]由于可以通过索引来访问：经纱在其中它映射到一个“阵列”（即，具有方法的对象的圆形队列get(index)其中index运行从0到length-1的且在内部确实((index+start)%length)

。

这样的话，你可以从尾部到头部应用二进制搜索，而不考虑实际的数据布局。

Answer 2

“最好”是一个主观术语，循环队列很少大到足以保证二进制搜索，所以我会选择在没有关于队列大小的信息时简单。最简单的方法是从头部开始，检查每个元素，直到尾部（或者你已经按顺序超越了它）来查看它是否存在。

假设您的头部变量指向将被移除的第一个项目并且尾部指向放置项目的下一个位置。进一步假设你正在浪费一个物品槽来简化代码（这是一种简化代码并告诉空白队列和完整队列之间差异的技巧）。这意味着空队列由tail == head表示。

ptr = head 
while ptr != tail: 
    if element[ptr] = searchvalue: 
     return true 
    if element[ptr] > searchvalue: 
     return false 
    ptr = (ptr + 1) % queuesize; 
return false 

Answer 3

我们可以向相反的方向穿越？也就是说，如果这样的话，我们可以设计一些可以利用它。即决定进行搜索的方式。

由于它是有序的，我们可以猜测它的位置（只是一个猜测，或者可能利用统计数据），然后开始全面搜索，只在方向上得到更少的结果