Μενού

Δομή δεδομένων ουράς σε C ++ με απεικόνιση

queue data structure c with illustration

Δοκιμάστε Το Όργανο Μας Για Την Εξάλειψη Των Προβλημάτων

Μια σύντομη εισαγωγή στην ουρά στο C ++ με απεικόνιση.

Η ουρά είναι μια βασική δομή δεδομένων όπως μια στοίβα. Σε αντίθεση με τη στοίβα που χρησιμοποιεί την προσέγγιση LIFO, η ουρά χρησιμοποιεί την προσέγγιση FIFO (first in, first out). Με αυτήν την προσέγγιση, το πρώτο στοιχείο που προστίθεται στην ουρά είναι το πρώτο στοιχείο που πρέπει να αφαιρεθεί από την ουρά. Ακριβώς όπως το Stack, η ουρά είναι επίσης μια γραμμική δομή δεδομένων.

οι καλύτεροι ιστότοποι για να παρακολουθείτε δωρεάν anime στο διαδίκτυο

Σε μια αναλογία πραγματικού κόσμου, μπορούμε να φανταστούμε μια ουρά λεωφορείων όπου οι επιβάτες περιμένουν το λεωφορείο σε μια ουρά ή μια γραμμή. Ο πρώτος επιβάτης στη γραμμή μπαίνει πρώτα στο λεωφορείο καθώς αυτός ο επιβάτης τυχαίνει να είναι αυτός που είχε έρθει πρώτος.

=> Διαβάστε τη δημοφιλή σειρά εκπαιδευτικών C ++ εδώ.

Ουρά σε C ++

Τι θα μάθετε:

Ουρά σε C ++

Σε όρους λογισμικού, η ουρά μπορεί να θεωρηθεί ως σύνολο ή συλλογή στοιχείων όπως φαίνεται παρακάτω. Τα στοιχεία διατάσσονται γραμμικά.

Ουρά

Έχουμε δύο άκρα, δηλαδή 'μπροστά' και 'πίσω' της ουράς. Όταν η ουρά είναι κενή, τότε και οι δύο δείκτες έχουν οριστεί στο -1.

Ο «πίσω» τελικός δείκτης είναι το μέρος από το οποίο εισάγονται τα στοιχεία στην ουρά. Η λειτουργία προσθήκης / εισαγωγής στοιχείων στην ουρά ονομάζεται 'enqueue'.

Ο 'μπροστινός' τελικός δείκτης είναι το μέρος από το οποίο αφαιρούνται τα στοιχεία από την ουρά. Η λειτουργία αφαίρεσης / διαγραφής στοιχείων από την ουρά ονομάζεται 'dequeue'.

Όταν η τιμή του πίσω δείκτη είναι μέγεθος-1, τότε λέμε ότι η ουρά είναι γεμάτη. Όταν το μέτωπο είναι μηδενικό, τότε η ουρά είναι κενή.

Βασικές λειτουργίες

Η δομή δεδομένων ουράς περιλαμβάνει τις ακόλουθες λειτουργίες:

  • EnQueue: Προσθέτει ένα στοιχείο στην ουρά. Η προσθήκη ενός αντικειμένου στην ουρά γίνεται πάντα στο πίσω μέρος της ουράς.
  • DeQueue: Καταργεί ένα στοιχείο από την ουρά. Ένα στοιχείο αφαιρείται ή απενεργοποιείται πάντα από το μπροστινό μέρος της ουράς.
  • είναι άδειο: Ελέγχει εάν η ουρά είναι κενή.
  • είναι γεμάτο: Ελέγχει εάν η ουρά είναι γεμάτη.
  • κρυφοκοίταγμα: Παίρνει ένα στοιχείο στο μπροστινό μέρος της ουράς χωρίς να το αφαιρέσετε.

Enqueue

Σε αυτήν τη διαδικασία, εκτελούνται τα ακόλουθα βήματα:

  • Ελέγξτε αν η ουρά είναι γεμάτη.
  • Εάν είναι πλήρης, δημιουργήστε σφάλμα υπερχείλισης και βγείτε.
  • Διαφορετικά, αυξήστε το «πίσω».
  • Προσθέστε ένα στοιχείο στην τοποθεσία που επισημαίνεται με το «πίσω».
  • Επιστροφή επιτυχία.

