Циклический буфер или циклическая очередь — это расширенная версия обычной очереди, в которой последний индекс и хвостовой индекс соединены в циклическую структуру. Циклический буфер в C++ использует два метода: enqueue() и dequeue(). На основе этих методов мы выполняем операцию циклического буфера или циклической очереди.
- Метод enqueue() проверяет, заполнен ли буфер. В противном случае убедитесь, что конечный индекс является последним. Если да, установите значение хвоста равным 0. Если нет, увеличьте значение хвоста на значение по этому индексу.
- Функция dequeue() принимает значение из переднего индекса в циклической очереди. Если очередь пуста, сообщение отобразит эту пустую очередь. В противном случае он получает последнее значение и удаляет его из очереди.
Программа для реализации циклического буфера на C++
Следуя двум упомянутым методам, мы реализуем циклический буфер на C++. Давайте рассмотрим все шаги реализации циклической очереди на C++.
#include
использование пространства имен std;
структура MyQueue
{
интервал голова , хвост ;
интервал Qsize;
интервал * НьюАрр;
Моя очередь ( интервал нет ) {
голова '=' хвост '=' -1 ;
Qsize = размер;
NewArr = новый int [ с ] ;
}
недействительность enQueue ( int val ) ;
int deQueue ( ) ;
void showQueue ( ) ;
} ;
Начиная с кода, мы сначала создаем структуру MyQueue для инициализации переменных head и Tail. Переменная head представляет передние индексы, а хвост — задние задние индексы массива. После этого определяется размер циклической очереди, обозначаемый переменной «Qsize».
Затем мы определяем динамически выделяемый массив NewArr, в котором хранятся значения циклической очереди. Затем мы вызываем MyQueue(), который является конструктором, и передаем параметр «sz» для размера циклической очереди. Внутри конструктора MyQueue() мы присваиваем значение «-1» указателям на начало и конец. Это отрицательное значение указывает на то, что очередь сейчас пуста. Двигаясь дальше, мы присваиваем значение «sz», которое представляет размер циклической очереди. Циклическая очередь «NewArr» задается с помощью нового ключевого слова для создания массива целых чисел в пределах указанного размера «sz».
Затем мы определяем функции enQueue() и dequeue(). Enqueue() вставляет значения в определенную циклическую очередь из хвоста. Однако элементы в заголовке циклической очереди удаляются функцией dequeue(). Функция-член showQueue() отображает значения циклической очереди.
Шаг 1. Создайте функцию для вставки элементов в кольцевой буфер
На предыдущем этапе мы установили класс, в котором инициализируются частные члены, а функции закрытых членов настроены для реализации циклической очереди. Теперь мы устанавливаем функцию для создания циклической очереди и вставляем значения в циклическую очередь, используя алгоритм.
void MyQueue::enQueue ( int val ){
если ( ( голова == 0 && хвост == Размер - 1 ) || ( хвост == ( голова - 1 ) % ( Размер - 1 ) ) )
{
расчет << ' \п Очередь заполнена» ;
возвращаться ;
}
еще если ( голова == - 1 )
{
голова '=' хвост '=' 0 ;
НовоеПрибытие [ хвост ] = значение;
}
еще если ( хвост == Размер - 1 && голова ! '=' 0 )
{
хвост '=' 0 ;
НовоеПрибытие [ хвост ] = значение;
}
еще {
хвост ++;
НовоеПрибытие [ хвост ] = значение;
}
}
Здесь мы вызываем функцию «enqueue()» из класса «MyQueue», чтобы вставить элемент в циклическую очередь, если очередь пуста или не заполнена. Функция «enqueue()» передается с параметром «val» и вставляет значение из хвоста циклической очереди. Для этого мы устанавливаем условие «if-else», чтобы вставить значения в циклическую очередь. Первый оператор «if», а именно «if ((head == 0 && Tail == Qsize – 1) || (tail == (head – 1) % (Qsize – 1)))», проверяет два условия, является ли заголовок находится в начальной позиции, а хвост — в конечной позиции круговой очереди. Затем он проверяет, находится ли хвост в одном положении позади головы. Если какое-либо из этих условий выполнено, очередь не пуста и подсказка генерирует сообщение.
Далее у нас есть условие «else-if», которое определяет, пуста ли очередь. Если это так, значение вставляется в очередь. Поскольку заголовок сохраняется равным -1, это показывает, что очередь пуста и значение необходимо вставить в циклическую очередь. Для этого мы устанавливаем заголовок и хвост равными 0. Затем мы вставляем значение из позиции хвоста в циклическую очередь «NewArr».
Затем у нас есть третье условие «иначе-если», которое проверяет, находится ли хвост в последней позиции очереди, а заголовок не является начальной позицией очереди. Это условие применяется, когда хвост достигает конца, а в исходной позиции еще есть место. Для этого нам нужно установить заголовок в 0, а элемент будет добавлен из позиции хвоста. Наконец, если все заданные условия не выполнены, очередь не будет ни пустой, ни полной. В этом случае мы увеличиваем хвост на 1, и значение добавляется из новой позиции хвоста.
Шаг 2. Создайте функцию для удаления элементов из кольцевого буфера.
Мы установили предыдущий код для создания и вставки элементов в циклическую очередь с помощью функции enqueue(). Теперь мы определяем реализацию удаления элементов из кольцевого буфера в случае его переполнения.
int MyQueue::deQueue ( ){
если ( голова == - 1 )
{
расчет << ' \п Очередь свободна» ;
возвращаться ИНТ_МИН;
}
int MyData = NewArr [ голова ] ;
НовоеПрибытие [ голова ] '=' -1 ;
если ( голова == хвост )
{
голова '=' -1 ;
хвост '=' -1 ;
}
еще если ( голова == Размер - 1 )
голова '=' 0 ;
еще
голова ++;
возвращаться Мои данные;
}
В данном коде мы вызываем функцию dequeue() из класса Myqueue, чтобы удалить элемент из головного индекса. Итак, у нас есть оператор if, который проверяет, пуста ли очередь. В заголовке установлено значение «-1», которое представляет пустую очередь. Генерируется сообщение о том, что очередь пуста, а затем возвращается INT_MIN, которое является постоянным минимальным значением для целого числа. Оператор if определяет, свободна ли очередь. Для этого мы определяем переменную «MyData» и устанавливаем значение элемента в начале очереди. Затем мы устанавливаем заголовок в позицию -1, что указывает на то, что это значение удалено из очереди. После этого проверяем, равны ли голова и хвост или нет. Если оба равны, мы присваиваем обоим значение «-1», обозначающее пустую циклическую очередь. Наконец, мы проверяем, работает ли функция dequeue(), если заголовок находится в последнем индексе очереди. Для этого мы устанавливаем для него значение «0», которое зацикливается в начале массива. Если ни одно из заданных условий не является истинным, значение заголовка увеличивается и возвращается элемент, исключенный из очереди.
Шаг 3. Создайте функцию для отображения элементов кольцевого буфера
В этом разделе мы вызываем функцию showQueue() для отображения элементов циклической очереди NewArr.
void MyQueue::showQueue ( ){
если ( голова == - 1 )
{
расчет << ' \п Очередь свободна» ;
возвращаться ;
}
расчет << ' \п Элементы круговой очереди: ' ;
если ( хвост > '=' голова )
{
для ( интервал я = голова ; я < '=' хвост ; я++ )
расчет << НовоеПрибытие [ я ] << ' ' ;
}
еще
{
для ( интервал я = голова ; я < размер; я++ )
расчет << НовоеПрибытие [ я ] << ' ' ;
для ( интервал я = 0 ; я < '=' хвост ; я++ )
расчет << НовоеПрибытие [ я ] << ' ' ;
}
}
Сначала проверяется пустой статус очереди. Индикация того, что кольцевая очередь свободна, отображается, если очередь свободна. В противном случае функция покажет элементы циклической очереди. Для этого мы определяем оператор «if», где у нас есть хвост, который больше или равен голове. Это условие установлено для обработки случая, когда циклическая очередь не завершена.
В этом случае мы используем цикл «for» для итерации от начала до конца и печати значений циклической очереди. Следующий случай — завершение кольцевой очереди. Для этого мы проверяем с помощью условия «если», когда хвост меньше головы. Затем нам нужно использовать два цикла, первый из которых выполняет итерацию от головы до конца очереди, а второй — от начала хвоста.
Шаг 4. Создайте функцию Main() программы кольцевой очереди.
Наконец, мы создаем функцию main() программы, в которой вставляем пять целых чисел в циклическую очередь и отображаем целые числа очереди. После этого мы показываем удаленные целые числа из циклической очереди, вызывая функцию dequeue(). После удаления нескольких элементов из очереди мы снова заполняем очередь, вставляя новые элементы с помощью функции enqueue().
int главный ( ){
Моя очередь, которая ( 5 ) ;
// Вставка элементов в Круговая очередь
que.enQueue ( одиннадцать ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( пятнадцать ) ;
// Элементы дисплея присутствуют в Круговая очередь
que.showQueue ( ) ;
// Удаление элементов из круговой очереди
расчет << ' \п Удаленный элемент = ' << que.deQueue ( ) ;
расчет << ' \п Удаленный элемент = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
возвращаться 0 ;
}
Выход:
Результаты реализации циклической очереди показаны на экране подсказки C++.
Заключение
В заключение, в этой статье подробно объясняется тема кольцевого буфера. Сначала мы создали циклический буфер, затем объяснили, как удалить его из циклической очереди, а затем отобразили элементы циклического процесса на C++.