ВВЕДЕННЯ ТА РЕАЛІЗАЦІЯ МАСИВУ ЧЕРГИ

Подібна до черги — це лінійна структура даних, яка дотримується певного порядку, у якому виконуються операції для зберігання даних. Порядок: першим прийшов, першим вийшов (FIFO) . Можна уявити собі чергу як чергу людей, які чекають отримати щось у послідовному порядку, який починається з початку черги. Це впорядкований список, у якому вставки виконуються з одного кінця, відомого як задня частина, а видалення виконуються з іншого кінця, відомого як передній. Хорошим прикладом черги є будь-яка черга споживачів для ресурсу, де споживач, який був першим, обслуговується першим.
Різниця між стеками та чергами полягає у видаленні. У стеку ми видаляємо елемент, доданий останнім; у черзі ми видаляємо елемент, доданий останнім часом.

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

Структура даних черги

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

enqueue(): вставляє елемент у кінець черги, тобто в задній кінець. dequeue(): Ця операція видаляє та повертає елемент, який знаходиться на передньому кінці черги. front(): Ця операція повертає елемент у передній частині, не видаляючи його. rear(): ця операція повертає елемент у задній частині, не видаляючи його. isEmpty(): Ця операція вказує, порожня черга чи ні. isFull(): ця операція вказує, чи заповнена черга чи ні. size(): ця операція повертає розмір черги, тобто загальну кількість елементів, які вона містить.

Типи черг:

Кругова черга : У кільцевій черзі елемент черги діє як кругове кільце. Робота циклічної черги подібна до лінійної черги, за винятком того, що останній елемент з’єднаний з першим елементом. Його перевага полягає в тому, що пам'ять використовується краще. Це пояснюється тим, що якщо є порожнє місце, тобто якщо в певній позиції черги немає жодного елемента, то елемент можна легко додати в цю позицію за допомогою модуля ємності ( %n ).
Пріоритетна черга : Ця черга є особливим типом черги. Його особливість полягає в тому, що він розташовує елементи в черзі на основі певного пріоритету. Пріоритет може бути таким, де елемент із найвищим значенням має пріоритет, тому він створює чергу зі зменшенням порядку значень. Пріоритет також може бути таким, що елемент із найнижчим значенням отримує найвищий пріоритет, таким чином, у свою чергу, він створює чергу зі зростаючим порядком значень. У попередньо визначеній черзі пріоритетів C++ надає пріоритет найвищому значенню, тоді як Java надає пріоритет найнижчому значенню.
Відповідно : Дечерга також відома як подвійна черга. Як випливає з назви, це означає, що елемент можна вставити або видалити з обох кінців черги, на відміну від інших черг, у яких це можна зробити лише з одного кінця. Через цю властивість він може не підкорятися властивості First In First Out.

Застосування черги:

Черга використовується, коли речі не потрібно обробити негайно, але їх потрібно обробити Ф спочатку я п Ф спочатку О ут порядок як Пошук спочатку вшир . Ця властивість Queue робить його також корисним у таких сценаріях.

Коли ресурс спільно використовується кількома споживачами. Приклади включають планування ЦП, Дискове планування.

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

Для реалізації черги нам потрібно відстежувати два індекси, передній і задній. Ми ставимо в чергу предмет позаду, а вилучаємо з черги — спереду. Якщо ми просто збільшимо передній і задній індекси, то можуть виникнути проблеми, передній може дійти до кінця масиву. Рішення цієї проблеми полягає в тому, щоб збільшити перед і зад круговим способом.

Кроки для постановки в чергу:

Перевірте, чи заповнена черга
Якщо заповнено, надрукуйте переповнення та вийдіть
Якщо чергу не заповнено, збільште хвіст і додайте елемент

Кроки для вилучення з черги:

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

Нижче наведено програму для реалізації описаної вище операції в черзі

C++

// CPP program for array> // implementation of queue> #include> using> namespace> std;> // A structure to represent a queue> class> Queue {> public>:> >int> front, rear, size;> >unsigned capacity;> >int>* array;> };> // function to create a queue> // of given capacity.> // It initializes size of queue as 0> Queue* createQueue(unsigned capacity)> {> >Queue* queue =>new> Queue();> >queue->ємність = місткість;> >queue->front = queue->size = 0;> >// This is important, see the enqueue> >queue->задній = місткість - 1;> >queue->масив =>new> int>[queue->місткість];> >return> queue;> }> // Queue is full when size> // becomes equal to the capacity> int> isFull(Queue* queue)> {> >return> (queue->size == queue->capacity);> }> // Queue is empty when size is 0> int> isEmpty(Queue* queue)> {> >return> (queue->розмір == 0);> }> // Function to add an item to the queue.> // It changes rear and size> void> enqueue(Queue* queue,>int> item)> {> >if> (isFull(queue))> >return>;> >queue->задній = (черга->задній + 1)> >% queue->місткість;> >queue->array[queue->rear] = item;> >queue->розмір = черга->розмір + 1;> >cout << item <<>

' enqueued to queue
'>

;> }> // Function to remove an item from queue.> // It changes front and size> int> dequeue(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >int> item = queue->масив[черга->передній];> >queue->front = (queue->front + 1)> >% queue->місткість;> >queue->розмір = черга->розмір - 1;> >return> item;> }> // Function to get front of queue> int> front(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->масив[черга->передній];> }> // Function to get rear of queue> int> rear(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[queue->rear];> }> // Driver code> int> main()> {> >Queue* queue = createQueue(1000);> >enqueue(queue, 10);> >enqueue(queue, 20);> >enqueue(queue, 30);> >enqueue(queue, 40);> >cout << dequeue(queue)> ><<>

' dequeued from queue
'>

;> >cout <<>'Front item is '> ><< front(queue) << endl;> >cout <<>'Rear item is '> ><< rear(queue) << endl;> >return> 0;> }> // This code is contributed by rathbhupendra>

C

// C program for array implementation of queue> #include> #include> #include> // A structure to represent a queue> struct> Queue {> >int> front, rear, size;> >unsigned capacity;> >int>* array;> };> // function to create a queue> // of given capacity.> // It initializes size of queue as 0> struct> Queue* createQueue(unsigned capacity)> {> >struct> Queue* queue = (>struct> Queue*)>malloc>(> >sizeof>(>struct> Queue));> >queue->ємність = місткість;> >queue->front = queue->size = 0;> >// This is important, see the enqueue> >queue->задній = місткість - 1;> >queue->масив = (>int>*)>malloc>(> >queue->місткість *>sizeof>(>int>));> >return> queue;> }> // Queue is full when size becomes> // equal to the capacity> int> isFull(>struct> Queue* queue)> {> >return> (queue->size == queue->capacity);> }> // Queue is empty when size is 0> int> isEmpty(>struct> Queue* queue)> {> >return> (queue->розмір == 0);> }> // Function to add an item to the queue.> // It changes rear and size> void> enqueue(>struct> Queue* queue,>int> item)> {> >if> (isFull(queue))> >return>;> >queue->задній = (черга->задній + 1)> >% queue->місткість;> >queue->array[queue->rear] = item;> >queue->розмір = черга->розмір + 1;> >printf>(>

'%d enqueued to queue
'>

, item);> }> // Function to remove an item from queue.> // It changes front and size> int> dequeue(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >int> item = queue->array[queue->front];> >queue->front = (queue->front + 1)> >% queue->місткість;> >queue->розмір = черга->розмір - 1;> >return> item;> }> // Function to get front of queue> int> front(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[queue->front];> }> // Function to get rear of queue> int> rear(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[queue->rear];> }> // Driver program to test above functions./> int> main()> {> >struct> Queue* queue = createQueue(1000);> >enqueue(queue, 10);> >enqueue(queue, 20);> >enqueue(queue, 30);> >enqueue(queue, 40);> >printf>(>

'%d dequeued from queue

'>

,> >dequeue(queue));> >printf>(>

'Front item is %d
'>

, front(queue));> >printf>(>

'Rear item is %d
'>

, rear(queue));> >return> 0;> }>

Java

// Java program for array> // implementation of queue> // A class to represent a queue> class> Queue {> >int> front, rear, size;> >int> capacity;> >int> array[];> >public> Queue(>int> capacity)> >{> >this>.capacity = capacity;> >front =>this>.size =>0>;> >rear = capacity ->1>;> >array =>new> int>[>this>.capacity];> >}> >// Queue is full when size becomes> >// equal to the capacity> >boolean> isFull(Queue queue)> >{> >return> (queue.size == queue.capacity);> >}> >// Queue is empty when size is 0> >boolean> isEmpty(Queue queue)> >{> >return> (queue.size ==>0>);> >}> >// Method to add an item to the queue.> >// It changes rear and size> >void> enqueue(>int> item)> >{> >if> (isFull(>this>))> >return>;> >this>.rear = (>this>.rear +>1>)> >%>this>.capacity;> >this>.array[>this>.rear] = item;> >this>.size =>this>.size +>1>;> >System.out.println(item> >+>' enqueued to queue'>);> >}> >// Method to remove an item from queue.> >// It changes front and size> >int> dequeue()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >int> item =>this>.array[>this>.front];> >this>.front = (>this>.front +>1>)> >%>this>.capacity;> >this>.size =>this>.size ->1>;> >return> item;> >}> >// Method to get front of queue> >int> front()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >return> this>.array[>this>.front];> >}> >// Method to get rear of queue> >int> rear()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >return> this>.array[>this>.rear];> >}> }> // Driver class> public> class> Test {> >public> static> void> main(String[] args)> >{> >Queue queue =>new> Queue(>1000>);> >queue.enqueue(>10>);> >queue.enqueue(>20>);> >queue.enqueue(>30>);> >queue.enqueue(>40>);> >System.out.println(queue.dequeue()> >+>

' dequeued from queue
'>

);> >System.out.println(>'Front item is '> >+ queue.front());> >System.out.println(>'Rear item is '> >+ queue.rear());> >}> }> // This code is contributed by Gaurav Miglani>

списки java

Python3

# Python3 program for array implementation of queue> # Class Queue to represent a queue> class> Queue:> ># __init__ function> >def> __init__(>self>, capacity):> >self>.front>=> self>.size>=> 0> >self>.rear>=> capacity>->1> >self>.Q>=> [>None>]>*>capacity> >self>.capacity>=> capacity> > ># Queue is full when size becomes> ># equal to the capacity> >def> isFull(>self>):> >return> self>.size>=>=> self>.capacity> > ># Queue is empty when size is 0> >def> isEmpty(>self>):> >return> self>.size>=>=> 0> ># Function to add an item to the queue.> ># It changes rear and size> >def> EnQueue(>self>, item):> >if> self>.isFull():> >print>(>'Full'>)> >return> >self>.rear>=> (>self>.rear>+> 1>)>%> (>self>.capacity)> >self>.Q[>self>.rear]>=> item> >self>.size>=> self>.size>+> 1> >print>(>'% s enqueued to queue'> %> str>(item))> ># Function to remove an item from queue.> ># It changes front and size> >def> DeQueue(>self>):> >if> self>.isEmpty():> >print>(>'Empty'>)> >return> > >print>(>'% s dequeued from queue'> %> str>(>self>.Q[>self>.front]))> >self>.front>=> (>self>.front>+> 1>)>%> (>self>.capacity)> >self>.size>=> self>.size>->1> > ># Function to get front of queue> >def> que_front(>self>):> >if> self>.isEmpty():> >print>(>'Queue is empty'>)> >print>(>'Front item is'>,>self>.Q[>self>.front])> > ># Function to get rear of queue> >def> que_rear(>self>):> >if> self>.isEmpty():> >print>(>'Queue is empty'>)> >print>(>'Rear item is'>,>self>.Q[>self>.rear])> # Driver Code> if> __name__>=>=> '__main__'>:> >queue>=> Queue(>30>)> >queue.EnQueue(>10>)> >queue.EnQueue(>20>)> >queue.EnQueue(>30>)> >queue.EnQueue(>40>)> >queue.DeQueue()> >queue.que_front()> >queue.que_rear()>

C#