Ντεκουέ

Η λειτουργία Dequeue αποτελείται από τα ακόλουθα βήματα:

  • Ελέγξτε εάν η ουρά είναι κενή.
  • Εάν είναι άδειο, εμφανίστε ένα σφάλμα underflow και βγείτε.
  • Αλλιώς, το στοιχείο πρόσβασης επισημαίνεται από το «μπροστινό».
  • Αυξήστε το «μπροστινό» για να δείξετε τα επόμενα προσβάσιμα δεδομένα.
  • Επιστροφή επιτυχία.

Στη συνέχεια, θα δούμε μια λεπτομερή απεικόνιση των λειτουργιών εισαγωγής και διαγραφής στην ουρά.

Απεικόνιση

απεικόνιση της εισαγωγής και διαγραφής στην ουρά

Αυτή είναι μια κενή ουρά και έτσι έχουμε το πίσω και το κενό σε -1.

Στη συνέχεια, προσθέτουμε 1 στην ουρά και ως αποτέλεσμα, ο πίσω δείκτης κινείται μπροστά από μία θέση.

Λειτουργία EnQueue

Στο επόμενο σχήμα, προσθέτουμε το στοιχείο 2 στην ουρά μετακινώντας τον πίσω δείκτη μπροστά με άλλη αύξηση.

προσθέστε το στοιχείο 2 στην ουρά

Στο παρακάτω σχήμα, προσθέτουμε το στοιχείο 3 και μετακινούμε τον πίσω δείκτη κατά 1.

προσθήκη στοιχείου 3

Σε αυτό το σημείο, ο πίσω δείκτης έχει τιμή 2 ενώ ο μπροστινός δείκτης βρίσκεται στο 0ουτοποθεσία.

Στη συνέχεια, διαγράφουμε το στοιχείο που δείχνει ο μπροστινός δείκτης. Καθώς ο μπροστινός δείκτης είναι στο 0, το στοιχείο που διαγράφεται είναι 1.

Λειτουργία DeQueue

Έτσι, το πρώτο στοιχείο που εισάγεται στην ουρά, δηλαδή 1 τυχαίνει να είναι το πρώτο στοιχείο που αφαιρείται από την ουρά. Ως αποτέλεσμα, μετά το πρώτο dequeue, ο μπροστινός δείκτης θα μετακινηθεί μπροστά στην επόμενη θέση που είναι 1.

Υλοποίηση σειράς για ουρά

Ας εφαρμόσουμε τη δομή δεδομένων ουράς χρησιμοποιώντας το C ++.

#include #define MAX_SIZE 5 using namespace std; class Queue { private: int myqueue(MAX_SIZE), front, rear; public: Queue(){ front = -1; rear = -1; } boolisFull(){ if(front == 0 && rear == MAX_SIZE - 1){ return true; } return false; } boolisEmpty(){ if(front == -1) return true; else return false; } void enQueue(int value){ if(isFull()){ cout << endl<< 'Queue is full!!'; } else { if(front == -1) front = 0; rear++; myqueue(rear) = value; cout << value << ' '; } } int deQueue(){ int value; if(isEmpty()){ cout << 'Queue is empty!!' <= rear){ //only one element in queue front = -1; rear = -1; } else { front++; } cout << endl < ' << value << ' from myqueue'; return(value); } } /* Function to display elements of Queue */ void displayQueue() { int i; if(isEmpty()) { cout << endl << 'Queue is Empty!!' << endl; } else { cout << endl << 'Front = ' << front; cout << endl << 'Queue elements : '; for(i=front; i<=rear; i++) cout << myqueue(i) << ' '; cout << endl << 'Rear = ' << rear << endl; } } }; int main() { Queue myq; myq.deQueue(); //deQueue cout<<'Queue created:'< queue is full myq.enQueue(60); myq.displayQueue(); //deQueue =>removes 10 myq.deQueue(); //queue after dequeue myq.displayQueue(); return 0; }

