- Ταξινόμηση ουράς διπλού άκρου
- Βασικές λειτουργίες Deque
- Εικονογράφηση Deque
- Υλοποίηση Deque
- Εφαρμογές
- Συμπέρασμα
Ένα σε βάθος σεμινάριο για την Deque ή ουρά διπλού άκρου στη C++. Το σεμινάριο εξηγεί τι είναι η Deque, βασικές λειτουργίες, υλοποίηση σε C++ και Java και εφαρμογές:
Η ουρά διπλού τέλους ή απλά αποκαλούμενη "Deque" είναι μια γενικευμένη έκδοση της ουράς.
Η διαφορά μεταξύ Queue και Deque είναι ότι δεν ακολουθεί την προσέγγιση FIFO (First In, First Out). Το δεύτερο χαρακτηριστικό της Deque είναι ότι μπορούμε να εισάγουμε και να αφαιρούμε στοιχεία είτε από το μπροστινό είτε από το πίσω άκρο.
Ταξινόμηση ουράς διπλού άκρου
Οι Deque μπορούν να ταξινομηθούν ως εξής:
Deque περιορισμένης εισόδου: Στην περίπτωση περιορισμένης εισόδου, η διαγραφή μπορεί να γίνει και από τα δύο άκρα, αλλά η εισαγωγή μπορεί να γίνει μόνο στο τελευταίο άκρο της ουράς.
Deque περιορισμένης εξόδου: Στην ουρά περιορισμένης εξόδου, η εισαγωγή μπορεί να γίνει και από τα δύο άκρα, αλλά η διαγραφή γίνεται μόνο στο ένα άκρο, δηλαδή στο μπροστινό άκρο της ουράς.
Μπορούμε επίσης να υλοποιήσουμε στοίβες και ουρές χρησιμοποιώντας την deque.
Βασικές λειτουργίες Deque
Ακολουθούν οι βασικές λειτουργίες που μπορούν να εκτελεστούν σε deque.
- ένθετο μπροστά: Εισαγωγή ή προσθήκη ενός στοιχείου στο μπροστινό μέρος της deque.
- insertLast: Εισαγωγή ή προσθήκη ενός στοιχείου στο πίσω μέρος της ντέκα.
- deleteFront: Διαγραφή ή αφαίρεση του στοιχείου από το μπροστινό μέρος της ουράς.
- διαγράψτε το τελευταίο: Διαγραφή ή αφαίρεση του στοιχείου από το τέλος της ουράς.
- getFront: Ανακτά το μπροστινό στοιχείο στην deque.
- getLast: Ανακτά το τελευταίο στοιχείο στην ουρά.
- isEmpty: Ελέγχει αν η deque είναι κενή.
- isFull: Ελέγχει αν η deque είναι πλήρης.
Εικονογράφηση Deque
Μια κενή deque αναπαρίσταται ως εξής:
Στη συνέχεια, εισάγουμε το στοιχείο 1 στο μπροστινό μέρος.
Τώρα, εισάγουμε το στοιχείο 3 στο πίσω μέρος.
Στη συνέχεια, προσθέτουμε το στοιχείο 5 στο μπροστινό μέρος και όταν αυξάνεται το μπροστινό μέρος δείχνει το 4.
Στη συνέχεια, εισάγουμε τα στοιχεία 7 στο πίσω μέρος και 9 στο μπροστινό μέρος. Η deque θα έχει την παρακάτω μορφή.
Στη συνέχεια, ας αφαιρέσουμε ένα στοιχείο από το μπροστινό μέρος.
Έτσι, βλέπουμε ότι όταν τα στοιχεία εισάγονται στο μπροστινό μέρος, η μπροστινή θέση μειώνεται, ενώ αυξάνεται όταν αφαιρείται ένα στοιχείο. Για το πίσω μέρος, η θέση αυξάνεται για την εισαγωγή και μειώνεται για την αφαίρεση .
Υλοποίηση Deque
Υλοποίηση Deque σε C++
Μπορούμε να υλοποιήσουμε μια deque στη C++ χρησιμοποιώντας πίνακες καθώς και μια συνδεδεμένη λίστα. Εκτός από αυτό, η Standard Template Library (STL) διαθέτει μια κλάση "deque" η οποία υλοποιεί όλες τις συναρτήσεις για αυτή τη δομή δεδομένων.
Η υλοποίηση της ουράς deque σε πίνακες δίνεται παρακάτω. Καθώς πρόκειται για ουρά διπλού άκρου, χρησιμοποιήσαμε κυκλικούς πίνακες για την υλοποίηση.
#includeusing namespace std; #define MAX_size 10 // Μέγιστο μέγεθος του πίνακα ή της Dequeue // Κλάση Deque class class Deque { int array[MAX_size]; int front; int rear; int size; public : Deque(int size) { front = -1; rear = 0; this->size = size; } // Πράξεις στην Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); int getFront(); int getRear(); // Έλεγχος αν η Deque είναιπλήρης bool isFull() return ((front == 0 && rear == size-1) // Ελέγξτε αν η Deque είναι άδεια bool isEmpty(){ return (front == -1); } } }; // Εισαγωγή ενός στοιχείου στο μπροστινό μέρος της Deque void Deque::insertfront(int key) { if (isFull()) { cout <<"Υπερχείλιση!!!\n" <<endl; return; } // Αν η ουρά είναι αρχικά άδεια, ορίστε front=rear=0- αρχή της Deque if (front == -1) { front = 0; rear = 0; } else if(front == 0) // front είναι η πρώτη θέση της ουράς front = size - 1 ; else // decrement front 1 position front = front-1; array[front] = key ; // insert current element into Deque } // insert element at the rear end of deque void Deque ::insertrear(int key) { if (isFull()) { cout <<" Overflow!!\n " <<endl; return; } // If queue is initially empty,set front=rear=0- start of deque if(front == -1) { front = 0; rear = 0; } else if (rear == size-1) // το rear βρίσκεται στην τελευταία θέση της ουράς rear = 0; else // αυξάνουμε το rear κατά 1 θέση rear = rear+1; array[rear] = key ; // εισάγουμε το τρέχον στοιχείο στην Deque } // διαγράφουμε το στοιχείο στο μπροστινό μέρος της Deque void Deque ::deletefront() { if (isEmpty()) { cout <<"Queue Underflow!!\n" <<endl; return ; } // Η Deque έχει μόνο ένα στοιχείο if(front == rear) { front = -1; rear = -1; } else // back to initial position if (front == size -1) front = 0; else // remove current front value from Deque;increment front by 1 front = front+1; } // Delete element at rear end of Deque void Deque::deleterear() { if (isEmpty()) { cout <<" Underflow!!\n" <<endl ; return ; } // Deque has only one element if (front == rear) { front = -1,rear = -1; } else if (rear == 0) rear = size-1- else rear = rear-1; } // ανάκτηση του μπροστινού στοιχείου της Deque int Deque::getFront() { if (isEmpty()) { cout <<" Underflow!!\n" <<endl; return -1 ; } return array[front]; } // ανάκτηση του πίσω στοιχείου της Deque int Deque::getRear() { if(isEmpty()//main program int main() { Deque dq(5); cout <<"Εισαγωγή του στοιχείου 1 στο πίσω άκρο \n"; dq.insertrear(1); cout <<"εισαγωγή του στοιχείου 3 στο πίσω άκρο \n"; dq.insertrear(3); cout <<"οπίσθιο στοιχείο της deque " <<" " <<dq.getRear() <<endl- dq.deleterear(); cout <<"Μετά την deleterear, rear = " <<dq.getRear() <<endl- cout <<"εισαγωγή του στοιχείου 5 στοfront end \n"; dq.insertfront(5); cout <<"front element of deque " <<" " <<dq.getFront() <<endl; dq.deletefront(); cout <<"After deletefront, front = " <<dq.getFront() <<endl; return 0; }
Έξοδος:
Τοποθετήστε το στοιχείο 1 στο οπίσθιο άκρο
Τοποθετήστε το στοιχείο 3 στο οπίσθιο άκρο
οπίσθιο στοιχείο του deque 3
Μετά την deleterear, πίσω =
τοποθέτηση του στοιχείου 5 στο εμπρόσθιο άκρο
μπροστινό στοιχείο του deque 5
Μετά το deletefront, μπροστά =
Υλοποίηση Java Deque
Η διεπαφή deque στη Java, "java.util.Deque" προέρχεται από τη διεπαφή "java.util.Queue". Η deque μπορεί να χρησιμοποιηθεί ως ουρά (First In, First Out) ή ως στοίβα (Last In, First Out). Αυτές οι υλοποιήσεις λειτουργούν ταχύτερα από τη συνδεδεμένη λίστα.
Παρακάτω δίνεται η ιεραρχία για τη διεπαφή Deque στη Java.
Πρέπει να θυμόμαστε μερικά σημεία σχετικά με τη διεπαφή Deque στη Java:
- Η υλοποίηση δεν είναι ασφαλής για νήματα, καθώς δεν υπάρχει εξωτερικός συγχρονισμός.
- Η Deque δεν υποστηρίζει την ταυτόχρονη χρήση πολλαπλών νημάτων.
- Οι Deque που υλοποιούνται με χρήση πινάκων δεν επιτρέπουν τη χρήση στοιχείων NULL.
- Οι συστοιχίες μπορούν να αναπτυχθούν σύμφωνα με τις απαιτήσεις, με την ελεύθερη από περιορισμούς χωρητικότητα και την υποστήριξη συστοιχιών με δυνατότητα αλλαγής μεγέθους να είναι τα δύο πιο σημαντικά χαρακτηριστικά.
Ακολουθούν οι διάφορες μέθοδοι που υποστηρίζονται από τη διεπαφή Deque:
| Όχι. | Μέθοδος | Περιγραφή |
|---|---|---|
| 1 | add(element) | Προσθέτει ένα στοιχείο στην ουρά. |
| 2 | addFirst(element) | Προσθέτει ένα στοιχείο στην κεφαλή/μπροστά. |
| 3 | addLast(element) | Προσθέτει ένα στοιχείο στην ουρά/πίσω πλευρά. |
| 4 | προσφορά(στοιχείο) | Προσθέτει ένα στοιχείο στην ουρά.Επιστρέφει μια boolean τιμή για να δείξει αν η εισαγωγή ήταν επιτυχής. |
| 5 | offerFirst(element) | Προσθέτει ένα στοιχείο στην επικεφαλίδα- επιστρέφει μια boolean τιμή για να δείξει αν η εισαγωγή ήταν επιτυχής. |
| 6 | offerLast(element) | Προσθέτει ένα στοιχείο στην ουρά.Επιστρέφει μια boolean τιμή για να δείξει αν η εισαγωγή ήταν επιτυχής. |
| 7 | iterator() | Επιστρέφει έναν επαναλήπτη για το deque. |
| 8 | descendingIterator() | Επιστρέφει έναν επαναλήπτη που έχει την αντίστροφη σειρά για αυτό το deque. |
| 9 | push(element) | Προσθέτει ένα στοιχείο στην κεφαλή του deque. |
| 10 | pop(element) | Αφαιρεί ένα στοιχείο από την κεφαλή του deque και το επιστρέφει. |
| 11 | removeFirst() | Αφαιρεί το στοιχείο που βρίσκεται στην κεφαλή του deque. |
| 12 | removeLast() | Αφαιρεί το στοιχείο που βρίσκεται στην ουρά του deque. |
| 13 | poll() | Ανακτά και αφαιρεί το πρώτο στοιχείο του deque (που αντιπροσωπεύεται από την κεφαλή του deque).Επιστρέφει NULL αν το deque είναι κενό. |
| 14 | pollFirst() | Ανακτά και αφαιρεί το πρώτο στοιχείο αυτού του deque.Επιστρέφει null αν αυτό το deque είναι άδειο. |
| 15 | pollLast() | Ανακτά και αφαιρεί το τελευταίο στοιχείο αυτού του deque.Επιστρέφει null αν αυτό το deque είναι άδειο. |
| 16 | peek() | Ανακτά την επικεφαλίδα (πρώτο στοιχείο της ουράς) της ουράς που αντιπροσωπεύεται από αυτήν την ουρά- επιστρέφει null εάν αυτή η ουρά είναι κενή. Σημείωση: Αυτή η λειτουργία δεν αφαιρεί το στοιχείο. |
| 17 | peekFirst() | Ανακτά το πρώτο στοιχείο αυτού του deque.Επιστρέφει null αν αυτό το deque είναι άδειο. Σημείωση: Αυτή η λειτουργία δεν αφαιρεί το στοιχείο. |
| 18 | peekLast() | Ανακτά το τελευταίο στοιχείο αυτού του deque, ή επιστρέφει null αν αυτό το deque είναι άδειο. Σημείωση: Αυτή η λειτουργία δεν αφαιρεί το στοιχείο. |
Η ακόλουθη υλοποίηση σε Java επιδεικνύει τις διάφορες λειτουργίες που αναφέρθηκαν παραπάνω.
import java.util.*; class Main { public static void main(String[] args) { Deque deque = new LinkedList (); // Μπορούμε να προσθέσουμε στοιχεία στην ουρά με διάφορους τρόπους deque.add(1); // προσθήκη στην ουρά deque.addFirst(3); deque.addLast(5); deque.push(7); // προσθήκη στην κεφαλή deque.offer(9); deque.offerFirst(11); deque.offerLast(13); System.out.println("Η ουρά : " + deque + "\n"); // Επανάληψη των στοιχείων της ουράς. System.out.println("Standard Iterator"); Iterator iterator = deque.iterator(); while(iterator.hasNext()) System.out.print(" " + iterator.next()); // Reverse order iterator Iterator reverse = deque.descendingIterator(); System.out.println("\nReverse Iterator"); while (reverse.hasNext()) System.out.print(" " + reverse.next()); // Peek επιστρέφει την κεφαλή, χωρίς να τη διαγράψει // από την deque System.out.println("\n\nPeek " + deque.peek()); System.out.println("After peek: " + deque),// Το Pop επιστρέφει την κεφαλή, και την αφαιρεί από // την deque System.out.println("\nPop " + deque.pop()); System.out.println("Μετά το pop: " + deque); // Μπορούμε να ελέγξουμε αν ένα συγκεκριμένο στοιχείο υπάρχει // στην deque System.out.println("\nContains element 3?: " + deque.contains(3)); // Μπορούμε να αφαιρέσουμε το πρώτο / τελευταίο στοιχείο. deque.removeFirst(); deque.removeLast(); System.out.println("Deque μετά την αφαίρεση "+ "πρώτο και τελευταίο στοιχείο: " + deque); } } Έξοδος:
Το deque : [11, 7, 3, 1, 5, 9, 13]
Τυποποιημένος επαναλήπτης
11 7 3 1 5 9 13
Αντίστροφος επαναλήπτης
13 9 5 1 3 7 1
Peek 11
Μετά το κρυφτό: [11, 7, 3, 1, 5, 9, 13]
Pop 11
Μετά το pop: [7, 3, 1, 5, 9, 13]
Περιέχει το στοιχείο 3;: true
Deque μετά την αφαίρεση του πρώτου και του τελευταίου στοιχείου: [3, 1, 5, 9]
Στο παραπάνω πρόγραμμα, χρησιμοποιήσαμε τη διεπαφή Deque της Java και ορίσαμε μια deque ακέραιων στοιχείων. Στη συνέχεια εκτελέσαμε διάφορες πράξεις σε αυτή τη deque και στην έξοδο εμφανίζονται τα αποτελέσματα αυτών των πράξεων.
Εφαρμογές
Η Deque μπορεί να χρησιμοποιηθεί σε ορισμένες από τις ακόλουθες εφαρμογές.
#1) Αλγόριθμος χρονοπρογραμματισμού: Ένας αλγόριθμος χρονοπρογραμματισμού, ο "αλγόριθμος χρονοπρογραμματισμού A-steal", υλοποιεί τον προγραμματισμό εργασιών για διάφορους επεξεργαστές στο σύστημα πολλαπλών επεξεργαστών. Αυτή η υλοποίηση χρησιμοποιεί deque και ο επεξεργαστής παίρνει το πρώτο στοιχείο από το deque για εκτέλεση.
#2) Αναίρεση λίστας δραστηριοτήτων: Στις εφαρμογές λογισμικού, έχουμε πολλές ενέργειες. Μία από αυτές είναι η "αναίρεση". Όταν έχουμε εκτελέσει την ενέργεια αναίρεσης πολλές φορές, όλες αυτές οι ενέργειες αποθηκεύονται σε μια λίστα. Αυτή η λίστα διατηρείται ως deque, έτσι ώστε να μπορούμε εύκολα να προσθέτουμε/αφαιρούμε καταχωρήσεις από οποιοδήποτε άκρο.
#3) Αφαιρέστε τις καταχωρήσεις μετά από κάποιο χρονικό διάστημα: Οι εφαρμογές ανανεώνουν τις καταχωρήσεις στη λίστα τους, όπως οι εφαρμογές που απαριθμούν τις καταχωρήσεις του αποθέματος, κ.λπ. Αυτές οι εφαρμογές αφαιρούν τις καταχωρήσεις μετά από κάποιο χρονικό διάστημα και επίσης εισάγουν νέες καταχωρήσεις. Αυτό γίνεται με τη χρήση μιας deque.
Συμπέρασμα
Η Deque είναι μια ουρά με δύο άκρα που μας επιτρέπει να προσθέτουμε/αφαιρούμε στοιχεία και από τα δύο άκρα, δηλαδή το μπροστινό και το πίσω μέρος της ουράς. Η Deque μπορεί να υλοποιηθεί χρησιμοποιώντας πίνακες ή συνδεδεμένες λίστες. Ωστόσο, έχουμε επίσης μια κλάση Standard Template Library (STL) που υλοποιεί τις διάφορες λειτουργίες της Deque.
Στη Java, έχουμε μια διεπαφή Deque που κληρονομείται από τη διεπαφή queue για την υλοποίηση της Deque. Εκτός από τις βασικές τυπικές λειτουργίες της Deque, η διεπαφή αυτή υποστηρίζει διάφορες άλλες λειτουργίες που μπορούν να εκτελεστούν στη Deque.
Η Deque χρησιμοποιείται γενικά για εφαρμογές που απαιτούν προσθήκη/αφαίρεση στοιχείων και από τα δύο άκρα. Χρησιμοποιείται επίσης κυρίως στον προγραμματισμό των επεξεργαστών σε συστήματα πολλαπλών επεξεργαστών.
Ελέγξτε την πλήρη σειρά εκπαίδευσης C++