// C# program for array implementation of queue> using> System;> namespace> GeeksForGeeks {> // A class to represent a linearqueue> class> Queue {> >private> int>[] ele;> >private> int> front;> >private> int> rear;> >private> int> max;> >public> Queue(>int> size)> >{> >ele =>new> int>[size];> >front = 0;> >rear = -1;> >max = size;> >}> >// Function to add an item to the queue.> >// It changes rear and size> >public> void> enqueue(>int> item)> >{> >if> (rear == max - 1) {> >Console.WriteLine(>'Queue Overflow'>);> >return>;> >}> >else> {> >ele[++rear] = item;> >}> >}> >// Function to remove an item from queue.> >// It changes front and size> >public> int> dequeue()> >{> >if> (front == rear + 1) {> >Console.WriteLine(>'Queue is Empty'>);> >return> -1;> >}> >else> {> >Console.WriteLine(ele[front] +>' dequeued from queue'>);> >int> p = ele[front++];> >Console.WriteLine();> >Console.WriteLine(>'Front item is {0}'>, ele[front]);> >Console.WriteLine(>'Rear item is {0} '>, ele[rear]);> >return> p;> >}> >}> >// Function to print queue.> >public> void> printQueue()> >{> >if> (front == rear + 1) {> >Console.WriteLine(>'Queue is Empty'>);> >return>;> >}> >else> {> >for> (>int> i = front; i <= rear; i++) {> >Console.WriteLine(ele[i] +>' enqueued to queue'>);> >}> >}> >}> }> // Driver code> class> Program {> >static> void> Main()> >{> >Queue Q =>new> Queue(5);> >Q.enqueue(10);> >Q.enqueue(20);> >Q.enqueue(30);> >Q.enqueue(40);> >Q.printQueue();> >Q.dequeue();> >}> }> }>

Javascript

> // Queue class> class Queue> {> >// Array is used to implement a Queue> >constructor()> >{> >this>.items = [];> >}> >isEmpty()> >{> >// return true if the queue is empty.> >return> this>.items.length == 0;> >}> >enqueue(element)> >{> >// adding element to the queue> >this>.items.push(element);> >document.write(element +>' enqueued to queue '>);> >}> >dequeue()> >{> >// removing element from the queue> >// returns underflow when called> >// on empty queue> >if>(>this>.isEmpty())> >return> 'Underflow '>;> >return> this>.items.shift();> >}> >front()> >{> >// returns the Front element of> >// the queue without removing it.> >if>(>this>.isEmpty())> >return> 'No elements in Queue '>;> >return> this>.items[0];> >}> >rear()> >{> >// returns the Rear element of> >// the queue without removing it.> >if>(>this>.isEmpty())> >return> 'No elements in Queue '>;> >return> this>.items[>this>.items.length-1];> >}> }> // creating object for queue class> var> queue =>new> Queue();> // Adding elements to the queue> queue.enqueue(10);> queue.enqueue(20);> queue.enqueue(30);> queue.enqueue(40);> // queue contains [10, 20, 30, 40]> // removes 10> document.write(queue.dequeue() +>' dequeued from queue '>);> // queue contains [20, 30, 40]> // Front is now 20> document.write(>'Front item is '> + queue.front() +>' '>);> // printing the rear element> // Rear is 40> document.write(>'Rear item is '> + queue.rear() +>' '>);> // This code is contributed by Susobhan Akhuli> >

bash else if

Вихід

10 enqueued to queue 20 enqueued to queue 30 enqueued to queue 40 enqueued to queue 10 dequeued from queue Front item is 20 Rear item is 40>

Аналіз складності:

Часова складність

Операції	Складність
Поставити в чергу (вставлення)	О(1)
Deque (видалення)	О(1)
Спереду (отримати спереду)	О(1)
Задній (Отримати задній)	О(1)
IsFull (перевірка черги заповнена чи ні)	О(1)
IsEmpty (Черга перевірки порожня чи ні)	О(1)

Переваги реалізації масиву:

Легко реалізувати.
Великим обсягом даних можна легко й ефективно керувати.
Такі операції, як вставка та видалення, можна виконувати з легкістю, оскільки вони дотримуються правила «першим прийшов, першим вийшов».

Недоліки реалізації масиву:

Статична структура даних, фіксований розмір.
Якщо черга містить велику кількість операцій постановки в чергу та вилучення з черги, у певний момент (у разі лінійного збільшення переднього та заднього індексів) ми можемо не мати змоги вставити елементи в чергу, навіть якщо черга порожня (цієї проблеми можна уникнути за допомогою циклічної черги).
Максимальний розмір черги потрібно визначити заздалегідь.

TechCodeview