Deque datová struktura

V tomto kurzu se dozvíte, co je to dvojitá fronta (deque). Také najdete pracovní příklady různých operací na deque v C, C ++, Java a Python.

Deque nebo Double Ended Queue je typ fronty, ve které lze vkládání a odebírání prvků provádět zepředu nebo zezadu. Nesleduje tedy pravidlo FIFO (First In First Out).

Zastoupení Deque

Druhy Deque

  • Deque Restricted Deque
    V tomto deque je vstup omezen na jednom konci, ale umožňuje odstranění na obou koncích.
  • Omezení výstupu Deque
    V tomto deque je výstup omezen na jednom konci, ale umožňuje vložení na oba konce.

Operace na Deque

Níže je implementace deque kruhového pole. V kruhovém poli, pokud je pole plné, začneme od začátku.

Ale v implementaci lineárního pole, pokud je pole plné, nelze vložit žádné další prvky. V každé z níže uvedených operací, pokud je pole plné, je vyvolána „zpráva o přetečení“.

Před provedením následujících operací se postupuje podle těchto kroků.

  1. Vezměte pole (deque) o velikosti n.
  2. Nastavte dva ukazatele na první pozici a nastavte front = -1a rear = 0.
Inicializujte pole a ukazatele pro deque

1. Vložte přední část

Tato operace přidá prvek vpředu.

  1. Zkontrolujte polohu přední části. Zkontrolujte polohu přední části
  2. Pokud front < 1znovu inicializovat front = n-1(poslední index). Posuňte přední část na konec
  3. Jinak snížit přední o 1.
  4. Přidejte nový klíč 5 do array(front). Vložte prvek vpředu

2. Vložte zadní část

Tato operace přidává prvek dozadu.

  1. Zkontrolujte, zda je pole plné. Zkontrolujte, zda je deque plný
  2. Pokud je deque plný, znovu inicializujte rear = 0.
  3. Jinak zvětšit zadní část o 1. Zvýšit zadní část
  4. Přidejte nový klíč 5 do array(rear). Vložte prvek vzadu

3. Odstranit zepředu

Operace odstraní prvek zepředu.

  1. Zkontrolujte, zda je deque prázdný. Zkontrolujte, zda je deque prázdný
  2. Pokud je deque prázdný (tj. front = -1), Nelze provést mazání ( podmínka podtečení ).
  3. Pokud má deque pouze jeden prvek (tj. front = rear), Nastavte front = -1a rear = -1.
  4. Jinak, pokud je přední strana na konci (tj. front = n - 1), Nastavte přechod na přední stranu front = 0.
  5. Jinak front = front + 1. Zvětšete přední část

4. Odstranit zezadu

Tato operace odstraní prvek zezadu.

  1. Zkontrolujte, zda je deque prázdný. Zkontrolujte, zda je deque prázdný
  2. Pokud je deque prázdný (tj. front = -1), Nelze provést mazání ( podmínka podtečení ).
  3. Pokud má deque pouze jeden prvek (tj. front = rear), Nastavte front = -1a rear = -1, jinak postupujte podle následujících kroků.
  4. Pokud je zadní část vpředu (tj. rear = 0), Nastavte možnost jít dopředu rear = n - 1.
  5. Jinak rear = rear - 1. Snižte zadní část

5. Zaškrtněte Prázdné

Tato operace kontroluje, zda je deque prázdný. Pokud front = -1je deque prázdný.

6. Zkontrolujte plné

Tato operace zkontroluje, zda je deque plný. Pokud front = 0a rear = n - 1NE front = rear + 1, deque je plný.

Deque implementace v Pythonu, Javě, C a 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; )

Časová složitost

Časová složitost všech výše uvedených operací je konstantní, tzn O(1).

Aplikace deque datové struktury

  1. Při zpětných operacích na softwaru.
  2. Ukládání historie do prohlížečů.
  3. Pro implementaci zásobníků i front.

Zajímavé články...