Home / Veri Yapıları / Öncelik Kuyruğu Nedir?

Öncelik Kuyruğu Nedir?

Size daha önce Diziler ile Kuyruk işlemleri ve Bağlı Liste ile Kuyruk işlemlerinden bahsetmiştik. Şimdi ise oldukça önemli bir husus olan öncelik kuyruk yapısını inceleyecek, ve kod örneğini paylaşacağız.

Normal kuyruk yapısında her yeni eleman kuyruğun en arkasındaki elemanın arkasına gelmekte ve en son gelen eleman, yeni en son eleman olarak güncellenmekteydi. Öncelik kuyruğunda ise temel mantık tam anlamıyla “torpil” üzerinedir. Bu sistemde kimin önce geldiği değil, kimin öncelikli olduğu göz önüne alınmalı ve kuyruğa bu şekilde dahil edilmelidir. Önceliği yüksek olan, önceliği düşük olanların önüne geçer.

Öncelikli kuyruk yapısında kuyruk taranır ve öncelik durumuna göre yerleştirme yapılır. Eğer algoritmayı modifiye etmezseniz işlem karmaşıklığı artabilir, ancak var olan haliyle bile karmaşıktır. Şimdi size bir örnek verelim.

Ahmet (3) – Ali (2) –  Seda(2) – Mehmet(0) – Sadullah (0)

Yukarıdaki kuyruk yapısında Ahmet en önde iken Sadullah en arkadadır. Parantez içerisinde öncelik durumları yer almıştır ve bu yapıya göre sıralama yapılmıştır. Şimdi Kuyruğa Ayşe(4) eklenmek istenirse ne olur?

Algoritma: Kuyruğun en başındaki elemandan başlayıp sırayla öncelikleri karşılaştır, Eğer karşılaştırılan elemanın önceliği düşük ise yeni elemanı öne yerleştir. Yani aşağıdaki gibi kuyruk yapısı oluşur.

Ayşe (4) – Ahmet (3) – Ali (2) –  Seda(2) – Mehmet(0) – Sadullah (0)

Peki yukarıdaki örnek kolay oldu. Şimdi de Deniz(1)’i yerleştirelim.

  • 1. Adım: Ayşe(4) ile Deniz(1)’i karşılaştır. Ayşe(4) büyük olduğu için diğer elemana geç
  • 2. Adım: Ahmet(3) ile Deniz(1)’i karşılaştır. Ahmet(3) büyük olduğu için diğer elemana geç.
  • 3. Adım: Ali(2) ile Deniz(1)’i karşılaştır. Ali(2) büyük olduğu için diğer elemana geç
  • 4. Adım: Seda(2) ile Deniz(1)’i karşılaştır. Seda(2) büyük olduğu için diğer elemana geç.
  • 5. Adım: Mehmet(0) ile Deniz(1)’i karşılaştır. Deniz(1) büyük olduğu için Mehmet(0)’ın önüne yerleştirme yapılır.

Ayşe (4) – Ahmet (3) – Ali (2) –  Seda(2) – Deniz(1) – Mehmet(0) – Sadullah (0)

Öncelik Kuyruğu C Kodu

Öncelik Kuyruğu yapısında esas önemli kısım kuyruğa eleman ekleme işlemidir. Geri kalan diğer tüm işlemler normal kuyruk veri yapısı ile aynıdır. Unutmayın Öncelik Kuyruğu C Kodu bağlı liste ile hazırlanmıştır. Zaten olması gereken budur. Dizi ile yapmaya kalkarsanız araya her ekleme işleminde diziyi kaydırmanız gerekecektir. Bu da anlamsız bir işlemdir.


#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

//Düğüm yapımız, priority yani öncelik diye bir değerimiz olduğuna dikkat ediniz.
struct node{
    char name[20];
    char secondName[20];
    int age;
    int priority;
    struct node *next;
};

//Kuyruğun en ön ve en arka değişkenleri
struct node* head = NULL;
struct node* tail = NULL;
//Geçici değişken
struct node* temp;

char firstName[20], secondName[20];
int age, pri;
char priority[10];

//Düğüm oluşturan fonksiyon
struct node* createPerson(char name[], char secondName[], int age, int priority)
{
    struct node* newPerson = (struct node*)malloc(sizeof(struct node));
    strcpy(newPerson->name, name);
    strcpy(newPerson->secondName, secondName);
    newPerson->age = age;
    newPerson->priority = priority;
    newPerson->next = NULL;

    return newPerson;
};

