All geek questions in one place

Finding an item in a circular queue?

I have a circular queue of ordered elements. I want to know if it has an element with a value of "x".

What is the best way (algorithm) to do this?

+3
source share
4 answers

If you can access each item by index, you can use binary search.

If you can see only the first element, you need to pull them out of the queue until the search key is lower than the key of the element that you just clicked. Since the sorting of the queue is sorted, you can stop as soon as you find out that the key can no longer be in the queue.

[EDIT] : , "" (.. get(index), index 0 length-1 ((index+start)%length).

, , .

+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
+2

? .. . , -, . .. , .

, ( , , , ), ,

0

, OP . .

, , , , .

The first case is a linear search with an initial “interval” of zero, and the final interval is supposedly recorded / maintained.

The second case is more complicated. The start slot is circulating as previous repositories are overwritten. The end slot also circulates, only one position after the start slot.

To perform a linear search on these moving indexes, a translation is needed to place the start slot at zero and the end slot at the size of the buffer.

How this algorithm works is yet to be determined.

0
source

Source: https://habr.com/ru/post/1709858/

More articles:


All Articles