Циркулярная очередь, не теряя при этом запись или используя счетчик

Question

Возможно ли реализовать круговую очередь с использованием array без наличия счетчика для подсчета количества элементов в очереди или без потери какой-либо записи массива?

Что я думаю:

Это невозможно, давайте предположим, что у нас есть два указателя front и rear, первый указывает на первый элемент очереди,

мы можем определить задний указатель в два способа:

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

2.It указывает на место, где будет вставлен следующий элемент.

В любом случае мы не можем различить полную пустую очередь &, если мы не тратим хотя бы одну запись массива, t держать счетчик счетчик the number of inserted - number of deleted elements

Answer 1

Как я его реализовал, я использовал дополнительный bool под названием «empty». Вы правы, нельзя различать в том случае, если оба указателя находятся в одном месте.

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

Answer 2

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

• Очередь пуста. Все указатели указывают на одно и то же место (второе определение для заднего указателя).
• В очереди есть 1 элемент, и удаление элемента сделает его пустым. Средний указатель и другой указатель указывают на одно и то же место.

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

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

Answer 3

Ваши проблемы обычно называются full vs. empty difficulty круговых очередей. Цитирование:

Для решения этой путаницы существует целый ряд решений:

1. Всегда держать один слот открытым.
2. Используйте количество заполнений, чтобы различать два случая.
3. Используйте дополнительный зеркальный бит, чтобы отличить два случая.
4. Используйте количество чтения и записи, чтобы получить счетчик заполнения.
5. Используйте абсолютные индексы.
6. Запишите последнюю операцию.

Номера 1, 2 и 4 вы адресуете прямо в своем вопросе. Они потребляют определенное количество памяти, кроме массива и индексов/указателей начала/конца (или спереди/сзади, как вы их называете). Другие решения также потребляют память.

# 3 - использование зеркального отображения Бит

только добавляет один дополнительный логическое или перечисление, по существу isEmpty или isFull. Идея, логика и доказательство этого подхода - more complicated.

# 5 - absoulte индексы

Индексы увеличиваются, когда операция выполняется, и никогда не уменьшается. Они по сути являются счетчиками числа операций каждого выполняемого типа. У этого есть other drawbacks.

# 6 - запись последней операции

По существу же, как и # 3, но различной семантикой.

В любом случае, все эти ссылки относятся к статье в Википедии. Я очень рекомендую. Могут быть и другие подходы, но было бы трудно улучшить один из 6 подходов, указанных в вашей статье. Все они имеют недостатки, а также преимущества, поэтому тщательно подумайте о предполагаемом прецеденте, прежде чем приступать к реализации.

Answer 4

в начале, сначала = 0, задний = -1;

мы добавляем его следующим образом ..... массив [задний]; задний = (задний + 1)% MAX;

мы удаляем его следующим образом .. массив [передний]; передние = (передние + 1)% MAX;

при удалении элемента из массива, мы можем добавить условие после того, как следует ...
if(front==rear+1) first=0, rear=-1

то пустое состояние может быть задано как ...

if(rear==-1) printf("Empty"); 

в полное состояние будет ...

if ((front==(rear+1) || (front==0 && rear==(n-1)) && rear!=-1) printf("Full"); 

это может работать. не используется функция «count»