double ended queue c with examples
Ένα σεμινάριο σε βάθος για την ουρά ή διπλή ουρά στο C ++. Το Tutorial εξηγεί τι είναι το Deque, οι βασικές λειτουργίες, η εφαρμογή και οι εφαρμογές C ++ & Java:
Διπλή ουρά ή απλά ονομάζεται 'Deque' είναι μια γενικευμένη έκδοση του Queue.
Η διαφορά μεταξύ Queue και Deque είναι ότι δεν ακολουθεί την προσέγγιση FIFO (First In, First Out). Το δεύτερο χαρακτηριστικό του Deque είναι ότι μπορούμε να εισαγάγουμε και να αφαιρέσουμε στοιχεία είτε από τα εμπρός όσο και από τα πίσω άκρα.
=> Διαβάστε το The Easy C ++ Training Series
Τι θα μάθετε:
- Ταξινόμηση ουράς διπλού τερματισμού
- Βασικές λειτουργίες αφής
- και απεικόνιση
- και εφαρμογή
- Εφαρμογές
- συμπέρασμα
- Συνιστώμενη ανάγνωση
Ταξινόμηση ουράς διπλού τερματισμού
Το Deque μπορεί να ταξινομηθεί ως εξής:
Είσοδος περιορισμένης αφής. Σε περιορισμούς εισόδου, η διαγραφή μπορεί να γίνει και από τα δύο άκρα αλλά η εισαγωγή μπορεί να γίνει μόνο στο πίσω άκρο της ουράς.
Deque περιορισμένης παραγωγής: Στην ουρά περιορισμένης εξόδου, η εισαγωγή μπορεί να γίνει και από τα δύο άκρα αλλά η διαγραφή γίνεται μόνο στο ένα άκρο, δηλαδή το εμπρόσθιο άκρο της ουράς.
Μπορούμε επίσης να εφαρμόσουμε στοίβες και ουρές χρησιμοποιώντας deque.
Βασικές λειτουργίες αφής
Τα παρακάτω είναι οι βασικές λειτουργίες που μπορούν να εκτελεστούν στο deque.
- εισάγετε μπροστά: Εισαγάγετε ή προσθέστε ένα στοιχείο στο μπροστινό μέρος του deque.
- ένθετο Τελευταίο: Εισαγάγετε ή προσθέστε ένα στοιχείο στο πίσω μέρος του deque.
- deleteFront: Διαγράψτε ή αφαιρέστε το στοιχείο από το μπροστινό μέρος της ουράς.
- διαγραφή τελευταία: Διαγράψτε ή αφαιρέστε το αντικείμενο από το πίσω μέρος της ουράς.
- getFront: Ανακτά το μπροστινό στοιχείο στο deque.
- getLast: Ανακτά το τελευταίο στοιχείο στην ουρά.
- είναι άδειο: Ελέγχει εάν το deque είναι άδειο.
- είναι γεμάτο: Ελέγχει εάν το deque είναι γεμάτο.
και απεικόνιση
Ένα άδειο deque παρουσιάζεται ως εξής:
δοκιμάστε τον ιστότοπό μου σε διαφορετικά προγράμματα περιήγησης
Στη συνέχεια, εισάγουμε το στοιχείο 1 στο μπροστινό μέρος.
Τώρα, εισάγουμε το στοιχείο 3 στο πίσω μέρος.
Στη συνέχεια, προσθέτουμε το στοιχείο 5 στο μπροστινό μέρος και όταν αυξάνουμε τα μπροστινά σημεία στο 4.
απροσδιόριστη αναφορά στη λειτουργία στο αρχείο κεφαλίδας c ++
Στη συνέχεια, εισάγουμε στοιχεία 7 στο πίσω μέρος και 9 στο μπροστινό μέρος. Το deque θα φαίνεται όπως φαίνεται παρακάτω.
Στη συνέχεια, ας αφαιρέσουμε ένα στοιχείο από μπροστά.
Έτσι, βλέπουμε ότι όταν τα στοιχεία εισάγονται στο μπροστινό μέρος, η μπροστινή θέση μειώνεται ενώ αυξάνεται όταν αφαιρείται ένα στοιχείο. Για το πίσω άκρο, η θέση αυξάνεται για εισαγωγή και μειώνεται για αφαίρεση .
και εφαρμογή
Εφαρμογή 100 ++ αφής
Μπορούμε να εφαρμόσουμε ένα deque στο C ++ χρησιμοποιώντας πίνακες καθώς και μια συνδεδεμένη λίστα. Εκτός από αυτό, η Βασική Βιβλιοθήκη Πρότυπων (STL) έχει μια κατηγορία «deque» που εφαρμόζει όλες τις λειτουργίες για αυτήν τη δομή δεδομένων.
Η υλοποίηση του πίνακα του deque έχει δοθεί παρακάτω. Καθώς πρόκειται για ουρά διπλού άκρου, χρησιμοποιήσαμε κυκλικούς πίνακες για εφαρμογή.
#include using namespace std; #define MAX_size 10 // Maximum size of array or 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; } // Operations on Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); int getFront(); int getRear(); // Check if Deque is full bool isFull()front == rear+1); // Check if Deque is empty bool isEmpty(){ return (front == -1); } }; // Insert an element at front of the deque void Deque::insertfront(int key) { if (isFull()) { cout << 'Overflow!!
' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (front == 0) // front is first position of queue 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!!
' << 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 is at last position of queue rear = 0; else // increment rear by 1 position rear = rear+1; array(rear) = key ; // insert current element into Deque } // Delete element at front of Deque void Deque ::deletefront() { if (isEmpty()) { cout << 'Queue Underflow!!
' << endl; return ; } // Deque has only one element 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!!
' << 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; } // retrieve front element of Deque int Deque::getFront() { if (isEmpty()) { cout << ' Underflow!!
' << endl; return -1 ; } return array(front); } // retrieve rear element of Deque int Deque::getRear() { if(isEmpty() || rear < 0) { cout << ' Underflow!!
' << endl; return -1 ; } return array(rear); } //main program int main() { Deque dq(5); cout << 'Insert element 1 at rear end
'; dq.insertrear(1); cout << 'insert element 3 at rear end
'; dq.insertrear(3); cout << 'rear element of deque ' << ' ' << dq.getRear() << endl; dq.deleterear(); cout << 'After deleterear, rear = ' << dq.getRear() << endl; cout << 'inserting element 5 at front end
'; 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
Μετά τη διαγραφή, πίσω = 1
εισαγωγή του στοιχείου 5 στο μπροστινό άκρο
εμπρός στοιχείο της deque 5
Μετά τη διαγραφή, μπροστά = 1
Καταμέτρηση υλοποίησης Java
Η διασύνδεση 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:
πώς να ανοίξετε ένα αρχείο jnlp windows 10
| Οχι. | Μέθοδος | Περιγραφή |
|---|---|---|
| 7 | επανάληψη () | Επιστρέφει έναν επαναληπτικό για το deque. |
| ένας | προσθήκη (στοιχείο) | Προσθέτει ένα στοιχείο στην ουρά. |
| δύο | addFirst (στοιχείο) | Προσθέτει ένα στοιχείο στο κεφάλι / μπροστά. |
| 3 | addLast (στοιχείο) | Προσθέτει ένα στοιχείο στην ουρά / πίσω. |
| 4 | προσφορά (στοιχείο) | Προσθέτει ένα στοιχείο στην ουρά. επιστρέφει μια δυαδική τιμή για να δείξει εάν η εισαγωγή ήταν επιτυχής. |
| 5 | offerFirst (στοιχείο) | Προσθέτει ένα στοιχείο στο κεφάλι. επιστρέφει μια δυαδική τιμή για να δείξει εάν η εισαγωγή ήταν επιτυχής. |
| 6 | offerLast (στοιχείο) | Προσθέτει ένα στοιχείο στην ουρά. επιστρέφει μια δυαδική τιμή για να δείξει εάν η εισαγωγή ήταν επιτυχής. |
| 8 | φθίνουσαIterator () | Επιστρέφει έναν επαναληπτικό που έχει την αντίστροφη σειρά για αυτό το deque. |
| 9 | ώθηση (στοιχείο) | Προσθέτει ένα στοιχείο στο κεφάλι του deque. |
| 10 | ποπ (στοιχείο) | Αφαιρεί ένα στοιχείο από την κεφαλή του deque και το επιστρέφει. |
| έντεκα | αφαίρεσηΠρώτα () | Αφαιρεί το στοιχείο στην κεφαλή του deque. |
| 12 | αφαίρεση Τελευταία () | Αφαιρεί το στοιχείο στην ουρά του deque. |
| 13 | ψηφοφορία() | Ανακτά και αφαιρεί το πρώτο στοιχείο της deque (αντιπροσωπεύεται από την κεφαλή της deque). επιστρέφει NULL εάν το deque είναι κενό. |
| 14 | pollFirst () | Ανακτά και αφαιρεί το πρώτο στοιχείο αυτού του deque. επιστρέφει null εάν αυτή η deque είναι άδεια. |
| δεκαπέντε | pollLast () | Ανακτά και αφαιρεί το τελευταίο στοιχείο αυτής της deque. επιστρέφει null εάν αυτή η deque είναι άδεια. |
| 16 | κρυφοκοίταγμα() | Ανακτά την κεφαλή (πρώτο στοιχείο της deque) της ουράς που αντιπροσωπεύεται από αυτήν την deque. επιστρέφει null εάν αυτή η deque είναι άδεια. Σημείωση: Αυτή η λειτουργία δεν αφαιρεί το στοιχείο. |
| 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 (); // We can add elements to the queue in various ways deque.add(1); // add to tail deque.addFirst(3); deque.addLast(5); deque.push(7); //add to head deque.offer(9); deque.offerFirst(11); deque.offerLast(13); System.out.println('The deque : ' + deque + '
'); // Iterate through the queue elements. 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('
Reverse Iterator'); while (reverse.hasNext()) System.out.print(' ' + reverse.next()); // Peek returns the head, without deleting // it from the deque System.out.println('
Peek ' + deque.peek()); System.out.println('After peek: ' + deque); // Pop returns the head, and removes it from // the deque System.out.println('
Pop ' + deque.pop()); System.out.println('After pop: ' + deque); // We can check if a specific element exists // in the deque System.out.println('
Contains element 3?: ' + deque.contains(3)); // We can remove the first / last element. deque.removeFirst(); deque.removeLast(); System.out.println('Deque after removing ' + 'first and last elements: ' + deque); } } Παραγωγή:
Και το (11, 7, 3, 1, 5, 9, 13)
Τυπικό επαναληπτικό
11 7 3 1 5 9 13
Αντίστροφη επανάληψη
13 9 5 1 3 7 11
Κοιτάξτε 11
Μετά τη ματιά: (11, 7, 3, 1, 5, 9, 13)
Ποπ 11
Μετά το ποπ: (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 που κληρονομείται από τη διεπαφή ουράς για την εφαρμογή του Deque. Εκτός από τις βασικές τυπικές λειτουργίες του Deque, αυτή η διεπαφή υποστηρίζει διάφορες άλλες λειτουργίες που μπορούν να πραγματοποιηθούν στο Deque.
Το Deque χρησιμοποιείται γενικά για εφαρμογές που απαιτούν προσθήκη / αφαίρεση στοιχείων και από τα δύο άκρα. Χρησιμοποιείται επίσης κυρίως στον προγραμματισμό των επεξεργαστών σε συστήματα πολλαπλών επεξεργαστών.
=> Δείτε την Πλήρη Σειρά Εκπαίδευσης C ++
Συνιστώμενη ανάγνωση
- Ουρά προτεραιότητας στο STL
- Τι είναι ο έλεγχος σύγκρισης (Μάθετε με παραδείγματα)
- Εκμάθηση Python DateTime με παραδείγματα
- Ταξινόμηση κελύφους σε C ++ με παραδείγματα
- Αποκοπή εντολής στο Unix με παραδείγματα
- Unix Cat Command Syntax, Επιλογές με παραδείγματα
- Χρήση δρομέα στο MongoDB με παραδείγματα
- Ls Command στο Unix με παραδείγματα