Дөңгелек кезек массивтерді пайдалана отырып, кезекті әдеттегі іске асыруда бос орынды ысырап етуді болдырмайды.
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-жағдай: АЛДЫҢҒЫ = 0 && АРТЫ == ӨЛШЕМ - 1
- 2-жағдай: АЛДЫҢҒЫ = АРТТЫ + 1
Екінші жағдай REAR айналмалы қадамға байланысты 0-ден басталғанда және оның мәні FRONT мәнінен тек 1-ге аз болғанда, кезек толған кезде орын алады.
Программалау тілінде циклдік кезекті жүзеге асыру
Кезектің ең көп тараған орындалуы массивтерді пайдаланады, бірақ тізімдерді қолданатын іске асыру да мүмкін болуы мүмкін.
Си программалау арқылы іске асыру
#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!!
Си программалау арқылы іске асыру ++
#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