//Kuyruğa öncelik sırasına göre eleman ekleyen fonksiyon
void enQueuePerson(char name[], char secondName[], int age, int priority)
{
    struct node* person = createPerson(name, secondName, age, priority);
    //Eğer kuyruğumuz boş ise yeni elemanımız hem en öndeki hem en arkadaki oluyor.
    if(head == NULL && tail == NULL)
    {
        head = person;
        tail = person;
    }
    else
    {
        //ilk olarak yeni eklenecek olan kişi, kuyruğun en önündeki kişinin önceliğinden büyük mü ona bakııyoruz.
        //Çok önemli not, Sitede konuyu anlatırken sayısı büyük olanın önceliği büyüktür demiştim, ama kod yapısında
        //Önceliği 1 olan 2 olandan daha yüksek öncelikli oluyor
        //Yani eğer yeni kişinin önceliği kuyruğun birinci sırasındakinden daha fazla ise direkt en öne geçiyor.
        if(person->priority <= head->priority)
        {
            temp = head;
            head = person;
            person->next = temp;
            return;
        }
        //Eğer yeni eklenecek kişinin önceliği kuyruğun en arkasındaki kişiden düşükse tek tek bakmaya gerek kalmadan
        //kuyruğun en arkasına atıyoruz.
        if(person->priority >= tail->priority)
        {
            tail->next = person;
            tail = person;
        }

        //Aşağıdaki döngü kodumuzun esasını oluşturuyor.
        temp = head;
        //Traverse için While döngüsü kullanıyoruz.
        while(temp->next != NULL)
        {
            //Eğer eklenecek olan kişi bir değerin önceliğinden daha yüksek ise önüne ekleniyor.
            if(person->priority < temp->next->priority)
            {
                struct node* newy;
                newy = temp->next;
                temp->next = person;
                person->next = newy;
            }
            temp = temp->next;
        }
    }
}

//kuyruktan eleman çıkarma işlemi sırasında öncelik değerleri önemsizdir. Normal çıkarma fonksiyonudur.
//Esas olay zaten yukarıdaki ekleme işlemidir. 
void deQueue()
{
    temp = head;
    if(head == NULL)
    {
        printf("\nQueue is empty, pls Enqueue");
        return;
    }

    if(head == tail)
    {
        head = NULL;
        tail = NULL;
        return;
    }

    head = temp->next;
    free(temp);
}

//Kuyruğun en önünde kim var?
struct node* whoNext()
{
    if(head == NULL)
    {
        printf("\nThere is no item in queue...");
        return 0;
    }

    return head;
}

//Öncelik kontrolü için bir fonksiyon. 
void checkPri(int x)
{
    if(x == 1)
            strcpy(priority, "High");
        else if(x == 2)
            strcpy(priority, "Normal");
        else
            strcpy(priority, "Low");
}

//Kuyruğun mevcut yapısını ekrana basan fonksiyon
void printQueue()
{

    int i = 1;
    if(head == NULL)
    {
        return;
    }
    temp = head;
    while(temp->next != NULL)
    {
        checkPri(temp->priority);
        printf("\n%d. Position => %s %s %d priority ==> %s ", i, temp->name, temp->secondName, temp->age, priority);
        temp = temp->next;
        i++;
    }
    checkPri(temp->priority);
    printf("\n%d. Position => %s %s %d priority ==> %s ", i, temp->name, temp->secondName, temp->age, priority);
}


//Bu da menu fonksiyonumuz.
void menu()
{
    int choise;
    while( 1 == 1 )
    {
        printf("\n 1- Enqueue ... ");
        printf("\n 2- Dequeue ... ");
        printf("\n 3- Who's next? ");
        printf("\nmake your choise ");
        scanf("%d", &choise);
        selection(choise);
    }
}

void selection(int chosen)
{
    switch(chosen)
    {
        case 1:
            printf("\n Enter First Name ... ");
            scanf("%s", &firstName);
            printf("\n Enter Second Name ... ");
            scanf("%s", &secondName);
            printf("\n Enter Age ... ");
            scanf("%d", &age);
            printf("\n Enter Priority ... (1 is High | 2 is Normal | 3 is Low) ");
            scanf("%d", &pri);
            enQueuePerson(firstName, secondName, age, pri);
            printQueue();
            break;
        case 2:
            deQueue();
            printQueue();
            break;
        case 3:
            temp = whoNext();
            printf("\n ****************** \n");
            if(temp != NULL)
            {
                printf("%s %s %d", temp->name, temp->secondName, temp->age);
            }
            break;
    }
}

int main()
{
    menu();
    return 0;
}

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir