Arrayes circulaires dans les files d'attente

Question

Comment mod est-il utilisé pour déterminer le début et la fin d'un tableau circulaire dans une file d'attente?

Answer 1

Eh bien, vous gardez généralement trace de l'index du premier élément et de la taille actuelle. Si la taille est égale à la taille du tableau, cela signifie que le tableau est plein. Enqueuing un nouvel élément, vous devez ensuite développer le tableau. Sinon, vous écrivez simplement à l'élément (start + size + 1) % array_size.

Lorsque vous dequeue un élément, vous prenez l'élément à start, remplacer par null pour permettre la collecte des ordures, décrémentez size, et incrémenter start, emballage à 0 si nécessaire.

Une alternative à garder une trace de start et size est de garder une trace de start et next - où next est l'indice de l'élément suivant à en file d'attente. Vous repérez si le tableau est plein lorsque start == next. Ensuite, la mise en file d'attente (lorsqu'elle n'est pas complète) nécessite uniquement que vous modifiiez next, et dequeuing vous demande seulement de changer start. Comme précédemment, vous devez envelopper lorsque vous augmentez ou décrémentez start/next.

Answer 2

Dans un tableau circulaire, l'arrière de la file d'attente est (front + number_of_elements_in_queue - 1) mod size_of_queue et le recto de la file d'attente doit être suivi après chaque file d'attente.

Answer 3

Il peut être utile de jeter un coup d'œil à la fonction wrapIndex à la ligne 28 de this example. wrapIndex (head) est le début (voir ligne 93) et wrapIndex (tail) est la fin (voir ligne 76).