Циклическая очередь позволяет избежать потери места в обычной реализации очереди с использованием массивов.
DeQueue - удаление элемента из очереди;
FRONT и REAR - два указателя, используемые для отслеживания первого и последнего элементов в очереди.
Как вы можете видеть на изображении выше, после некоторого количества добавления в очередь и удаления из очереди ее размер был уменьшен.
Индексы 0 и 1 могут использоваться только после сброса очереди, когда все элементы сняты.
Как работает круговая очередь
Циклическая очередь работает по процессу циклического приращения, то есть когда мы пытаемся увеличить любую переменную и достигаем конца очереди, мы начинаем с начала очереди по модулю деления с размером очереди.
То есть:
if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of queue)
Операции с очередями работают следующим образом:
- Два указателя, называемые FRONT и REAR, используются для отслеживания первого и последнего элементов в очереди.
- При инициализации очереди мы устанавливаем значение FRONT и REAR равным -1.
- При добавления элемента мы постепенно увеличиваем значение индекса REAR и помещаем новый элемент в положение, на которое указывает REAR.
- При снятии очереди с элемента мы возвращаем значение, на которое указывает FRONT, и постепенно увеличиваем индекс FRONT.
- Перед постановкой в очередь мы проверяем, заполнена ли очередь.
- Перед снятием очереди мы проверяем, пуста ли очередь.
- При инициализации первого элемента мы устанавливаем значение FRONT в 0.
- При удалении последнего элемента мы сбрасываем значения FRONT и REAR в -1.
Однако проверка на полную очередь имеет новый дополнительный пункт:
- Случай 1: FRONT = 0 && REAR == РАЗМЕР - 1
- Случай 2: ПЕРЕДНЯЯ = ЗАДНЯЯ + 1
Второй случай происходит, когда REAR начинается с 0 из-за кругового приращения, и когда его значение всего на 1 меньше значения FRONT, очередь заполнена.
Реализация циклической очереди на языке программирования
Наиболее распространенная реализация очереди использует массивы, но также может возможна реализация с использованием списков.
Реализация с использованием C-программирования
#include <stdio.h>
#define SIZE 5
int items[SIZE];
int front = -1, rear =-1;
int isFull()
{
if( (front == rear + 1) || (front == 0 && rear == SIZE-1)) return 1;
return 0;
}
int isEmpty()
{
if(front == -1) return 1;
return 0;
}
void enQueue(int element)
{
if(isFull()) printf("\n Queue is full!! \n");
else
{
if(front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
printf("\n Inserted -> %d", element);
}
}
int deQueue()
{
int element;
if(isEmpty()) {
printf("\n Queue is empty !! \n");
return(-1);
} else {
element = items[front];
if (front == rear){
front = -1;
rear = -1;
} /* В Q есть только один элемент, поэтому мы сбрасываем очередь после ее удаления. */
else {
front = (front + 1) % SIZE;
}
printf("\n Deleted element -> %d \n", element);
return(element);
}
}
void display()
{
int i;
if(isEmpty()) printf(" \n Empty Queue\n");
else
{
printf("\n Front -> %d ",front);
printf("\n Items -> ");
for( i = front; i!=rear; i=(i+1)%SIZE) {
printf("%d ",items[i]);
}
printf("%d ",items[i]);
printf("\n Rear -> %d \n",rear);
}
}
int main()
{
// Ложь, потому что front = -1
deQueue();
enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);
// Невозможно поставить в очередь, потому что front == 0 && rear == SIZE - 1
enQueue(6);
display();
deQueue();
display();
enQueue(7);
display();
// Невозможно поставить в очередь, потому что front == rear + 1
enQueue(8);
return 0;
}
Когда вы запустите эту программу, получите следующее:
Inserted -> 1 Inserted -> 2 Inserted -> 3 Inserted -> 4 Inserted -> 5 Queue is full!! Front -> 0 Items -> 1 2 3 4 5 Rear -> 4 Deleted element -> 1 Front -> 1 Items -> 2 3 4 5 Rear -> 4 Inserted -> 7 Front -> 1 Items -> 2 3 4 5 7 Rear -> 0 Queue is full!!
Реализация с использованием программирования на C ++
#include <iostream>
#define SIZE 5 /* Размер круговой очереди */
using namespace std;
class Queue {
private:
int items[SIZE], front, rear;
public:
Queue(){
front = -1;
rear = -1;
}
bool isFull(){
if(front == 0 && rear == SIZE - 1){
return true;
}
if(front == rear + 1) {
return true;
}
return false;
}
bool isEmpty(){
if(front == -1) return true;
else return false;
}
void enQueue(int element){
if(isFull()){
cout << "Queue is full";
} else {
if(front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
cout << endl << "Inserted " << element << endl;
}
}
int deQueue(){
int element;
if(isEmpty()){
cout << "Queue is empty" << endl;
return(-1);
} else {
element = items[front];
if(front == rear){
front = -1;
rear = -1;
} /* Q имеет только один элемент, поэтому мы удаляем очередь после удаления. */
else {
front=(front+1) % SIZE;
}
return(element);
}
}
void display()
{
/* Функция для отображения статуса круговой очереди */
int i;
if(isEmpty()) {
cout << endl << "Empty Queue" << endl;
}
else
{
cout << "Front -> " << front;
cout << endl << "Items -> ";
for(i=front; i!=rear;i=(i+1)%SIZE)
cout << items[i];
cout << items[i];
cout << endl << "Rear -> " << rear;
}
}
};
int main()
{
Queue q;
// Ложь, потому что front = -1
q.deQueue();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
// Невозможно поставить в очередь, потому что front == 0 && rear == SIZE - 1
q.enQueue(6);
q.display();
int elem = q.deQueue();
if( elem != -1)
cout << endl << "Deleted Element is " << elem;
q.display();
q.enQueue(7);
q.display();
// Невозможно поставить в очередь, потому что front == rear + 1
q.enQueue(8);
return 0;
}
Когда вы запустите эту программу, получите следующее:
Queue is empty Inserted 1 Inserted 2 Inserted 3 Inserted 4 Inserted 5 Queue is full Front -> 0 Items -> 12345 Rear -> 4 Deleted Element is 1 Front -> 1 Items -> 2345 Rear -> 4 Inserted 7 Front -> 1 Items -> 23457 Rear -> 0 Queue is full
