Меню

Структура даних черги в C ++ з ілюстрацією

queue data structure c with illustration

Спробуйте Наш Інструмент Для Усунення Проблем

Короткий вступ до черги в C ++ з ілюстрацією.

Черга - це основна структура даних, подібна до стека. На відміну від стека, який використовує підхід LIFO, в черзі використовується підхід FIFO (перший вхід, перший вихід). При такому підході перший елемент, який додається до черги, є першим елементом, який потрібно видалити з черги. Так само, як Stack, черга також є лінійною структурою даних.

різниця між спритним та водоспадним тестуванням

За реальною аналогією ми можемо уявити собі чергу в автобусі, де пасажири чекають на автобус у черзі чи на лінії. Перший пасажир в черзі заходить в автобус першим, оскільки пасажир виявляється тим, хто прийшов першим.

=> Ознайомтесь з Популярною серією навчальних програм C ++ тут.

Черга в C ++

Що ви дізнаєтесь:

Черга в C ++

З точки зору програмного забезпечення, чергу можна розглядати як набір або набір елементів, як показано нижче. Елементи розташовані лінійно.

черга

У нас є два кінці, тобто „передній” та „задній” черги. Коли черга порожня, для обох покажчиків встановлено значення -1.

Кінцевий вказівник “задній” - це місце, звідки елементи вставляються в чергу. Операція додавання / вставки елементів у чергу називається “enqueue”.

Кінцевий вказівник “передній” - це місце, звідки елементи видаляються з черги. Операція з видалення / видалення елементів із черги називається “вилученням із черги”.

Коли значення заднього вказівника має розмір-1, тоді ми говоримо, що черга заповнена. Коли фронт нульовий, тоді черга порожня.

Основні операції

Структура даних черги включає такі операції:

  • Черга: Додає елемент до черги. Додавання елемента до черги завжди робиться в задній частині черги.
  • DeQueue: Видаляє елемент із черги. Елемент вилучається або виводиться з черги завжди з передньої частини черги.
  • пусто: Перевіряє, чи не порожня черга.
  • isFull: Перевіряє, чи черга заповнена.
  • заглянути: Отримує елемент в передній частині черги, не видаляючи його.

Очередь

У цьому процесі виконуються такі дії:

  • Перевірте, чи черга заповнена.
  • Якщо заповнено, видайте помилку переповнення та вийдіть.
  • В іншому випадку збільшуйте ‘задній’.
  • Додайте елемент до місця, на яке вказує „тил”.
  • Повернути успіх.

Зняти чергу

Операція зняття черги складається з наступних етапів:

  • Перевірте, чи не порожня черга.
  • Якщо порожнє, відобразіть помилку недоливу та вийдіть.
  • В іншому випадку на елемент доступу вказує «спереду».
  • Збільште 'фронт', щоб вказати на наступні доступні дані.
  • Повернути успіх.

Далі ми побачимо докладну ілюстрацію операцій вставки та видалення в черзі.

Ілюстрація

ілюстрація вставки та видалення в черзі

Це порожня черга, і, отже, ми маємо тил і порожній значення -1.

Далі ми додаємо 1 до черги, і в результаті задній вказівник рухається вперед на одне місце.

Операція EnQueue

На наступному малюнку ми додаємо елемент 2 до черги, пересуваючи задній вказівник вперед на ще один крок.

додати елемент 2 до черги

На наступному малюнку ми додаємо елемент 3 і переміщуємо задній покажчик на 1.

додати елемент 3

На даний момент задній вказівник має значення 2, тоді як передній вказівник знаходиться на 0гоРозташування.

Далі ми видаляємо елемент, на який вказує передній вказівник. Оскільки передній вказівник знаходиться на 0, елемент, який видаляється, дорівнює 1.

Операція DeQueue

Таким чином, перший елемент, введений в чергу, тобто 1, буває першим елементом, вилученим з черги. В результаті, після першої черги передній покажчик тепер буде переміщений вперед t0 до наступного розташування, яке дорівнює 1.

Реалізація масиву для черги

Давайте реалізуємо структуру даних черги за допомогою C ++.

#include #define MAX_SIZE 5 using namespace std; class Queue { private: int myqueue(MAX_SIZE), front, rear; public: Queue(){ front = -1; rear = -1; } boolisFull(){ if(front == 0 && rear == MAX_SIZE - 1){ return true; } return false; } boolisEmpty(){ if(front == -1) return true; else return false; } void enQueue(int value){ if(isFull()){ cout << endl<< 'Queue is full!!'; } else { if(front == -1) front = 0; rear++; myqueue(rear) = value; cout << value << ' '; } } int deQueue(){ int value; if(isEmpty()){ cout << 'Queue is empty!!' <= rear){ //only one element in queue front = -1; rear = -1; } else { front++; } cout << endl < ' << value << ' from myqueue'; return(value); } } /* Function to display elements of Queue */ void displayQueue() { int i; if(isEmpty()) { cout << endl << 'Queue is Empty!!' << endl; } else { cout << endl << 'Front = ' << front; cout << endl << 'Queue elements : '; for(i=front; i<=rear; i++) cout << myqueue(i) << ' '; cout << endl << 'Rear = ' << rear << endl; } } }; int main() { Queue myq; myq.deQueue(); //deQueue cout<<'Queue created:'< queue is full myq.enQueue(60); myq.displayQueue(); //deQueue =>removes 10 myq.deQueue(); //queue after dequeue myq.displayQueue(); return 0; }

