Σε αυτό το σεμινάριο, θα μάθετε τι είναι η ουρά. Επίσης, θα βρείτε την εφαρμογή της ουράς σε C, C ++, Java και Python.
Η ουρά είναι μια χρήσιμη δομή δεδομένων στον προγραμματισμό. Είναι παρόμοιο με την ουρά εισιτηρίων έξω από μια αίθουσα κινηματογράφου, όπου το πρώτο άτομο που μπαίνει στην ουρά είναι το πρώτο άτομο που παίρνει το εισιτήριο.
Η ουρά ακολουθεί τον κανόνα First In First Out (FIFO) - το στοιχείο που μπαίνει πρώτο είναι το στοιχείο που βγαίνει πρώτο.
FIFO Αναπαράσταση της ουράς
Στην παραπάνω εικόνα, δεδομένου ότι το 1 διατηρήθηκε στην ουρά πριν από το 2, είναι και το πρώτο που πρέπει να αφαιρεθεί από την ουρά. Ακολουθεί τον κανόνα FIFO .
Σε όρους προγραμματισμού, η τοποθέτηση αντικειμένων στην ουρά ονομάζεται enqueue και η αφαίρεση αντικειμένων από την ουρά ονομάζεται dequeue .
Μπορούμε να εφαρμόσουμε την ουρά σε οποιαδήποτε γλώσσα προγραμματισμού όπως C, C ++, Java, Python ή C #, αλλά η προδιαγραφή είναι σχεδόν η ίδια.
Βασικές λειτουργίες της ουράς
Η ουρά είναι ένα αντικείμενο (μια αφηρημένη δομή δεδομένων - ADT) που επιτρέπει τις ακόλουθες λειτουργίες:
- Enqueue : Προσθέστε ένα στοιχείο στο τέλος της ουράς
- Dequeue : Αφαιρέστε ένα στοιχείο από το μπροστινό μέρος της ουράς
- IsEmpty : Ελέγξτε εάν η ουρά είναι κενή
- IsFull : Ελέγξτε εάν η ουρά είναι πλήρης
- Ρίξτε μια ματιά : Αποκτήστε την τιμή του μπροστινού μέρους της ουράς χωρίς να την αφαιρέσετε
Εργασία της ουράς
Οι λειτουργίες ουράς λειτουργούν ως εξής:
- δύο δείκτες Μπροστά και ΠΙΣΩ
- FRONT παρακολουθείτε το πρώτο στοιχείο της ουράς
- ΠΙΣΩ παρακολουθείτε το τελευταίο στοιχείο της ουράς
- αρχικά, ορίστε την τιμή FRONT και REAR σε -1
Λειτουργία Enqueue
- ελέγξτε αν η ουρά είναι γεμάτη
- για το πρώτο στοιχείο, ορίστε την τιμή του FRONT στο 0
- αύξηση του δείκτη REAR κατά 1
- προσθέστε το νέο στοιχείο στη θέση που δείχνει ο REAR
Λειτουργία Dequeue
- ελέγξτε αν η ουρά είναι κενή
- επιστρέψτε την τιμή που δείχνει ο FRONT
- αύξηση του δείκτη FRONT κατά 1
- για το τελευταίο στοιχείο, επαναφέρετε τις τιμές FRONT και REAR σε -1
Λειτουργίες Enqueue και Dequeue
Εφαρμογές ουράς σε Python, Java, C και C ++
Συνήθως χρησιμοποιούμε πίνακες για την εφαρμογή ουρών σε Java και C / ++. Στην περίπτωση της Python, χρησιμοποιούμε λίστες.
Python Java C C ++ # Queue implementation in Python class Queue: def __init__(self): self.queue = () # Add an element def enqueue(self, item): self.queue.append(item) # Remove an element def dequeue(self): if len(self.queue) < 1: return None return self.queue.pop(0) # Display the queue def display(self): print(self.queue) def size(self): return len(self.queue) q = Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.display() q.dequeue() print("After removing an element") q.display()
// Queue implementation in Java public class Queue ( int SIZE = 5; int items() = new int(SIZE); int front, rear; Queue() ( front = -1; rear = -1; ) boolean isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) boolean isEmpty() ( if (front == -1) return true; else return false; ) void enQueue(int element) ( if (isFull()) ( System.out.println("Queue is full"); ) else ( if (front == -1) front = 0; rear++; items(rear) = element; System.out.println("Inserted " + element); ) ) int deQueue() ( int element; if (isEmpty()) ( System.out.println("Queue is empty"); return (-1); ) else ( element = items(front); if (front>= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) System.out.println("Deleted -> " + element); return (element); ) ) void display() ( /* Function to display elements of Queue */ int i; if (isEmpty()) ( System.out.println("Empty Queue"); ) else ( System.out.println("Front index-> " + front); System.out.println("Items -> "); for (i = front; i " + rear); ) ) public static void main(String() args) ( Queue q = new Queue(); // deQueue is not possible on empty queue q.deQueue(); // enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // 6th element can't be added to because the queue is full q.enQueue(6); q.display(); // deQueue removes element entered first i.e. 1 q.deQueue(); // Now we have just 4 elements q.display(); ) )
// Queue implementation in C #include #define SIZE 5 void enQueue(int); void deQueue(); void display(); int items(SIZE), front = -1, rear = -1; int main() ( //deQueue is not possible on empty queue deQueue(); //enQueue 5 elements enQueue(1); enQueue(2); enQueue(3); enQueue(4); enQueue(5); // 6th element can't be added to because the queue is full enQueue(6); display(); //deQueue removes element entered first i.e. 1 deQueue(); //Now we have just 4 elements display(); return 0; ) void enQueue(int value) ( if (rear == SIZE - 1) printf("Queue is Full!!"); else ( if (front == -1) front = 0; rear++; items(rear) = value; printf("Inserted -> %d", value); ) ) void deQueue() ( if (front == -1) printf("Queue is Empty!!"); else ( printf("Deleted : %d", items(front)); front++; if (front> rear) front = rear = -1; ) ) // Function to print the queue void display() ( if (rear == -1) printf("Queue is Empty!!!"); else ( int i; printf("Queue elements are:"); for (i = front; i <= rear; i++) printf("%d ", items(i)); ) printf(""); )
// Queue implementation in C++ #include #define SIZE 5 using namespace std; class Queue ( private: int items(SIZE), front, rear; public: Queue() ( front = -1; rear = -1; ) bool isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) bool isEmpty() ( if (front == -1) return true; else return false; ) void enQueue(int element) ( if (isFull()) ( cout << "Queue is full"; ) else ( if (front == -1) front = 0; rear++; items(rear) = element; cout << endl << "Inserted " << element << endl; ) ) int deQueue() ( int element; if (isEmpty()) ( cout << "Queue is empty" <= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) cout << endl < " << element << endl; return (element); ) ) void display() ( /* Function to display elements of Queue */ int i; if (isEmpty()) ( cout << endl << "Empty Queue" << endl; ) else ( cout << endl < " << front; cout << endl < "; for (i = front; i <= rear; i++) cout << items(i) << " "; cout << endl < " << rear << endl; ) ) ); int main() ( Queue q; //deQueue is not possible on empty queue q.deQueue(); //enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // 6th element can't be added to because the queue is full q.enQueue(6); q.display(); //deQueue removes element entered first i.e. 1 q.deQueue(); //Now we have just 4 elements q.display(); return 0; )
Περιορισμοί της ουράς
Όπως μπορείτε να δείτε στην παρακάτω εικόνα, μετά από λίγη επεξεργασία και αποσυμπίεση, το μέγεθος της ουράς μειώθηκε.
Περιορισμός της ουράς
Και μπορούμε να προσθέσουμε ευρετήρια 0 και 1 μόνο όταν γίνεται επαναφορά της ουράς (όταν όλα τα στοιχεία έχουν αφαιρεθεί).
Αφού το REAR φτάσει στο τελευταίο ευρετήριο, εάν μπορούμε να αποθηκεύσουμε επιπλέον στοιχεία στους κενούς χώρους (0 και 1), μπορούμε να χρησιμοποιήσουμε τους κενούς χώρους. Αυτό υλοποιείται από μια τροποποιημένη ουρά που ονομάζεται κυκλική ουρά.
Ανάλυση πολυπλοκότητας
Η πολυπλοκότητα των λειτουργιών enqueue και dequeue σε μια ουρά χρήση μίας συστοιχίας είναι O(1).
Εφαρμογές ουράς
- Προγραμματισμός CPU, Προγραμματισμός δίσκου
- Όταν τα δεδομένα μεταφέρονται ασύγχρονα μεταξύ δύο διεργασιών. Η ουρά χρησιμοποιείται για συγχρονισμό. Για παράδειγμα: IO Buffers, σωλήνες, αρχείο IO, κ.λπ.
- Χειρισμός διακοπών σε συστήματα πραγματικού χρόνου.
- Τα τηλεφωνικά συστήματα Call Center χρησιμοποιούν ουρές για να κρατούν τα άτομα που τα καλούν σε σειρά.
Προτεινόμενες αναγνώσεις
- Τύποι ουράς
- Κυκλική ουρά
- Δομή δεδομένων Deque
- Ουρά προτεραιότητας
