Deque-gegevensstructuur

In deze tutorial leer je wat een dubbele wachtrij (deque) is. Ook vindt u werkende voorbeelden van verschillende bewerkingen op een deque in C, C ++, Java en Python.

Deque of Double Ended Queue is een soort wachtrij waarin het invoegen en verwijderen van elementen van voren of van achteren kan worden uitgevoerd. Het volgt dus niet de FIFO-regel (First In First Out).

Vertegenwoordiging van Deque

Soorten Deque

  • Invoer beperkte deque
    In deze deque is de invoer beperkt aan één uiteinde, maar kan deze aan beide uiteinden worden verwijderd.
  • Uitvoer beperkte deque
    In deze deque is de uitvoer beperkt aan een enkel uiteinde, maar kan aan beide uiteinden worden ingevoerd .

Operaties op een Deque

Hieronder ziet u de circulaire array-implementatie van deque. In een cirkelvormige array beginnen we vanaf het begin als de array vol is.

Maar als in een lineaire array-implementatie de array vol is, kunnen er geen elementen meer worden ingevoegd. In elk van de onderstaande bewerkingen, als de array vol is, wordt een "overloopbericht" gegenereerd.

Voordat u de volgende bewerkingen uitvoert, worden deze stappen gevolgd.

  1. Neem een ​​array (deque) van maat n.
  2. Stel twee wijzers in op de eerste positie en stel front = -1en in rear = 0.
Initialiseer een array en pointers voor deque

1. Invoegen aan de voorkant

Deze operatie voegt een element aan de voorkant toe.

  1. Controleer de positie van de voorkant. Controleer de positie van de voorkant
  2. Als front < 1, herinitialiseer front = n-1(laatste index). Schuif van voren naar het einde
  3. Anders verkleint u de voorkant met 1.
  4. Voeg de nieuwe sleutel 5 toe aan array(front). Plaats het element vooraan

2. Invoegen aan de achterkant

Deze operatie voegt een element aan de achterkant toe.

  1. Controleer of de array vol is. Controleer of de deque vol is
  2. Als de kaart vol is, initialiseert u opnieuw rear = 0.
  3. Anders verhoogt u de achterkant met 1. Vergroot de achterkant
  4. Voeg de nieuwe sleutel 5 toe aan array(rear). Plaats het element aan de achterkant

3. Verwijderen vanaf de voorkant

De bewerking verwijdert een element van de voorkant.

  1. Controleer of de kaart leeg is. Controleer of de kaart leeg is
  2. Als de kaart leeg is (dwz front = -1), kan de verwijdering niet worden uitgevoerd ( onderstroomtoestand ).
  3. Als de deque slechts één element heeft (dwz front = rear), stelt u front = -1en in rear = -1.
  4. Anders, als de voorkant aan het einde is (dwz front = n - 1), ga dan naar de voorkant front = 0.
  5. Else, front = front + 1. Verhoog de voorkant

4. Verwijderen van achteren

Deze bewerking verwijdert een element van achteren.

  1. Controleer of de kaart leeg is. Controleer of de kaart leeg is
  2. Als de kaart leeg is (dwz front = -1), kan de verwijdering niet worden uitgevoerd ( onderstroomtoestand ).
  3. Als de deque slechts één element (dwz front = rear) heeft, stelt u front = -1en in rear = -1, anders volgt u de onderstaande stappen.
  4. Als de achterkant vooraan is (dwz rear = 0), ga dan naar de voorkant rear = n - 1.
  5. Else, rear = rear - 1. Verlaag de achterkant

5. Vink Leeg aan

Deze operatie controleert of de kaart leeg is. Als front = -1de kaart leeg is.

6. Controleer Vol

Deze handeling controleert of de kaart vol is. Als front = 0en rear = n - 1OF front = rear + 1, is de kaart vol.

Deque-implementatie in Python, Java, C en 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; )

Tijdscomplexiteit

De tijdcomplexiteit van alle bovenstaande bewerkingen is constant, dwz O(1).

Toepassingen van Deque-gegevensstructuur

  1. Bij het ongedaan maken van bewerkingen op software.
  2. Om geschiedenis in browsers op te slaan.
  3. Voor het implementeren van zowel stapels als wachtrijen.

Interessante artikelen...