Вихід:

Черга порожня !!
Створена черга:
10 20 30 40 50
Черга заповнена !!
Спереду = 0
Елементи черги: 10 20 30 40 50
Задній = 4

Видалено => 10 з моєї черги
Спереду = 1
Елементи черги: 20 30 40 50
Задній = 4

Вищевказана реалізація показує чергу, представлену у вигляді масиву. Вказуємо max_size для масиву. Ми також визначаємо операції enqueue і dequeue, а також операції isFull та isEmpty.

Нижче наведено реалізацію Java структури даних черги.

// A class representing a queue class Queue { int front, rear, size; int max_size; int myqueue(); public Queue(int max_size) { this.max_size = max_size; front = this.size = 0; rear = max_size - 1; myqueue = new int(this.max_size); } //if size = max_size , queue is full boolean isFull(Queue queue) { return (queue.size == queue.max_size); } // size = 0, queue is empty boolean isEmpty(Queue queue) { return (queue.size == 0); } // enqueue - add an element to the queue void enqueue( int item) { if (isFull(this)) return; this.rear = (this.rear + 1)%this.max_size; this.myqueue(this.rear) = item; this.size = this.size + 1; System.out.print(item + ' ' ); } // dequeue - remove an elment from the queue int dequeue() { if (isEmpty(this)) return Integer.MIN_VALUE; int item = this.myqueue(this.front); this.front = (this.front + 1)%this.max_size; this.size = this.size - 1; return item; } // move to front of the queue int front() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.myqueue(this.front); } // move to the rear of the queue int rear() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.myqueue(this.rear); } } // main class class Main { public static void main(String() args) { Queue queue = new Queue(1000); System.out.println('Queue created as:'); queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); queue.enqueue(40); System.out.println(' Element ' + queue.dequeue() + ' dequeued from queue '); System.out.println('Front item is ' + queue.front()); System.out.println('Rear item is ' + queue.rear()); } }

Вихід:

Черга створена як:
10 20 30 40
Елемент 10 виведено з черги

Лицьова деталь - 20
Задній елемент - 40

Вищезазначена реалізація схожа на реалізацію С ++.

Далі, давайте реалізуємо чергу в C ++ за допомогою пов’язаного списку.

Впровадження зв’язаного списку для черги:

#include using namespace std; struct node { int data; struct node *next; }; struct node* front = NULL; struct node* rear = NULL; struct node* temp; void Insert(int val) { if (rear == NULL) { rear = new node; rear->next = NULL; rear->data = val; front = rear; } else { temp=new node; rear->next = temp; temp->data = val; temp->next = NULL; rear = temp; } } void Delete() { temp = front; if (front == NULL) { cout<<'Queue is empty!!'next; cout<<'Element deleted from queue is : '

Вихід:

Черга створена:
10 20 30 40 50
Елемент, видалений з черги: 10
Черга після одного видалення:
20 30 40 50

як використовувати торрентований файл - -

Стек проти Черга

Стеки та черги - це вторинні структури даних, які можна використовувати для зберігання даних. Їх можна запрограмувати, використовуючи основні структури даних, такі як масиви та пов'язані списки. Детально обговоривши обидві структури даних, настав час обговорити основні відмінності між цими двома структурами даних.

СтекиЧерги
Використовує підхід LIFO (Last in, First out).Використовує підхід FIFO (First in, First out).
Елементи додаються або видаляються лише з одного кінця, який називається “Top” стека.Елементи додаються із “заднього” кінця черги та видаляються з “переднього” краю черги.
Основними операціями для стека є “натискання” та “Поп”.Основними операціями для черги є 'чергу' та 'скидання'.
Ми можемо робити всі операції над стеком, підтримуючи лише один вказівник для доступу до верхньої частини стека.У чергах нам потрібно підтримувати два вказівники, один для доступу до передньої частини черги, а другий для доступу до задньої частини черги.
Стек в основному використовується для вирішення рекурсивних задач.Черги використовуються для вирішення проблем, пов’язаних із замовленою обробкою.

Програми черги

Давайте обговоримо різні додатки структури даних черги нижче.

  • Структура даних черги використовується в різних процесорах та плануванні дисків. Тут ми маємо кілька завдань, що вимагають одночасно процесор або диск. Час процесора або диска планується для кожного завдання за допомогою черги.
  • Черга також може бути використана для спулінгу друку, коли кількість завдань друку розміщується в черзі.
  • Обробка переривань у системах реального часу здійснюється за допомогою структури даних черги. Переривання обробляються в порядку їх надходження.
  • Перший за шириною пошук, при якому сусідні вузли дерева обходять перед переходом на наступний рівень, використовує чергу для реалізації.
  • Телефонні системи кол-центру використовують черги для утримання дзвінків, поки представники служби не відповідуть на них.

Загалом, ми можемо сказати, що структура даних черги використовується, коли нам потрібно, щоб ресурси або елементи обслуговувались у тому порядку, в якому вони надходять, тобто First in, First Out.

Висновок

Черга - це структура даних FIFO (First In, First Out), яка в основному використовується у ресурсах, де потрібне планування. Він має два вказівники ззаду і спереду на двох кінцях, і вони використовуються для вставки елемента та вилучення елемента з / з черги відповідно.

У нашому наступному підручнику ми дізнаємось про деякі розширення черги, такі як пріоритетна черга та кругова черга.

=> Дивіться тут, щоб ознайомитися з повним списком підручників з C ++.

Рекомендована література

^