Меню

Двостороння черга (Deque) в C ++ із прикладами

double ended queue c with examples

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

Поглиблений підручник з Deque або двосторонньої черги в C ++. Підручник пояснює, що таке Deque, основні операції, реалізація C ++ та Java та додатки:

Двостороння черга або просто її називають “Deque” - це узагальнена версія Черги.

Різниця між Queue та Deque полягає в тому, що вона не дотримується підходу FIFO (First In, First Out). Друга особливість Deque полягає в тому, що ми можемо вставляти і витягувати елементи як з переднього, так і із заднього кінців.

=> Прочитайте серію навчальних програм Easy C ++

Двостороння черга (Deque) в C ++

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

Класифікація подвійної черги

Деке можна класифікувати наступним чином:

Введення з обмеженим дотиком; У обмеженому введенні видалення може бути здійснено з обох кінців, але вставка може бути зроблена лише в задньому кінці черги.

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

Ми також можемо реалізувати стеки та черги за допомогою deque.

Основні операції дотику

Нижче наведено основні операції, які можна виконувати на деке.

  • вставити спереду: Вставте або додайте предмет в передній частині декаля.
  • insertLast: Вставте або додайте предмет у задній частині деке.
  • deleteFront: Видаліть або видаліть елемент із передньої частини черги.
  • видалити останнє: Видаліть або видаліть елемент із задньої частини черги.
  • getFront: Отримує передній елемент у deque.
  • getLast: Отримує останній елемент у черзі.
  • пусто: Перевіряє, чи не є порожня кришка.
  • isFull: Перевіряє, чи заповнений дек.

та ілюстрації

Порожня деке представлена ​​таким чином:

Повторний підрахунок

найкраще програмне забезпечення для клонування диска windows 10

Далі вставляємо елемент 1 спереду.

Вставте елемент 1 спереду

Тепер ми вставляємо елемент 3 ззаду.

Вставте елемент 3 ззаду

Далі ми додаємо елемент 5 спереду і при збільшенні передніх точок до 4.

Елемент 5 спереду

Потім ми вставляємо елементи 7 ззаду і 9 спереду. Деке буде виглядати, як показано нижче.

елементи 7 ззаду і 9 спереду

Далі видалимо елемент спереду.

Зніміть елемент спереду

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

та впровадження

Впровадження 100 ++ touch

Ми можемо реалізувати deque в C ++ за допомогою масивів, а також пов'язаного списку. Окрім цього, Стандартна бібліотека шаблонів (STL) має клас “deque”, який реалізує всі функції для цієї структури даних.

Реалізація масиву deque була наведена нижче. Оскільки це подвійна черга, для реалізації ми використали кругові масиви.

які всі сайти електронної пошти
#include using namespace std; #define MAX_size 10 // Maximum size of array or Dequeue // Deque class class Deque { int array(MAX_size); int front; int rear; int size; public : Deque(int size) { front = -1; rear = 0; this->size = size; } // Operations on Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); int getFront(); int getRear(); // Check if Deque is full bool isFull()front == rear+1); // Check if Deque is empty bool isEmpty(){ return (front == -1); } }; // Insert an element at front of the deque void Deque::insertfront(int key) { if (isFull()) { cout << 'Overflow!! ' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (front == 0) // front is first position of queue front = size - 1 ; else // decrement front 1 position front = front-1; array(front) = key ; // insert current element into Deque } // insert element at the rear end of deque void Deque ::insertrear(int key) { if (isFull()) { cout << ' Overflow!! ' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (rear == size-1) // rear is at last position of queue rear = 0; else // increment rear by 1 position rear = rear+1; array(rear) = key ; // insert current element into Deque } // Delete element at front of Deque void Deque ::deletefront() { if (isEmpty()) { cout << 'Queue Underflow!! ' << endl; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else // back to initial position if (front == size -1) front = 0; else // remove current front value from Deque;increment front by 1 front = front+1; } // Delete element at rear end of Deque void Deque::deleterear() { if (isEmpty()) { cout << ' Underflow!! ' << endl ; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size-1; else rear = rear-1; } // retrieve front element of Deque int Deque::getFront() { if (isEmpty()) { cout << ' Underflow!! ' << endl; return -1 ; } return array(front); } // retrieve rear element of Deque int Deque::getRear() { if(isEmpty() || rear < 0) { cout << ' Underflow!! ' << endl; return -1 ; } return array(rear); } //main program int main() { Deque dq(5); cout << 'Insert element 1 at rear end '; dq.insertrear(1); cout << 'insert element 3 at rear end '; dq.insertrear(3); cout << 'rear element of deque ' << ' ' << dq.getRear() << endl; dq.deleterear(); cout << 'After deleterear, rear = ' << dq.getRear() << endl; cout << 'inserting element 5 at front end '; dq.insertfront(5); cout << 'front element of deque ' << ' ' << dq.getFront() << endl; dq.deletefront(); cout << 'After deletefront, front = ' << dq.getFront() << endl; return 0; }

Вихід:

Вставте елемент 1 ззаду

вставте елемент 3 ззаду

задній елемент деке 3

Після делетера, тил = 1

вставний елемент 5 на передньому кінці

передній елемент деке 5

Після видалення frontfront, front = 1

і вихід

Перерахунок реалізації Java

Інтерфейс deque в Java 'java.util.Deque' походить від інтерфейсу 'java.util.Queue'. Deque можна використовувати як чергу (First In, First Out) або стек (Last In, First Out). Ці реалізації працюють швидше, ніж пов'язаний список.

