Структура даних Deque

У цьому підручнику ви дізнаєтесь, що таке подвійна черга (deque). Крім того, ви знайдете робочі приклади різних операцій над декетом в C, C ++, Java та Python.

Deque або Double Ended Queue - це тип черги, при якій вставка та вилучення елементів може виконуватися як спереду, так і ззаду. Таким чином, він не відповідає правилу FIFO (First In First Out).

Представлення Деке

Види Деке

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

Операції на деке

Нижче представлена ​​кругова реалізація масиву deque. У круговому масиві, якщо масив заповнений, ми починаємо спочатку.

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

Перед виконанням наступних операцій виконайте ці кроки.

  1. Візьмемо масив (deque) розміром n.
  2. Встановіть два покажчики в першу позицію та встановіть front = -1і rear = 0.
Ініціалізуйте масив і покажчики для deque

1. Вставте спереду

Ця операція додає елемент спереду.

  1. Перевірте положення спереду. Перевірте положення спереду
  2. Якщо front < 1, повторно ініціалізувати front = n-1(останній індекс). Зсуньте фронт до кінця
  3. В іншому випадку зменшіть фронт на 1.
  4. Додайте новий ключ 5 в array(front). Вставте елемент спереду

2. Вставте ззаду

Ця операція додає елемент ззаду.

  1. Перевірте, чи масив заповнений. Перевірте, чи заповнений пробник
  2. Якщо деке заповнене, повторно ініціалізуйте rear = 0.
  3. В іншому випадку збільште задній на 1. Збільште задній
  4. Додайте новий ключ 5 в array(rear). Вставте елемент ззаду

3. Видалити з фронту

Операція видаляє елемент спереду.

  1. Перевірте, чи не пустує кришка. Перевірте, чи немає пустоти
  2. Якщо параметр порожній (тобто front = -1), видалення виконати неможливо ( умова недотоку ).
  3. Якщо деке має лише один елемент (тобто front = rear), встановіть front = -1і rear = -1.
  4. В іншому випадку, якщо спереду в кінці (тобто front = n - 1), встановити перейти вперед front = 0.
  5. Інакше front = front + 1. Збільште фронт

4. Видалити з тилу

Ця операція видаляє елемент із тильної сторони.

  1. Перевірте, чи не пустує кришка. Перевірте, чи немає пустоти
  2. Якщо параметр порожній (тобто front = -1), видалення виконати неможливо ( умова недотоку ).
  3. Якщо деке має лише один елемент (тобто front = rear), встановіть front = -1і rear = -1, інакше виконайте наведені нижче дії.
  4. Якщо тил знаходиться спереду (тобто rear = 0), встановіть перейти вперед rear = n - 1.
  5. Інакше rear = rear - 1. Зменшіть задню частину

5. Позначте Порожній

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

6. Позначка Повна

Ця операція перевіряє, чи заповнено деку. Якщо front = 0і rear = n - 1АБО front = rear + 1, деке заповнене.

Впровадження Deque в Python, Java, C та C ++

