Bu eğitimde sıranın ne olduğunu öğreneceksiniz. Ayrıca kuyruk uygulamalarını C, C ++, Java ve Python'da bulacaksınız.
Kuyruk, programlamada yararlı bir veri yapısıdır. Sinema salonunun dışındaki bilet kuyruğuna benzer, burada sıraya ilk giren kişi bileti alan ilk kişi olur.
Sıra, İlk Giren İlk Çıkar (FIFO) kuralını izler - ilk giren öğe ilk çıkan öğedir.
Kuyruğun FIFO Temsili
Yukarıdaki görüntüde 1, 2'den önce kuyrukta tutulduğundan, kuyruktan da ilk çıkarılacak olanıdır. FIFO kuralını izler .
Terimleri programlama denir kuyruğunda öğeleri koyarak yılında enqueue ve kuyruktaki öğeleri kaldırmayla denir dequeue .
Sırayı C, C ++, Java, Python veya C # gibi herhangi bir programlama dilinde uygulayabiliriz, ancak şartname hemen hemen aynıdır.
Temel Kuyruk İşlemleri
Kuyruk, aşağıdaki işlemlere izin veren bir nesnedir (soyut bir veri yapısı - ADT):
- Sırala : Sıranın sonuna bir öğe ekleyin
- Sıradan çıkarma : Sıranın önünden bir öğeyi kaldırın
- IsEmpty : Kuyruğun boş olup olmadığını kontrol edin
- IsFull : Kuyruğun dolu olup olmadığını kontrol edin
- Göz at : Sıranın ön kısmının değerini çıkarmadan elde edin
Kuyruğun Çalışması
Kuyruk işlemleri şu şekilde çalışır:
- iki işaretçi ÖN ve ARKA
- ÖN kuyruğun ilk öğesini takip edin
- REAR kuyruğun son öğesini takip eder
- başlangıçta FRONT ve REAR değerini -1 olarak ayarlayın
İşlemi Sırala
- sıranın dolu olup olmadığını kontrol edin
- ilk öğe için FRONT değerini 0 olarak ayarlayın
- REAR endeksini 1 artır
- REAR ile gösterilen konuma yeni elemanı ekleyin
Sıradan Çıkarma İşlemi
- sıranın boş olup olmadığını kontrol edin
- FRONT ile gösterilen değeri döndür
- FRONT endeksini 1 artır
- son eleman için FRONT ve REAR değerlerini -1 olarak sıfırlayın
Sıraya Alma ve Sıradan Çıkarma İşlemleri
Python, Java, C ve C ++ 'da Sıra Uygulamaları
Java ve C / ++ 'da kuyrukları uygulamak için genellikle dizileri kullanırız. Python söz konusu olduğunda listeleri kullanırız.
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; )
Sıranın Sınırlamaları
Aşağıdaki resimde de görebileceğiniz gibi, biraz kuyruğa alma ve kuyruğundan çıkarma işleminden sonra kuyruğun boyutu küçültülmüştür.
Bir kuyruğun sınırlandırılması
Ve sadece sıra sıfırlandığında (tüm elemanlar kuyruktan çıkarıldığında) sadece 0 ve 1 dizinlerini ekleyebiliriz.
REAR son indekse ulaştıktan sonra boş alanlara (0 ve 1) fazladan eleman depolayabilirsek boş alanlardan faydalanabiliriz. Bu, döngüsel kuyruk adı verilen değiştirilmiş bir kuyruk tarafından gerçekleştirilir.
Karmaşıklık Analizi
Bir dizi kullanan bir kuyruktaki kuyruğa alma ve kuyruktan çıkarma işlemlerinin karmaşıklığı O(1).
Kuyruk Uygulamaları
- CPU planlama, Disk Planlama
- Veriler iki işlem arasında eşzamansız olarak aktarıldığında Kuyruk senkronizasyon için kullanılır Örneğin: GÇ Tamponları, borular, dosya GÇ, vb.
- Gerçek zamanlı sistemlerde kesintilerin ele alınması.
- Çağrı Merkezi telefon sistemleri, onları arayan kişileri sırayla tutmak için Kuyrukları kullanır.
Önerilen Okumalar
- Kuyruk Türleri
- Dairesel Sıra
- Deque Data Yapısı
- Öncelik Kuyruğu
