c circular queue data structure
Овај водич о структури података кружног реда за Ц ++ објашњава шта је кружни ред, које су основне операције уз имплементацију и примене:
Кружни ред је продужетак основног реда о којем смо раније говорили. Такође је познат и као „Ринг буффер“.
Шта је Цирцулар Куеуе у Ц ++?
Кружни ред је линеарна структура података која се користи за чување ставки података. Изводи операције пратећи ФИФО (Фирст Ин, Фирст Оут) приступ, а последња позиција у реду је поново повезана са првом позицијом да формира круг.
=> Овде потражите целу серију обука за Ц ++
Шта ћете научити:
Кружни ред у Ц ++
Следећи дијаграм приказује кружни ред.
Горња слика приказује кружну структуру података величине 10. Првих шест елемената већ су у реду и видимо да су прва и последња позиција спојене. Због овог аранжмана, простор се не губи, као што се то дешава у линеарном реду.
основна скл питања за интервју за тестере
У линеарном реду након што се ред напуни, бришемо елементе са другог краја, а статус реда је и даље приказан као пун и не можемо убацити више елемената.
У кружни ред, када је ред пун, и када уклонимо елементе са предње стране пошто су повезани последњи и први положај, можемо да убацимо елементе са задње стране који су испражњени брисањем елемента.
У следећем одељку сазнаћемо о основним операцијама кружног реда.
Основне операције
Неке од основних операција кружног реда су следеће:
Фронт: Враћа предњу позицију у кружном реду.
Задњи: Враћа задњи положај у кружном реду.
Енкуеуе: Енкуеуе (валуе) се користи за уметање елемента у кружни ред. Елемент се увек убацује на задњи крај реда.
Пратимо следећи редослед корака за уметање новог елемента у кружни ред.
# 1) Проверите да ли је кружни ред пун: тест ((задњи == ВЕЛИЧИНА-1 && предњи == 0) || (задњи == предњи-1)), где је „ВЕЛИЧИНА“ величина кружног реда.
#два) Ако је кружни ред пун, приказује се порука „Ред је пун“. Ако ред тада није пун, проверите да ли је (задњи == ВЕЛИЧИНА - 1 && предњи! = 0). Ако је тачно, поставите задњи = 0 и уметните елемент.
Декуеуе: Декуеуе функција се користи за брисање елемента из реда. У кружном реду, елемент се увек брише са предњег краја. Доље је дат редослед за декуеуе операцију у кружном реду.
Кораци:
# 1) Проверите да ли је кружни ред празан: проверите да ли је (фронт == - 1).
#два) Ако је празно, прикажите поруку „Ред је празан“. Ако ред није празан, изведите корак 3.
# 3) Проверите да ли (напред == позади). Ако је тачно, поставите фронт = задњи = -1, иначе проверите да ли је (фронт == сизе-1), ако је тачно, поставите фронт = 0 и вратите елемент.
Илустрација
У овом одељку ћемо проћи кроз детаљну илустрацију додавања / уклањања елемената у кружном реду.
Размотрите следећи кружни ред од 5 елемената као што је приказано доле:
који је најбољи оперативни систем Виндовс
Даље, у ред убацујемо ставку 1.
Затим убацујемо ставку са вредношћу 3.
Када убацимо елементе да би ред био пун, приказ ће бити као што је приказано доле.
Сада бришемо два елемента, тј. Ставку 1 и ставку 3 из реда, као што је приказано доле.
Даље, убацујемо или стављамо елемент 11 у кружни ред као што је приказано у наставку.
Поново ставимо елемент 13 у кружни ред. Ред ће изгледати као што је приказано у наставку.
Видимо да у кружном реду померамо или убацујемо елементе у круг. Стога можемо потрошити читав простор реда док се не напуни.
Имплементација
Применимо кружни ред користећи Ц ++.
#include using namespace std; class Queue { public: // Initialize front and rear int rear, front; // Circular Queue int size; int *circular_queue; Queue(int sz) { front = rear = -1; size = sz; circular_queue = new int(sz); } void enQueue(int elem); int deQueue(); void displayQueue(); }; /* Function to create Circular queue */ void Queue::enQueue(int elem) { if ((front == 0 && rear == size-1) || (rear == (front-1)%(size-1))) { cout<<'
Queue is Full'; return; } else if (front == -1) { /* Insert First Element */ front = rear = 0; circular_queue(rear) = elem; } else if (rear == size-1 && front != 0) { rear = 0; circular_queue(rear) = elem; } else { rear++; circular_queue(rear) = elem; } } // Function to delete element from Circular Queue int Queue::deQueue() { if (front == -1) { cout<<'
Queue is Empty'; return -1; } int data = circular_queue(front); circular_queue(front) = -1; if (front == rear) { front = -1; rear = -1; } else if (front == size-1) front = 0; else front++; return data; } //display elements of Circular Queue void Queue::displayQueue() { if (front == -1) { cout<<'
Queue is Empty'<= front) { for (int i = front; i <= rear; i++) cout< Изнад је приказан резултат операција кружног реда. Прво додајемо елементе, а затим два елемента уклањамо из реда или уклањамо из њих. Затим у кружни ред убацујемо или стављамо у ред још три елемента. Видимо да се за разлику од линеарног реда елементи додају на крају реда.
Имплементација повезане листе
Хајде да разговарамо сада о примени повезаног списка кружног реда. Доље је дато спровођење повезане листе на кружном реду у Ц ++. Имајте на уму да користимо струцт за представљање сваког чвора. Операције су исте као што је претходно речено, осим што их у овом случају морамо изводити у односу на повезане чворове листе.
Излаз приказује кружни ред након операције енкуеуе, декуеуе и такође након друге операције енкуеуе.
#include using namespace std; struct Node { int data; struct Node* link; }; struct PQueue { struct Node *front, *rear; }; /* this functions performs enqueue operation for circular queue */ void enQueue(PQueue *pq,int elem) { struct Node *temp = new Node; temp->data = elem; if (pq->front == NULL) pq->front = temp; else pq->rear->link = temp; pq->rear = temp; pq->rear->link = pq->front; } // This function performs dequeue operation for Circular Queue int deQueue(PQueue *pq) { if (pq->front == NULL) { cout<<'Queue is empty!!'; return -1; } int elem; // item to be dequeued // item is the last node to be deleted if (pq->front == pq->rear) { elem = pq->front->data; free(pq->front); pq->front = NULL; pq->rear = NULL; } else //more than one nodes { struct Node *temp = pq->front; elem = temp->data; pq->front = pq->front->link; pq->rear->link= pq->front; free(temp); } return elem ; } //display elements of Circular Queue void displayQueue(struct PQueue *pq) { struct Node *temp = pq->front; while (temp->link != pq->front) { cout<data<<' '; temp = temp->link; } cout<data; } //main program int main() { // Create a circular queue and initialize front and rear PQueue *pq = new PQueue; pq->front = pq->rear = NULL; // Insert/enqueue elements in Circular Queue enQueue(pq, 1); enQueue(pq, 3); enQueue(pq, 5); cout<<'
Circular Queue elements after enqueue operation: '; // Display elements in Circular Queue displayQueue(pq); // Delete/dequeue elements from Circular Queue cout<<'
Dequeued Item: '< Излаз:
Следећа имплементација је Јава програм за демонстрирање кружног реда помоћу повезане листе.
import java.util.* ; class Main { // Node structure static class Node { int data; Node link; } static class CQueue { Node front, rear; } // Enqueue operation for circular queue static void enQueue(CQueue cq, int value) { Node temp = new Node(); temp .data = value; if (cq .front == null) cq .front = temp; else cq .rear .link = temp; cq .rear = temp; cq .rear .link = cq .front; } // Dequeue operation for Circular Queue static int deQueue(CQueue cq) { if (cq .front == null) { System.out.printf ('Queue is empty!!'); return Integer.MIN_VALUE; } int value; // Value to be dequeued // the last node to be deleted if (cq.front == cq.rear) { value = cq.front.data; cq.front = null; cq.rear = null; } else { // There are more than one nodes Node temp = cq.front; value = temp.data; cq.front = cq.front.link; cq.rear.link= cq.front; } return value ; } // display the elements of Circular Queue static void displayQueue( CQueue cq) { Node temp = cq.front; while (temp.link != cq.front) { System.out.printf('%d ', temp.data); temp = temp.link; } System.out.printf('%d', temp.data); } /* main program */ public static void main(String args()) { // Create a queue and initialize front and rear CQueue cq = new CQueue(); cq.front = cq.rear = null; // Insert/enqueue elements in Circular Queue enQueue(cq, 2); enQueue(cq, 4); enQueue(cq, 6); System.out.print('
Circular Queue elements after Enqueue Operation:'); // Display elements in Circular Queue displayQueue(cq); // Delete/dequeue elements from Circular Queue System.out.printf('
Dequeued Item = %d', deQueue(cq)); System.out.printf('
Dequeued Item = %d', deQueue(cq)); System.out.print('
Circular Queue elements after Dequeue Operation:'); displayQueue(cq); enQueue(cq, 8); enQueue(cq, 10); System.out.print('
Circular Queue elements after second Enqueue Operation:'); displayQueue(cq); } } Излаз:
Резултат горњег програма је сличан претходном програму.
Апликације
Размотримо неке од примена кружног реда.
- ЦПУ заказивање: Процес оперативног система који захтева да се догоди неки догађај или да би се неки други процеси довршили за извршење често одржава у кружном реду тако да се извршавају један за другим када су испуњени сви услови или када се догоде сви догађаји.
- Управљање меморијом: Коришћење уобичајених редова троши меморијски простор као што је већ поменуто у нашој горњој дискусији. Коришћење кружног реда за управљање меморијом корисно је за оптимално коришћење меморије.
- Компјутерски контролисан систем саобраћајних сигнала: Компјутеризовани саобраћајни сигнали се често додају у кружни ред тако да се понављају након истека наведеног временског интервала.
Закључак
Кружни редови поправљају главни недостатак нормалног реда у којем не можемо уметнути елементе када је задњи показивач на крају реда, чак и када бришемо елементе и простор се испразни. У кружном реду, елементи су поређани кружно, тако да се простор уопште не троши.
Такође смо видели главне операције кружног реда. Кружни редови су углавном корисни у сврхе распоређивања и за апликације као што су системи саобраћајне сигнализације у којима се сигнали ужарено закрећу.
ц ++ питања и одговори
У нашем следећем упутству научићемо о двоструким редовима који се једноставно називају „декуе“.
=> Посетите овде да бисте научили Ц ++ из огреботина
Препоручено читање
- Структура података у реду у Ц ++ са илустрацијом
- Структура података приоритетног реда у Ц ++ са илустрацијом
- Структура података кружно повезане листе на Ц ++ са илустрацијом
- Дата Март Туториал - Врсте, примери и примена Дата Март
- Структура података стека у Ц ++ са илустрацијом
- Примери рударства података: Најчешћа примена рударства података 2021
- Структура података бинарног стабла у језику Ц ++
- Редослед приоритета у СТЛ-у
