c circular queue data structure
Цей підручник зі структури даних кругової черги C ++ пояснює, що таке кругова черга, які основні операції разом із впровадженням та програмами:
Кругова черга - це продовження основної черги, про яку ми вже говорили раніше. Він також відомий як 'кільцевий буфер'.
Що таке кругова черга в C ++?
Кругова черга - це лінійна структура даних, яка використовується для зберігання елементів даних. Він виконує операції, дотримуючись підходу FIFO (First In, First Out), і остання позиція в черзі підключається назад до першої позиції, утворюючи коло.
=> Шукайте тут цілу серію навчальних програм C ++
Що ви дізнаєтесь:
Кругова черга в C ++
На наступній схемі показана кругова черга.
Наведене зображення показує кругову структуру даних розміром 10. Перші шість елементів уже в черзі, і ми бачимо, що перша позиція та остання позиція об’єднані. Завдяки такому розташуванню простір не втрачається даремно, як це відбувається в лінійній черзі.
хто найкращий постачальник електронної пошти
У лінійній черзі після заповнення черги ми видаляємо елементи з іншого кінця, а статус черги все ще відображається як заповнений, і ми не можемо вставити більше елементів.
У круговій черзі, коли черга заповнена, і коли ми видаляємо елементи спереду, оскільки з’єднано останнє та перше положення, ми можемо вставити елементи ззаду, які звільнилися, видаливши елемент.
У наступному розділі ми дізнаємося про основні операції кругової черги.
Основні операції
Деякі основні операції кругової черги такі:
Спереду: Повертає переднє положення в круговій черзі.
Задня: Повертає заднє положення в круговій черзі.
Черга: Enqueue (значення) використовується для вставки елемента в кругову чергу. Елемент завжди вставляється в задній кінець черги.
Ми виконуємо наступну послідовність кроків, щоб вставити новий елемент у кругову чергу.
# 1) Перевірте, чи кругова черга заповнена: test ((ззаду == РОЗМІР-1 && спереду == 0) || (ззаду == спереду-1)), де ‘SIZE’ - це розмір кругової черги.
# два) Якщо кругова черга заповнена, тоді відображається повідомлення “Черга заповнена”. Якщо черга не заповнена, перевірте, якщо (ззаду == РОЗМІР - 1 && спереду! = 0). Якщо це правда, тоді встановіть тил = 0 і вставте елемент.
Зменшення черги: Функція зняття черги використовується для видалення елемента з черги. У круговій черзі елемент завжди видаляється з інтерфейсу. Нижче наведено послідовність операцій із вилучення черги в круговій черзі.
Кроки:
найкращий конвертер YouTube в mp3 безкоштовно
# 1) Перевірте, чи кругова черга порожня: перевірте, якщо (спереду == - 1).
# два) Якщо він порожній, виведіть повідомлення “Черга порожня”. Якщо черга не порожня, виконайте крок 3.
# 3) Перевірте, якщо (спереду == ззаду). Якщо це істина, то встановіть front = rear = -1, інакше перевірте, якщо (front == size-1), якщо це істина, встановіть front = 0 і поверніть елемент.
Ілюстрація
У цьому розділі ми розглянемо докладну ілюстрацію додавання / видалення елементів у круговій черзі.
Розглянемо наступну кругову чергу з 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); } } Вихід:
Результат роботи вищезазначеної програми подібний до попередньої програми.
Програми
Давайте обговоримо деякі застосування кругової черги.
- Планування процесора: Процес операційної системи, який вимагає виникнення якоїсь події або завершення деяких інших процесів для виконання, часто ведеться в круговій черзі, щоб вони виконувались один за одним, коли виконуються всі умови або коли відбуваються всі події.
- Управління пам'яттю: Використання звичайних черг витрачає простір пам'яті, як уже згадувалося в нашому вище обговоренні. Використання кругової черги для управління пам’яттю корисно для оптимального використання пам’яті.
- Комп’ютерна система керування дорожнім сигналом: Комп’ютеризовані сигнали дорожнього руху часто додаються до кругової черги, щоб вони повторювались після закінчення зазначеного інтервалу часу.
Висновок
Кругові черги виправляють основний недолік звичайної черги, коли ми не можемо вставляти елементи, коли задній вказівник знаходиться в кінці черги, навіть коли ми видаляємо елементи, і місце звільняється. У круговій черзі елементи розташовані круговим чином, так що простір не витрачається взагалі.
Ми також бачили основні операції кругової черги. Кругові черги в основному корисні для цілей планування та таких додатків, як системи сигналів дорожнього руху, де сигнали світяться по черзі.
як використовувати css селектор в селені - -
У нашому наступному навчальному посібнику ми дізнаємось про подвійні черги, які просто називаються “deque”.
=> Завітайте сюди, щоб вивчити C ++ з нуля
Рекомендована література
- Структура даних черги в C ++ з ілюстрацією
- Структура даних черги пріоритетів у C ++ з ілюстрацією
- Структура даних кругового зв’язаного списку на C ++ з ілюстрацією
- Підручник з Data Mart - типи, приклади та реалізація Data Mart
- Структура даних стеку в C ++ з ілюстрацією
- Приклади інтелектуального аналізу даних: Найпоширеніші програми інтелектуального аналізу даних 2021
- Структура даних двійкового дерева в C ++
- Черга пріоритетів у STL