Python Java C C ++ 
 # Deque implementaion in python class Deque: def __init__(self): self.items = () def isEmpty(self): return self.items == () def addRear(self, item): self.items.append(item) def addFront(self, item): self.items.insert(0, item) def removeFront(self): return self.items.pop() def removeRear(self): return self.items.pop(0) def size(self): return len(self.items) d = Deque() print(d.isEmpty()) d.addRear(8) d.addRear(5) d.addFront(7) d.addFront(10) print(d.size()) print(d.isEmpty()) d.addRear(11) print(d.removeRear()) print(d.removeFront()) d.addFront(55) d.addRear(45) print(d.items)
 // Deque implementation in Java class Deque ( static final int MAX = 100; int arr(); int front; int rear; int size; public Deque(int size) ( arr = new int(MAX); front = -1; rear = 0; this.size = size; ) boolean isFull() ( return ((front == 0 && rear == size - 1) || front == rear + 1); ) boolean isEmpty() ( return (front == -1); ) void insertfront(int key) ( if (isFull()) ( System.out.println("Overflow"); return; ) if (front == -1) ( front = 0; rear = 0; ) else if (front == 0) front = size - 1; else front = front - 1; arr(front) = key; ) void insertrear(int key) ( if (isFull()) ( System.out.println(" Overflow "); return; ) if (front == -1) ( front = 0; rear = 0; ) else if (rear == size - 1) rear = 0; else rear = rear + 1; arr(rear) = key; ) void deletefront() ( if (isEmpty()) ( System.out.println("Queue Underflow"); return; ) // Deque has only one element if (front == rear) ( front = -1; rear = -1; ) else if (front == size - 1) front = 0; else front = front + 1; ) void deleterear() ( if (isEmpty()) ( System.out.println(" Underflow"); return; ) if (front == rear) ( front = -1; rear = -1; ) else if (rear == 0) rear = size - 1; else rear = rear - 1; ) int getFront() ( if (isEmpty()) ( System.out.println(" Underflow"); return -1; ) return arr(front); ) int getRear() ( if (isEmpty() || rear < 0) ( System.out.println(" Underflow"); return -1; ) return arr(rear); ) public static void main(String() args) ( Deque dq = new Deque(4); System.out.println("Insert element at rear end : 12 "); dq.insertrear(12); System.out.println("insert element at rear end : 14 "); dq.insertrear(14); System.out.println("get rear element : " + dq.getRear()); dq.deleterear(); System.out.println("After delete rear element new rear become : " + dq.getRear()); System.out.println("inserting element at front end"); dq.insertfront(13); System.out.println("get front element: " + dq.getFront()); dq.deletefront(); System.out.println("After delete front element new front become : " + +dq.getFront()); ) )
 // Deque implementation in C #include #define MAX 10 void addFront(int *, int, int *, int *); void addRear(int *, int, int *, int *); int delFront(int *, int *, int *); int delRear(int *, int *, int *); void display(int *); int count(int *); int main() ( int arr(MAX); int front, rear, i, n; front = rear = -1; for (i = 0; i < MAX; i++) arr(i) = 0; addRear(arr, 5, &front, &rear); addFront(arr, 12, &front, &rear); addRear(arr, 11, &front, &rear); addFront(arr, 5, &front, &rear); addRear(arr, 6, &front, &rear); addFront(arr, 8, &front, &rear); printf("Elements in a deque: "); display(arr); i = delFront(arr, &front, &rear); printf("removed item: %d", i); printf("Elements in a deque after deletion: "); display(arr); addRear(arr, 16, &front, &rear); addRear(arr, 7, &front, &rear); printf("Elements in a deque after addition: "); display(arr); i = delRear(arr, &front, &rear); printf("removed item: %d", i); printf("Elements in a deque after deletion: "); display(arr); n = count(arr); printf("Total number of elements in deque: %d", n); ) void addFront(int *arr, int item, int *pfront, int *prear) ( int i, k, c; if (*pfront == 0 && *prear == MAX - 1) ( printf("Deque is full."); return; ) if (*pfront == -1) ( *pfront = *prear = 0; arr(*pfront) = item; return; ) if (*prear != MAX - 1) ( c = count(arr); k = *prear + 1; for (i = 1; i <= c; i++) ( arr(k) = arr(k - 1); k--; ) arr(k) = item; *pfront = k; (*prear)++; ) else ( (*pfront)--; arr(*pfront) = item; ) ) void addRear(int *arr, int item, int *pfront, int *prear) ( int i, k; if (*pfront == 0 && *prear == MAX - 1) ( printf("Deque is full."); return; ) if (*pfront == -1) ( *prear = *pfront = 0; arr(*prear) = item; return; ) if (*prear == MAX - 1) ( k = *pfront - 1; for (i = *pfront - 1; i < *prear; i++) ( k = i; if (k == MAX - 1) arr(k) = 0; else arr(k) = arr(i + 1); ) (*prear)--; (*pfront)--; ) (*prear)++; arr(*prear) = item; ) int delFront(int *arr, int *pfront, int *prear) ( int item; if (*pfront == -1) ( printf("Deque is empty."); return 0; ) item = arr(*pfront); arr(*pfront) = 0; if (*pfront == *prear) *pfront = *prear = -1; else (*pfront)++; return item; ) int delRear(int *arr, int *pfront, int *prear) ( int item; if (*pfront == -1) ( printf("Deque is empty."); return 0; ) item = arr(*prear); arr(*prear) = 0; (*prear)--; if (*prear == -1) *pfront = -1; return item; ) void display(int *arr) ( int i; printf(" front: "); for (i = 0; i < MAX; i++) printf(" %d", arr(i)); printf(" :rear"); ) int count(int *arr) ( int c = 0, i; for (i = 0; i < MAX; i++) ( if (arr(i) != 0) c++; ) return c; )
 // Deque implementation in C++ #include using namespace std; #define MAX 10 class Deque ( int arr(MAX); int front; int rear; int size; public: Deque(int size) ( front = -1; rear = 0; this->size = size; ) void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); bool isFull(); bool isEmpty(); int getFront(); int getRear(); ); bool Deque::isFull() ( return ((front == 0 && rear == size - 1) || front == rear + 1); ) bool Deque::isEmpty() ( return (front == -1); ) void Deque::insertfront(int key) ( if (isFull()) ( cout << "Overflow" << endl; return; ) if (front == -1) ( front = 0; rear = 0; ) else if (front == 0) front = size - 1; else front = front - 1; arr(front) = key; ) void Deque ::insertrear(int key) ( if (isFull()) ( cout << " Overflow " << endl; return; ) if (front == -1) ( front = 0; rear = 0; ) else if (rear == size - 1) rear = 0; else rear = rear + 1; arr(rear) = key; ) void Deque ::deletefront() ( if (isEmpty()) ( cout << "Queue Underflow" << endl; return; ) if (front == rear) ( front = -1; rear = -1; ) else if (front == size - 1) front = 0; else front = front + 1; ) void Deque::deleterear() ( if (isEmpty()) ( cout << " Underflow" << endl; return; ) if (front == rear) ( front = -1; rear = -1; ) else if (rear == 0) rear = size - 1; else rear = rear - 1; ) int Deque::getFront() ( if (isEmpty()) ( cout << " Underflow" << endl; return -1; ) return arr(front); ) int Deque::getRear() ( if (isEmpty() || rear < 0) ( cout << " Underflow" << endl; return -1; ) return arr(rear); ) int main() ( Deque dq(4); cout << "insert element at rear end "; dq.insertrear(5); dq.insertrear(11); cout << "rear element: " << dq.getRear() << endl; dq.deleterear(); cout << "after deletion of the rear element, the new rear element: " << dq.getRear() << endl; cout << "insert element at front end "; dq.insertfront(8); cout << "front element: " << dq.getFront() << endl; dq.deletefront(); cout << "after deletion of front element new front element: " << dq.getFront() << endl; )

Складність часу

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

Застосування структури даних Deque

  1. Операції скасування програмного забезпечення.
  2. Для зберігання історії у браузерах.
  3. Для реалізації як стеків, так і черг.

Цікаві статті...