c circular queue data structure
Този урок за С ++ Структура на данните за кръгова опашка обяснява какво е кръгова опашка, кои са основните операции заедно с внедряването и приложенията:
Кръговата опашка е продължение на основната опашка, която обсъдихме по-рано. Известен е още като „Ring buffer“.
Какво представлява Circular Queue в C ++?
Кръговата опашка е линейна структура от данни, която се използва за съхраняване на елементи от данни. Той изпълнява операции, като следва подхода FIFO (First In, First Out) и последната позиция в опашката е свързана обратно към първата позиция, за да образува кръг.
=> Потърсете тук цялата серия за обучение на C ++
Какво ще научите:
Кръгова опашка в C ++
Следващата диаграма показва кръгова опашка.
Горното изображение показва кръгла структура от данни с размер 10. Първите шест елемента вече са в опашката и виждаме, че първата позиция и последната позиция са обединени. Поради тази подредба пространството не се губи, както се случва в линейна опашка.
как се отваря торент файл
В линейна опашка, след като опашката е пълна, ние изтриваме елементите от друг край и състоянието на опашката все още се показва като пълно и не можем да вмъкнем повече елементи.
В кръговата опашка, когато опашката е пълна и когато премахнем елементи отпред, тъй като последната и първата позиция са свързани, можем да вмъкнем елементите отзад, които бяха освободени, като изтрием елемента.
В следващия раздел ще научим за основните операции на кръговата опашка.
Основни операции
Някои от основните операции на кръговата опашка са както следва:
Отпред: Връща предната позиция в кръговата опашка.
Задна част: Връща задната позиция в кръговата опашка.
Опашка: Enqueue (стойност) се използва за вмъкване на елемент в кръговата опашка. Елементът винаги се вмъква в задния край на опашката.
Следваме следната последователност от стъпки, за да вмъкнем нов елемент в кръговата опашка.
# 1) Проверете дали кръговата опашка е пълна: тест ((отзад == РАЗМЕР-1 && отпред == 0) || (отзад == отпред-1)), където „РАЗМЕР“ е размерът на кръговата опашка.
# две) Ако кръговата опашка е пълна, тя показва съобщение като „Опашката е пълна“. Ако опашката не е пълна, проверете дали (отзад == РАЗМЕР - 1 && отпред! = 0). Ако е вярно, задайте заден = 0 и вмъкнете елемент.
Dequeue: Функцията Dequeue се използва за изтриване на елемент от опашката. В кръговата опашка елементът винаги се изтрива от предния край. По-долу е дадена последователността за операция по деквей в кръгова опашка.
Стъпки:
# 1) Проверете дали кръговата опашка е Празна: проверете дали (отпред == - 1).
# две) Ако е празно, покажете съобщението „Опашката е празна“. Ако опашката не е празна, изпълнете стъпка 3.
# 3) Проверете дали (отпред == отзад). Ако е вярно, задайте front = back = -1, иначе проверете дали (front == size-1), ако е вярно, тогава задайте front = 0 и върнете елемента.
как да отворите bin файл
Илюстрация
В този раздел ще преминем през подробна илюстрация на добавяне / премахване на елементи в кръговата опашка.
Помислете за следната кръгова опашка от 5 елемента, както е показано по-долу:
След това вмъкваме елемент 1 в опашката.
След това вмъкваме елемент със стойност 3.
Когато вмъкнем елементите, за да направим опашката пълна, представянето ще бъде както е показано по-долу.
Сега изтриваме двата елемента, т.е. т. 1 и т. 3 от опашката, както е показано по-долу.
След това вмъкваме или поставяме в опашка елемент 11 в кръговата опашка, както е показано по-долу.
Отново нека вмъкнем елемент 13 в кръговата опашка. Опашката ще изглежда както е показано по-долу.
Виждаме, че в кръговата опашка преместваме или вмъкваме елементи в кръг. Следователно можем да консумираме цялото пространство на опашката, докато се запълни.
Изпълнение
Нека да приложим кръговата опашка, използвайки C ++.
#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< По-горе е показан изходът от операции с кръгови опашки. Първо добавяме елементите и след това премахваме или премахваме два елемента. След това вмъкваме или поставяме в опашка още три елемента в кръговата опашка. Виждаме, че за разлика от линейната опашка, елементите се добавят в края на опашката.
Внедряване на свързан списък
Нека сега обсъдим изпълнението на свързания списък на кръгова опашка. По-долу е дадено изпълнението на свързания списък на кръговата опашка в C ++. Имайте предвид, че използваме struct, за да представим всеки възел. Операциите са същите като обсъдените по-рано, с изключение на това, че в този случай трябва да ги изпълним по отношение на свързаните възлови списъци.
Изходът показва кръговата опашка след операция за опашка, отмяна и след втората операция за опашка.
#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: '< Изход:
Следващата реализация е Java програма за демонстриране на кръгова опашка, използвайки свързания списък.
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); } } Изход:
Резултатът от горната програма е подобен на предишната програма.
Приложения
Нека обсъдим някои от приложенията на кръговата опашка.
- Планиране на процесора: Процесът на операционната система, който изисква да се случи някакво събитие или някои други процеси да завършат за изпълнение, често се поддържа в кръгова опашка, така че те да се изпълняват един след друг, когато са изпълнени всички условия или когато настъпят всички събития.
- Управление на паметта: Използването на обикновени опашки губи място в паметта, както вече беше споменато в горната ни дискусия. Използването на кръгла опашка за управление на паметта е полезно за оптималното използване на паметта.
- Компютърно контролирана система за пътна сигнализация: Компютърните сигнали за трафика често се добавят към кръгова опашка, така че да се повтарят след изтичане на указания интервал от време.
Заключение
Кръговите опашки коригират основния недостатък на нормалната опашка, при която не можем да вмъкнем елементи, когато задният указател е в края на опашката, дори когато изтрием елементите и пространството се изпразни. В кръгова опашка елементите са подредени по кръгов начин, така че изобщо да не се губи място.
Виждали сме и основните операции на кръговата опашка. Кръговите опашки са предимно полезни за целите на планирането и приложения като системи за пътна сигнализация, при които сигналите светят на завой.
какво е бета тестване при тестване на софтуер
В следващия урок ще научим за двойните опашки, които просто се наричат „deque“.
=> Посетете тук, за да научите C ++ от нулата
Препоръчително четене
- Структура на данните за опашката в C ++ с илюстрация
- Структура на данните за приоритетна опашка в C ++ с илюстрация
- Структура на данните от циркулярно свързан списък в C ++ с илюстрация
- Data Mart Урок - Видове, примери и изпълнение на Data Mart
- Структура на данните за стека в C ++ с илюстрация
- Примери за извличане на данни: Най-често срещаните приложения за извличане на данни 2021
- Структура на данните на двоичното дърво в C ++
- Приоритетна опашка в STL
