Циклічна черга дозволяє уникнути втрати місця у звичайній реалізації черги з використанням масивів.
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