Нижче наведена ієрархія інтерфейсу Deque в Java.

Ієрархія інтерфейсу Deque в Java

Потрібно пам’ятати кілька моментів щодо інтерфейсу Deque в Java:

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

Нижче наведено різні методи, підтримувані інтерфейсом Deque:

яке найкраще програмне забезпечення для копіювання DVD
Ні.МетодОпис
7ітератор ()Повертає ітератор для модуля deque.
одиндодати (елемент)Додає елемент до хвоста.
дваaddFirst (елемент)Додає елемент до голови / спереду.
3addLast (елемент)Додає елемент до хвоста / тилу.
4пропозиція (елемент)Додає елемент до хвоста; повертає логічне значення, щоб вказати, чи вставка була успішною.
5offerFirst (елемент)Додає елемент до голови; повертає логічне значення, щоб вказати, чи вставка була успішною.
6offerLast (елемент)Додає елемент до хвоста; повертає логічне значення, щоб вказати, чи вставка була успішною.
8descendingIterator ()Повертає ітератор, який має зворотний порядок для цього дека.
9штовхати (елемент)Додає елемент до головки дека.
10поп (елемент)Видаляє елемент з головки дека і повертає його.
одинадцятьremoveFirst ()Видаляє елемент на чолі дека.
12removeLast ()Видаляє елемент на хвості деке.
13опитування ()Отримує та видаляє перший елемент деке (представлений головкою дека); повертає NULL, якщо параметр порожній.
14опитуванняПерше ()Отримує та видаляє перший елемент цього деке; повертає null, якщо цей параметр порожній.
п’ятнадцятьpollLast ()Отримує та вилучає останній елемент цього деке; повертає null, якщо цей параметр порожній.
16заглянути ()Отримує заголовок (перший елемент deque) черги, представлену цим deque; повертає null, якщо цей параметр порожній.
Примітка: Ця операція не видаляє елемент.
17peekFirst ()Отримує перший елемент цього deque; повертає null, якщо цей параметр порожній.
Примітка: Ця операція не видаляє елемент.
18peekLast ()Отримує останній елемент цього deque або повертає null, якщо цей deque порожній.
Примітка: Ця операція не видаляє елемент.

Наступна реалізація Java демонструє різні операції, обговорені вище.

import java.util.*; class Main { public static void main(String() args) { Deque deque = new LinkedList (); // We can add elements to the queue in various ways deque.add(1); // add to tail deque.addFirst(3); deque.addLast(5); deque.push(7); //add to head deque.offer(9); deque.offerFirst(11); deque.offerLast(13); System.out.println('The deque : ' + deque + ' '); // Iterate through the queue elements. System.out.println('Standard Iterator'); Iterator iterator = deque.iterator(); while (iterator.hasNext()) System.out.print(' ' + iterator.next()); // Reverse order iterator Iterator reverse = deque.descendingIterator(); System.out.println(' Reverse Iterator'); while (reverse.hasNext()) System.out.print(' ' + reverse.next()); // Peek returns the head, without deleting // it from the deque System.out.println(' Peek ' + deque.peek()); System.out.println('After peek: ' + deque); // Pop returns the head, and removes it from // the deque System.out.println(' Pop ' + deque.pop()); System.out.println('After pop: ' + deque); // We can check if a specific element exists // in the deque System.out.println(' Contains element 3?: ' + deque.contains(3)); // We can remove the first / last element. deque.removeFirst(); deque.removeLast(); System.out.println('Deque after removing ' + 'first and last elements: ' + deque); } }

Вихід:

І (11, 7, 3, 1, 5, 9, 13)

Стандартний ітератор
11 7 3 1 5 9 13
Зворотний ітератор
13 9 5 1 3 7 11

Загляньте 11
Після підгляду: (11, 7, 3, 1, 5, 9, 13)

Поп 11
Після спливаючого: (7, 3, 1, 5, 9, 13)

Містить елемент 3 ?: true

Знищення після видалення першого та останнього елементів: (3, 1, 5, 9)

Вихідні дані Java

У наведеній вище програмі ми використовували інтерфейс Deque Java і визначали деко цілих елементів. Потім ми виконували різні операції над цим деке та виводили результати цих операцій.

Програми

Deque можна використовувати в деяких із наведених нижче програм.

# 1) Алгоритм планування: Алгоритм планування 'Алгоритм планування викрадення' реалізує планування завдань для різних процесорів у багатопроцесорній системі. Ця реалізація використовує deque, і процесор отримує перший елемент з deque для виконання.

# 2) Скасувати перелік заходів: У програмних програмах ми маємо багато дій. Один з них - 'скасувати'. Коли ми багато разів виконували дію скасування, усі ці дії зберігаються у списку. Цей список підтримується як деке, щоб ми могли легко додавати / видаляти записи з будь-якого кінця.

# 3) Видаліть записи через деякий час: Програми оновлюють записи у своєму списку, як-от програми з переліком запасів тощо. Ці програми через деякий час видаляють записи, а також вставляють нові записи. Це робиться за допомогою деке.

Висновок

Deque - це двостороння черга, яка дозволяє нам додавати / видаляти елементи з обох кінців, тобто спереду та ззаду, черги. Deque може бути реалізований за допомогою масивів або пов'язаних списків. Однак у нас також є клас стандартної бібліотеки шаблонів (STL), який реалізує різні операції Deque.

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

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

=> Ознайомтесь із Повною навчальною серією C ++

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

^