logo

TechCodeview

Deque (або двостороння черга)

У цій статті ми обговоримо двосторонню чергу або deque. Спочатку ми повинні побачити короткий опис черги.

Що таке черга?

Черга — це структура даних, у якій все, що з’являється першим, і вийде першим, і вона відповідає політиці FIFO (першим прийшов — першим вийшов). Вставлення в чергу виконується з одного кінця, відомого як задній кінець або хвіст, тоді як видалення виконується з іншого кінця, відомого як передній кінець або голова черги.

трійчаста зима

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

Що таке Deque (або двостороння черга)

Deque розшифровується як Double Ended Queue. Deque — це лінійна структура даних, де операції вставки та видалення виконуються з обох кінців. Можна сказати, що deque є узагальненою версією черги.

Хоча вставлення та видалення в deque можна виконувати з обох сторін, це не відповідає правилу FIFO. Представлення дека дається таким чином:

Deque (або двостороння черга)

Види дек

Є два типи deque -

  • Обмежена черга введення
  • Обмежена черга виведення

Черга з обмеженим введенням

У черзі з обмеженим введенням операцію вставки можна виконати лише з одного кінця, тоді як видалення можна виконати з обох кінців.

Deque (або двостороння черга)

Обмежена черга виведення

У черзі з обмеженим виведенням операцію видалення можна виконати лише з одного кінця, тоді як вставлення можна виконати з обох кінців.

Deque (або двостороння черга)

Операції, що виконуються на deque

Існують наступні операції, які можна застосувати до deque:

  • Вставка спереду
  • Вставка ззаду
  • Видалення спереду
  • Видалення ззаду

Ми також можемо виконувати операції перегляду в deque разом із операціями, перерахованими вище. Завдяки операції peek ми можемо отримати передні та задні елементи дека. Таким чином, на додаток до вищевказаних операцій, наступні операції також підтримуються в deque -

що таке java hashmap
  • Отримайте передній предмет з дека
  • Отримайте задній предмет із дека
  • Перевірте, чи заповнена дека
  • Перевіряє, чи порожня двочерга

Тепер давайте розберемося з операцією, що виконується над deque, на прикладі.

Вставка на передньому кінці

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

  • Якщо черга порожня, і задня, і передня частини ініціалізуються 0. Тепер обидва вказуватимуть на перший елемент.
  • В іншому випадку перевірте положення передньої частини, якщо передня частина менше 1 (передня<1), then reinitialize it by front = n - 1, тобто останній індекс масиву.
Deque (або двостороння черга)

Вставка на задньому кінці

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

  • Якщо черга порожня, і задня, і передня частини ініціалізуються 0. Тепер обидва вказуватимуть на перший елемент.
  • В іншому випадку збільште задню частину на 1. Якщо задня частина має останній індекс (або розмір - 1), то замість збільшення його на 1 ми повинні зробити його рівним 0.
Deque (або двостороння черга)

Видалення на передньому кінці

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

Якщо черга порожня, тобто front = -1, це умова недоповнення, і ми не можемо виконати видалення. Якщо черга не заповнена, елемент можна вставити з інтерфейсу за допомогою наведених нижче умов:

іменування правил java

Якщо дек має лише один елемент, встановіть rear = -1 і front = -1.

Інакше, якщо front знаходиться в кінці (це означає front = size - 1), встановіть front = 0.

вікно.відкрите

Інакше збільште фронт на 1 (тобто фронт = фронт + 1).

Deque (або двостороння черга)

Видалення на задньому кінці

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

Якщо черга порожня, тобто front = -1, це умова недоповнення, і ми не можемо виконати видалення.

Якщо дек має лише один елемент, встановіть rear = -1 і front = -1.

Якщо rear = 0 (rear знаходиться спереду), тоді встановіть rear = n - 1.

Інакше зменшіть задню частину на 1 (або задню частину = задню -1).

Deque (або двостороння черга)

Чек порожній

Ця операція виконується, щоб перевірити, чи двочерга порожня чи ні. Якщо front = -1, це означає, що дві черги порожні.

Чек повний

Ця операція виконується, щоб перевірити, чи заповнена двочерга. Якщо front = rear + 1, або front = 0 і rear = n - 1, це означає, що дек повний.

Часова складність усіх перерахованих вище операцій деке дорівнює O(1), тобто постійна.

Застосування deque

  • Deque можна використовувати і як стек, і як чергу, оскільки він підтримує обидві операції.
  • Deque можна використовувати як засіб перевірки паліндрому, що означає, що якщо ми прочитаємо рядок з обох кінців, рядок буде однаковим.

Реалізація deque

Тепер давайте подивимося реалізацію deque мовою програмування C.

java виходить із циклу 
 #include #define size 5 int deque[size]; int f = -1, r = -1; // insert_front function will insert the value from the front void insert_front(int x) { if((f==0 &amp;&amp; r==size-1) || (f==r+1)) { printf(&apos;Overflow&apos;); } else if((f==-1) &amp;&amp; (r==-1)) { f=r=0; deque[f]=x; } else if(f==0) { f=size-1; deque[f]=x; } else { f=f-1; deque[f]=x; } } // insert_rear function will insert the value from the rear void insert_rear(int x) { if((f==0 &amp;&amp; r==size-1) || (f==r+1)) { printf(&apos;Overflow&apos;); } else if((f==-1) &amp;&amp; (r==-1)) { r=0; deque[r]=x; } else if(r==size-1) { r=0; deque[r]=x; } else { r++; deque[r]=x; } } // display function prints all the value of deque. void display() { int i=f; printf(&apos;
Elements in a deque are: &apos;); while(i!=r) { printf(&apos;%d &apos;,deque[i]); i=(i+1)%size; } printf(&apos;%d&apos;,deque[r]); } // getfront function retrieves the first value of the deque. void getfront() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else { printf(&apos;
The value of the element at front is: %d&apos;, deque[f]); } } // getrear function retrieves the last value of the deque. void getrear() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else { printf(&apos;
The value of the element at rear is %d&apos;, deque[r]); } } // delete_front() function deletes the element from the front void delete_front() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else if(f==r) { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=-1; r=-1; } else if(f==(size-1)) { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=0; } else { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=f+1; } } // delete_rear() function deletes the element from the rear void delete_rear() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else if(f==r) { printf(&apos;
The deleted element is %d&apos;, deque[r]); f=-1; r=-1; } else if(r==0) { printf(&apos;
The deleted element is %d&apos;, deque[r]); r=size-1; } else { printf(&apos;
The deleted element is %d&apos;, deque[r]); r=r-1; } } int main() { insert_front(20); insert_front(10); insert_rear(30); insert_rear(50); insert_rear(80); display(); // Calling the display function to retrieve the values of deque getfront(); // Retrieve the value at front-end getrear(); // Retrieve the value at rear-end delete_front(); delete_rear(); display(); // calling display function to retrieve values after deletion return 0; }

Вихід:

Deque (або двостороння черга)

Отже, це все про статтю. Сподіваюся, стаття буде для вас корисною та пізнавальною.