Deque datastruktur

I denne vejledning lærer du, hvad en kø med dobbelt ende (deque) er. Du finder også arbejdseksempler på forskellige operationer på en deque i C, C ++, Java og Python.

Deque eller Double Ended Queue er en type kø, hvor indsættelse og fjernelse af elementer kan udføres fra enten forfra eller bagfra. Således følger den ikke FIFO-reglen (First In First Out).

Repræsentation af Deque

Typer af Deque

  • Input Restricted Deque
    I denne deque er input begrænset i en enkelt ende, men tillader sletning i begge ender.
  • Output Restricted Deque
    I denne deque er output begrænset i en enkelt ende, men tillader indsættelse i begge ender.

Operationer på en Deque

Nedenfor er den cirkulære matriximplementering af deque. I en cirkulær matrix, hvis matrixen er fuld, starter vi fra starten.

Men i en lineær matriximplementering, hvis matrixen er fuld, kan der ikke indsættes flere elementer. Hvis matrixen er fuld i hver af nedenstående operationer, kastes "overløbsmeddelelse".

Før du udfører følgende handlinger, følges disse trin.

  1. Tag en matrix (deque) af størrelse n.
  2. Sæt to markører på første position, og indstil front = -1og rear = 0.
Initialiser en matrix og pegepunkter til deque

1. Indsæt foran

Denne operation tilføjer et element foran.

  1. Kontroller frontens position. Kontroller frontens position
  2. Hvis front < 1, genstart initialiser front = n-1(sidste indeks). Skift front til slutningen
  3. Ellers mindskes fronten med 1.
  4. Tilføj den nye nøgle 5 i array(front). Indsæt elementet foran

2. Indsæt bagpå

Denne operation tilføjer et element bagpå.

  1. Kontroller, om matrixen er fuld. Kontroller, om deque er fuld
  2. Genstart initialiseringen, hvis deque er fuld rear = 0.
  3. Ellers øges bagenden med 1. Forøg bagenden
  4. Tilføj den nye nøgle 5 i array(rear). Indsæt elementet bagpå

3. Slet fra forsiden

Operationen sletter et element forfra.

  1. Kontroller, om skiltet er tomt. Kontroller, om deque er tom
  2. Hvis deque er tom (dvs. front = -1), kan sletning ikke udføres ( underflowtilstand ).
  3. Hvis deque kun har et element (dvs. front = rear), skal du indstille front = -1og rear = -1.
  4. Ellers hvis fronten er i slutningen (dvs. front = n - 1), skal du gå til fronten front = 0.
  5. Ellers front = front + 1. Forøg fronten

4. Slet bagfra

Denne handling sletter et element bagfra.

  1. Kontroller, om skiltet er tomt. Kontroller, om deque er tom
  2. Hvis deque er tom (dvs. front = -1), kan sletning ikke udføres ( underflowtilstand ).
  3. Hvis deque kun har et element (dvs. front = rear), skal du sætte front = -1og rear = -1ellers følge nedenstående trin.
  4. Hvis bagsiden er forrest (dvs. rear = 0), skal du indstille gå fremad rear = n - 1.
  5. Ellers rear = rear - 1. Sænk bagenden

5. Marker Tom

Denne handling kontrollerer, om deque er tom. Hvis front = -1deque er tom.

6. Kontroller fuldt ud

Denne handling kontrollerer, om deque er fuld. Hvis front = 0og rear = n - 1ELLER front = rear + 1, er deken fuld.

Deque-implementering i Python, Java, C og 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; )

Tidskompleksitet

Tiden kompleksiteten af alle de ovennævnte operationer er konstant dvs. O(1).

Anvendelser af Deque-datastruktur

  1. Fortryd operationer på software.
  2. For at gemme historik i browsere.
  3. Til implementering af både stakke og køer.

Interessante artikler...