Παραγωγή:

Η ουρά είναι άδεια !!
Δημιουργήθηκε ουρά:
10 20 30 40 50
Η ουρά είναι γεμάτη !!
Μπροστά = 0
Στοιχεία ουράς: 10 20 30 40 50
Πίσω = 4

Διαγράφηκε => 10 από το myqueue
Μπροστά = 1
Στοιχεία ουράς: 20 30 40 50
Πίσω = 4

Η παραπάνω εφαρμογή δείχνει την ουρά που αναπαρίσταται ως πίνακας. Καθορίζουμε το μέγιστο μέγεθος για τον πίνακα. Ορίζουμε επίσης τις λειτουργίες enqueue και dequeue, καθώς και τις λειτουργίες isFull και isEmpty.

Δίνεται παρακάτω η εφαρμογή Java της δομής δεδομένων ουράς.

// A class representing a queue class Queue { int front, rear, size; int max_size; int myqueue(); public Queue(int max_size) { this.max_size = max_size; front = this.size = 0; rear = max_size - 1; myqueue = new int(this.max_size); } //if size = max_size , queue is full boolean isFull(Queue queue) { return (queue.size == queue.max_size); } // size = 0, queue is empty boolean isEmpty(Queue queue) { return (queue.size == 0); } // enqueue - add an element to the queue void enqueue( int item) { if (isFull(this)) return; this.rear = (this.rear + 1)%this.max_size; this.myqueue(this.rear) = item; this.size = this.size + 1; System.out.print(item + ' ' ); } // dequeue - remove an elment from the queue int dequeue() { if (isEmpty(this)) return Integer.MIN_VALUE; int item = this.myqueue(this.front); this.front = (this.front + 1)%this.max_size; this.size = this.size - 1; return item; } // move to front of the queue int front() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.myqueue(this.front); } // move to the rear of the queue int rear() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.myqueue(this.rear); } } // main class class Main { public static void main(String() args) { Queue queue = new Queue(1000); System.out.println('Queue created as:'); queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); queue.enqueue(40); System.out.println(' Element ' + queue.dequeue() + ' dequeued from queue '); System.out.println('Front item is ' + queue.front()); System.out.println('Rear item is ' + queue.rear()); } }

Παραγωγή:

Η ουρά δημιουργήθηκε ως:
10 20 30 40
Στοιχείο 10 από την ουρά

Το μπροστινό αντικείμενο είναι 20
Το οπίσθιο αντικείμενο είναι 40

Η παραπάνω εφαρμογή είναι παρόμοια με την εφαρμογή C ++.

Στη συνέχεια, ας εφαρμόσουμε την ουρά στο C ++ χρησιμοποιώντας μια συνδεδεμένη λίστα.

Εφαρμογή συνδεδεμένης λίστας για ουρά:

#include using namespace std; struct node { int data; struct node *next; }; struct node* front = NULL; struct node* rear = NULL; struct node* temp; void Insert(int val) { if (rear == NULL) { rear = new node; rear->next = NULL; rear->data = val; front = rear; } else { temp=new node; rear->next = temp; temp->data = val; temp->next = NULL; rear = temp; } } void Delete() { temp = front; if (front == NULL) { cout<<'Queue is empty!!'next; cout<<'Element deleted from queue is : '

Παραγωγή:

Δημιουργία ουράς:
10 20 30 40 50
Το στοιχείο που διαγράφηκε από την ουρά είναι: 10
Ουρά μετά από μία διαγραφή:
20 30 40 50

vr ακουστικά για pc και ps4

Στοίβα Vs. Ουρά

Οι στοίβες και οι ουρές είναι δευτερεύουσες δομές δεδομένων που μπορούν να χρησιμοποιηθούν για την αποθήκευση δεδομένων. Μπορούν να προγραμματιστούν χρησιμοποιώντας τις κύριες δομές δεδομένων, όπως πίνακες και συνδεδεμένες λίστες. Έχοντας συζητήσει λεπτομερώς και τις δύο δομές δεδομένων, ήρθε η ώρα να συζητήσουμε τις κύριες διαφορές μεταξύ αυτών των δύο δομών δεδομένων.

