Как найти количество элементов в циклической очереди? |передний - задний| не всегда работает.
Есть ли одна формула, чтобы узнать, сколько элементов находится в круговой очереди, используя передний, задний и размер массива?
Как найти количество элементов в циклической очереди? |передний - задний| не всегда работает.
Есть ли одна формула, чтобы узнать, сколько элементов находится в круговой очереди, используя передний, задний и размер массива?
на самом деле размер был бы,
size = front > rear ? (MAX - front + rear + 1) : (rear - front + 1);
или можно перейти к общей формуле:
size = abs(abs(MAX - front) - abs(MAX -rear));//this works in every situation
Предполагая, что вы реализуете его, используя массив размером N
, поэтому есть указатели, указывающие на переднюю и заднюю часть. Используйте следующую формулу:
size = front > rear ? (front - rear) : (front+N - rear);
Предполагая, что вы используете массив размера N для реализации очереди, размер очереди будет size = (N-front + rear) mod N
.
Стандартный ответ — взять два итератора в начале, увеличить первый один раз, а второй два раза. Проверьте, указывают ли они на один и тот же объект. Затем повторяйте до тех пор, пока тот, который увеличивается дважды, либо не достигнет первого, либо не достигнет конца. внутри этого цикла используйте счетчик, чтобы получить длину CQuueeue
Ни одна из формул не учитывает пустой (нулевой) случай. Это даст вам количество свободных байтов, доступных в очереди:
FreeSpace = (printRdQue == printWrQue) ? PRINT_QUEUE_SIZE :
(PRINT_QUEUE_SIZE - printWrQue + printRdQue) % PRINT_QUEUE_SIZE;
может ли ваша очередь содержать один и тот же элемент в нескольких местах? если это возможно, то я не думаю, что вы можете это сделать, поскольку нет никакого способа узнать разницу между:
a->b->c
а также
a->b->c->a->b->c
если он не может содержать один и тот же элемент более одного раза, просто просматривайте очередь, пока не найдете элемент, который вы уже видели
Нет элементов в циклической очереди,
size = (N-f+r) mod N
куда
Эта формула работает как для линейных, так и для кольцевых очередей.
Что нужно для реализации циклической очереди?
Ответ: вам понадобятся передние и задние узлы + список элементов + количество_элементов.
Конечно, это реализовано только тогда, когда очередь конечна, когда речь идет о
динамическое размещение будет другим.
Взгляните на пример на языке C,
typedef struct
{
TYPE items[MAXSIZE];
TYPE front;
TYPE rear;
int count_items;
} QUEUE;
Это гарантирует вам точное количество элементов, находящихся в настоящее время в очереди.
Когда вы хотите вставить элемент в очередь, вы просто увеличиваете значение Rear и count_items, а когда хотите удалить элемент из очереди, вы просто уменьшаете значение Rear и count_items.
нет. элементов = (сзади + MAX_SIZE - спереди) % MAX_SIZE + 1
Самый простой способ подсчитать количество элементов в циклической очереди:
если front > rear
(т.е. спереди впереди, чем сзади) Просто подсчитайте количество пустых мест между ними
front - (rear+1)
иначе если front < rear
:
rear - front + 1
Программа C, если вам нужно:
int find_ele(int total,int front,int rear){
if(rear < front ) { \\1st case
int res = front - rear + 1;
return (total-res);}
else{
return (rear - front + 1);
}
}
Предполагая, что вы реализуете очередь с использованием кругового массива A[0, n-1], где (n-1)-й индекс используется для хранения полного/пустого состояния, формула будет выглядеть так:
Количество элементов = { зад-перед + 1 , если зад==перед
{ rear-front + n , otherwise
Мы будем перемещать очередь по часовой стрелке при каждой постановке в очередь или удалении из очереди.