Δομή δεδομένων Deque

Σε αυτό το σεμινάριο, θα μάθετε τι είναι η ουρά διπλού άκρου (deque). Επίσης, θα βρείτε παραδείγματα εργασίας διαφορετικών λειτουργιών σε ένα deque σε C, C ++, Java και Python.

Το Deque ή το Double Ended Queue είναι ένας τύπος ουράς στην οποία η εισαγωγή και η αφαίρεση στοιχείων μπορούν να πραγματοποιηθούν είτε από το μπροστινό είτε από το πίσω μέρος. Έτσι, δεν ακολουθεί τον κανόνα FIFO (First In First Out).

Εκπροσώπηση του Ντεκ

Τύποι Deque

  • Input Restricted Deque
    Σε αυτό το deque, η είσοδος περιορίζεται σε ένα μόνο άκρο αλλά επιτρέπει τη διαγραφή και στα δύο άκρα.
  • Output Restricted 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. Ελέγξτε εάν ο πίνακας είναι πλήρης. Ελέγξτε εάν το deque είναι γεμάτο
  2. Εάν το deque είναι γεμάτο, επανεκκινήστε rear = 0.
  3. Αλλιώς, αυξήστε το πίσω κατά 1. Αυξήστε το πίσω
  4. Προσθέστε το νέο κλειδί 5 στο array(rear). Τοποθετήστε το στοιχείο στο πίσω μέρος

3. Διαγράψτε από το μπροστινό μέρος

Η λειτουργία διαγράφει ένα στοιχείο από μπροστά.

  1. Ελέγξτε εάν το deque είναι άδειο. Ελέγξτε εάν το deque είναι άδειο
  2. Εάν το deque είναι κενό (δηλ. front = -1), Δεν είναι δυνατή η διαγραφή ( κατάσταση underflow )
  3. Εάν η deque έχει μόνο ένα στοιχείο (δηλαδή front = rear), ορίστε front = -1και rear = -1.
  4. Διαφορετικά, εάν το μπροστινό μέρος είναι στο τέλος (δηλαδή front = n - 1), μεταβείτε στο μπροστινό μέρος front = 0.
  5. Αλλιώς, front = front + 1. Αυξήστε το μέτωπο

4. Διαγράψτε από το πίσω μέρος

Αυτή η λειτουργία διαγράφει ένα στοιχείο από πίσω.

  1. Ελέγξτε εάν το deque είναι άδειο. Ελέγξτε εάν το deque είναι άδειο
  2. Εάν το deque είναι κενό (δηλ. front = -1), Δεν είναι δυνατή η διαγραφή ( κατάσταση underflow )
  3. Εάν η deque έχει μόνο ένα στοιχείο (δηλαδή front = rear), ορίστε front = -1και rear = -1, αλλιώς ακολουθήστε τα παρακάτω βήματα.
  4. Εάν το πίσω μέρος είναι μπροστά (δηλ. rear = 0), Ρυθμίστε το προς τα εμπρός rear = n - 1.
  5. Αλλιώς, rear = rear - 1. Μειώστε το πίσω μέρος

5. Επιλέξτε Άδειασμα

Αυτή η λειτουργία ελέγχει εάν το deque είναι κενό. Εάν front = -1, το deque είναι άδειο.

6. Έλεγχος πλήρους

Αυτή η λειτουργία ελέγχει εάν το deque είναι γεμάτο. Εάν front = 0και rear = n - 1OR front = rear + 1, η deque είναι γεμάτη.

Εφαρμογή 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. Για την εφαρμογή τόσο στοίβες όσο και ουρές.

ενδιαφέροντα άρθρα...