ΣτοίβεςΟυρές
Χρησιμοποιεί την προσέγγιση LIFO (Last in, First out).Χρησιμοποιεί την προσέγγιση FIFO (First in, First out).
Τα στοιχεία προστίθενται ή διαγράφονται από ένα μόνο άκρο που ονομάζεται 'Κορυφή' της στοίβας.Τα στοιχεία προστίθενται από το 'Πίσω' άκρο της ουράς και αφαιρούνται από το 'εμπρός' της ουράς.
Οι βασικές λειτουργίες για το stack είναι «push» και «Pop».Οι βασικές λειτουργίες για μια ουρά είναι «enqueue» και «dequeue».
Μπορούμε να κάνουμε όλες τις λειτουργίες στη στοίβα διατηρώντας μόνο έναν δείκτη για πρόσβαση στην κορυφή της στοίβας.Στις ουρές, πρέπει να διατηρήσουμε δύο δείκτες, έναν για πρόσβαση στο μπροστινό μέρος της ουράς και το δεύτερο για πρόσβαση στο πίσω μέρος της ουράς.
Η στοίβα χρησιμοποιείται κυρίως για την επίλυση αναδρομικών προβλημάτων.Οι ουρές χρησιμοποιούνται για την επίλυση προβλημάτων που σχετίζονται με την παραγγελία.

Εφαρμογές ουράς

Ας συζητήσουμε τις διάφορες εφαρμογές της δομής δεδομένων ουράς παρακάτω.

  • Η δομή δεδομένων ουράς χρησιμοποιείται σε διάφορους προγραμματιστές CPU και δίσκου. Εδώ έχουμε πολλές εργασίες που απαιτούν CPU ή δίσκο ταυτόχρονα. Ο χρόνος CPU ή δίσκου έχει προγραμματιστεί για κάθε εργασία χρησιμοποιώντας μια ουρά.
  • Η ουρά μπορεί επίσης να χρησιμοποιηθεί για εκτύπωση τυλίγματος όπου ο αριθμός των εργασιών εκτύπωσης τοποθετείται σε ουρά.
  • Ο χειρισμός των διακοπών σε συστήματα σε πραγματικό χρόνο γίνεται χρησιμοποιώντας μια δομή δεδομένων ουράς. Οι διακοπές διακόπτονται με τη σειρά που φτάνουν.
  • Πρώτη αναζήτηση εύρους στην οποία διασχίζονται οι γειτονικοί κόμβοι ενός δέντρου πριν προχωρήσει στο επόμενο επίπεδο χρησιμοποιεί μια ουρά για εφαρμογή.
  • Τα τηλεφωνικά συστήματα τηλεφωνικών κέντρων χρησιμοποιούν ουρές για να κρατούν τις κλήσεις μέχρι να απαντηθούν από τους εκπροσώπους των υπηρεσιών.

Σε γενικές γραμμές, μπορούμε να πούμε ότι η δομή δεδομένων ουράς χρησιμοποιείται όποτε απαιτείται η εξυπηρέτηση των πόρων ή των στοιχείων με τη σειρά που φθάνουν, δηλαδή Πρώτο σε, Πρώτο Έξοδος.

συμπέρασμα

Η ουρά είναι μια δομή δεδομένων FIFO (First In, First Out) που χρησιμοποιείται κυρίως σε πόρους όπου απαιτείται προγραμματισμός. Έχει δύο δείκτες πίσω και μπροστά στα δύο άκρα και χρησιμοποιούνται για την εισαγωγή ενός στοιχείου και την αφαίρεση ενός στοιχείου από / προς την ουρά αντίστοιχα.

Στο επόμενο σεμινάριό μας, θα μάθουμε για ορισμένες από τις επεκτάσεις της ουράς, όπως ουρά προτεραιότητας και κυκλική ουρά.

=> Δείτε εδώ για να εξερευνήσετε την πλήρη λίστα μαθημάτων C ++.

Συνιστώμενη ανάγνωση

^