Veri Yapısı ve Algoritmalar - Sıra

Sıra, Yığınlara biraz benzeyen soyut bir veri yapısıdır. Yığınlardan farklı olarak, bir kuyruk her iki ucunda da açıktır. Bir uç her zaman veri eklemek (sıraya koymak) için kullanılırken diğeri verileri kaldırmak (sıradan çıkarmak) için kullanılır. Sıra, İlk Giren İlk Çıkar metodolojisini izler, yani ilk önce depolanan veri öğesine ilk olarak erişilir.

Gerçek dünyadaki kuyruk örneği, aracın ilk girdiği ve ilk çıktığı tek şeritli tek yönlü bir yol olabilir. Daha fazla gerçek dünya örneği, bilet gişelerinde ve otobüs duraklarında kuyruklar olarak görülebilir.

Kuyruk Temsili

Şimdi anladığımız gibi, her iki uca da farklı nedenlerle erişiyoruz. Aşağıda verilen şema, kuyruk gösterimini veri yapısı olarak açıklamaya çalışır -

Yığınlarda olduğu gibi, bir kuyruk da Diziler, Bağlantılı Listeler, İşaretçiler ve Yapılar kullanılarak uygulanabilir. Basitlik adına, tek boyutlu diziler kullanarak kuyrukları gerçekleştireceğiz.

Temel işlemler

Kuyruk işlemleri kuyruğu başlatmayı veya tanımlamayı, onu kullanmayı ve ardından hafızadan tamamen silmeyi içerebilir. Burada kuyruklarla ilişkili temel işlemleri anlamaya çalışacağız -

  • enqueue() - kuyruğa bir öğe ekleyin (saklayın).

  • dequeue() - kuyruktaki bir öğeyi kaldırın (erişin).

Yukarıda bahsedilen kuyruk operasyonunu verimli kılmak için birkaç fonksiyon daha gereklidir. Bunlar -

  • peek() - Sıranın önündeki öğeyi kaldırmadan alır.

  • isfull() - Sıranın dolu olup olmadığını kontrol eder.

  • isempty() - Kuyruğun boş olup olmadığını kontrol eder.

Kuyrukta, verileri her zaman sıradan çıkarırız (veya erişiriz). front işaretçi ve kuyruktaki verileri sıralarken (veya saklarken) yardım alırız rear Işaretçi.

Önce bir kuyruğun destekleyici işlevlerini öğrenelim -

dikizlemek()

Bu işlev, verilerin frontkuyruğun. Peek () fonksiyonunun algoritması aşağıdaki gibidir -

Algorithm

begin procedure peek
   return queue[front]
end procedure

Peek () işlevinin C programlama dilinde uygulanması -

Example

int peek() {
   return queue[front];
}

dolu()

Sırayı uygulamak için tek boyutlu dizi kullandığımız için, sıranın dolu olduğunu belirlemek için arka işaretçinin MAXSIZE'a ulaşmasını kontrol ediyoruz. Sırayı döngüsel bağlantılı bir listede tutmamız durumunda, algoritma farklı olacaktır. İsfull () işlevinin algoritması -

Algorithm

begin procedure isfull

   if rear equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

C programlama dilinde isfull () işlevinin uygulanması -

Example

bool isfull() {
   if(rear == MAXSIZE - 1)
      return true;
   else
      return false;
}

boş()

İsempty () fonksiyonunun algoritması -

Algorithm

begin procedure isempty

   if front is less than MIN  OR front is greater than rear
      return true
   else
      return false
   endif
   
end procedure

Eğer değeri front MIN veya 0'dan küçükse, kuyruğun henüz başlatılmadığını, dolayısıyla boş olduğunu söyler.

İşte C programlama kodu -

Example

bool isempty() {
   if(front < 0 || front > rear) 
      return true;
   else
      return false;
}

İşlemi Sırala

Kuyruklar iki veri işaretçisi tutar, front ve rear. Bu nedenle, işlemlerinin uygulanması yığınlardan daha zordur.

Verileri bir kuyruğa sıraya koymak (eklemek) için aşağıdaki adımlar atılmalıdır -

  • Step 1 - Sıranın dolu olup olmadığını kontrol edin.

  • Step 2 - Kuyruk doluysa, taşma hatası üretin ve çıkın.

  • Step 3 - Kuyruk dolu değilse artırın rear sonraki boş alanı gösteren işaretçi.

  • Step 4 - Arka tarafın baktığı kuyruk konumuna veri öğesi ekleyin.

  • Step 5 - başarıya dönüş.

Bazen, öngörülemeyen durumların üstesinden gelmek için bir sıranın başlatılıp başlatılmadığını da kontrol ederiz.

Kuyruklama işlemi için algoritma

procedure enqueue(data)      
   
   if queue is full
      return overflow
   endif
   
   rear ← rear + 1
   queue[rear] ← data
   return true
   
end procedure

C programlama dilinde enqueue () uygulaması -

Example

int enqueue(int data)      
   if(isfull())
      return 0;
   
   rear = rear + 1;
   queue[rear] = data;
   
   return 1;
end procedure

Sıradan Çıkarma İşlemi

Kuyruktan verilere erişim iki görevden oluşan bir süreçtir - verilere erişim fronterişimden sonra verileri işaret ediyor ve kaldırıyor. Gerçekleştirmek için aşağıdaki adımlar atılırdequeue operasyon -

  • Step 1 - Kuyruğun boş olup olmadığını kontrol edin.

  • Step 2 - Kuyruk boşsa, alt akış hatası üretin ve çıkın.

  • Step 3 - Kuyruk boş değilse, verilere buradan erişin front işaret ediyor.

  • Step 4 - Artış front bir sonraki kullanılabilir veri öğesini gösteren işaretçi.

  • Step 5 - Başarıya dönüş.

Kuyruktan çıkarma işlemi için algoritma

procedure dequeue
   
   if queue is empty
      return underflow
   end if

   data = queue[front]
   front ← front + 1
   return true

end procedure

Dequeue () 'nin C programlama dilinde uygulanması -

Example

int dequeue() {
   if(isempty())
      return 0;

   int data = queue[front];
   front = front + 1;

   return data;
}

C programlama dilinde eksiksiz bir Kuyruk programı için lütfen buraya tıklayın .