почему хвост в круговой очереди указывает на пустой элемент?

Question

Я хочу знать, почему хвост в круговой очереди должен указывать на пустой элемент?Как мы все знаем, емкость кольцевой очереди равна (N-1), потому что она должна оставлять пустое пространство для очереди, чтобы судить, заполнена ли очередь.Но, с моей точки зрения, это связано с тем, что указатель хвоста должен указывать на пустой элемент, если он может указывать на последний элемент, а не на пустой, он может заполнить все пробелы в очереди.Поэтому я хочу знать, почему мы создаем круговую очередь в этом формате, большое спасибо!

Answer 1

Если указатель хвоста указывает на следующий элемент для заполнения (и без элемента «всегда пусто»), есть два условия, которые мы не можем отличить друг от друга.Это условия «очередь заполнена» и «очередь пуста», в обоих случаях голова и хвост имеют одно и то же значение.

             H,T
        +---+---+---+---+---+
empty:  | - | - | - | - | - |
        +---+---+---+---+---+
        +---+---+---+---+---+
full:   | 5 | 1 | 2 | 3 | 4 |
        +---+---+---+---+---+
             H,T

Это много, что вы уже знаете, основываясь на вашем вопросе.

Однако, если бы вы использовали хвостовой указатель для указания на последний заполненный элемент, вы бы все же не смогли бы различить два условия.

Это связано с тем, что в одноэлементной очереди заголовок и хвост будут равны, поэтому для представления пустой очереди хвост будет равен одному перед заголовком (если вы этого не сделали, «очередь пуста»условия "и" очередь с одним элементом "были бы неразличимы).К сожалению, это также имеет место, если вы полны:

          T   H
        +---+---+---+---+---+
empty:  | - | - | - | - | - |
        +---+---+---+---+---+
        +---+---+---+---+---+
full:   | 5 | 1 | 2 | 3 | 4 |
        +---+---+---+---+---+
          T   H

---

Суть в том, что голова и хвост не вполне достаточно информации, чтобы однозначно идентифицировать все условия независимо откакую схему вы выберете, поэтому есть пустая ячейка.

Вы можете делать это так, как вы хотите (хвост указывает на последнюю заполненную ячейку, а не на следующую ячейку, которая будет заполнена), новам будет все еще нужна пустая ячейка, чтобы различать пустые и полные случаи.

---

Конечно, вы можете решить эту проблему, введя count дляструктура данных, а также.Если у вас есть это, вы можете легко различать случаи (в обоих сценариях).

Answer 2

Извините, что замечаю, где я ошибаюсь ...... ЕСЛИ указатель хвоста указывает на последний элемент, а не на последний (элемент + 1), если хвост == front, мы не можем знать, находится ли очередь в очередипуст или заполнен только один элемент.Так что это вызовет некоторые проблемы.