[структура данных]: хвостовой указатель циклической очереди

Question

В реализации циклической очереди указатель хвоста указывает на позицию 1 после последнего элемента в очереди:

|1|2|3|4|5| | |
 ^         ^
front      tail

почему?

Я думаю, что могу реализовать циклическийОчередь с указателем хвоста, указывающим на самый последний элемент, а не на 1 после последнего.

Answer 1

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

• front указывает на первый (самый старый) используемый элемент - следующий элемент для чтения
• tail указывает на первый (самый старый) неиспользуемый элемент - следующий записываемый элемент

В любом случае вам нужно сделать немного больше, чтобы различить полную циклическую очередь ипустой.Некоторые альтернативы (в том числе и по-своему) обсуждаются в статье Википедии о кольцевых буферах .

Answer 2

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

http://en.wikipedia.org/wiki/Circular_buffer#Full_.2F_Empty_Buffer_Distinction