C dilinde Queue Veri Yapısı

Selamlar,

Bu yazımda programlama ortamlarında sıkça lazım olan Queue yapısının C dilinde uygulanışını , kendi tasarladığım kütüphane yapısı ile göstereceğim.

Queue yapısı head ve tail değişkenleri kullanılarak FIFO(First in First Out) yapısında tasarlanmış ve uygulanmıştır.

Kuyruk yapısına eleman ekleme işlemi “enqueue” olarak ifade edilir. Enqueue prosedürü :

– Kuyruk pointer’ı ve eklenmek istenen elemanın pointer’ının null pointer olmaması için gerekli kontrol yapılır.
– Kuyruk init edilmiş mi kontrol edilir. Kuyruk dolu mu kontrol edilir. Dolu ise işleme devam edilmez.
– Kontrollerden true sonucu alınmış ise, eleman queue’ya eklenir. Tail değişkeni 1 artırılır. Length 1 artırılır.

Kuyruk yapısından eleman çıkarma işlemi “dequeue” veya olarak ifade edilir. Dequeue prosedürü :

– Kuyruk pointer’ı ve kuyruktan çıkarılacak eleman için verilen çıktı pointer’ının null pointer olmaması için gerekli kontrol yapılır.
– Kuyruk boş mu kontrol edilir. Boş ise işleme devam edilmez.
– Kontrollerden true sonucu alınmış ise, head indisindeki eleman, çıkış pointer’ına kopyalanır. Head indisindeki eleman temizlenir. Head değişkeni 1 artırılır. Length 1 azaltılır.

Algoritmanın C dilinde gerçeklenmesi :

que.h dosyası :

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef struct
{
	int clasroom;
	int number;
}Student_t;

#define dataType Student_t

typedef struct
{
	bool init;
	int capacity;
	int length;
	int head;
	int tail;
	dataType * p_array;
}Queue_t;

bool que_init(Queue_t *p_que);
bool que_isFull(Queue_t *p_que);
bool que_isEmpty(Queue_t *p_que);
bool que_enqueueElement(Queue_t *p_que , dataType *p_element);
bool que_dequeueElement(Queue_t *p_que , dataType *p_outElement);

Queue’nun hangi veri tipi için geçerli olacağı “#define dataType Student_t” ile tanımlanmıştır. Farklı veri tipleri için Queue implement edebilmek için, ilgili veri tipinin h dosyası içinde implement edilmesi ve gerekli define işleminin yapılması yeterlidir.

que.c dosyası :

#include "que.h"

#define QUE_CAPACITY 	8

static dataType dataArray[QUE_CAPACITY] = {0};
static dataType* p_dataArrayPtr = &dataArray[0];

bool que_init(Queue_t *p_que)
{
 bool retVal = false;
	
 if(p_que != 0 && p_dataArrayPtr != 0)
 {
  p_que->capacity = QUE_CAPACITY;
  p_que->tail = 0;
  p_que->head = 0;
  p_que->length = 0;
  p_que->p_array = p_dataArrayPtr;
  p_que->init = true;
  retVal = true;
 }

return retVal;
}

bool que_isFull(Queue_t *p_que)
{
 bool retVal = false;
	
 if((p_que->tail + 1) == p_que->capacity)
 {
  retVal = true;
 }
	 
return retVal;
}


bool que_isEmpty(Queue_t *p_que)
{
 bool retVal = false;
	
 if(p_que->length == 0)
 {
  retVal = true;
 }
	
 return retVal;
}


bool que_enqueueElement(Queue_t *p_que , dataType *p_element)
{
 bool retVal = false;
 uint8_t wrIdx = 0;	

 if((p_que != 0) && (p_element != 0) && (p_que->init == true))
 {
  if(que_isFull(p_que) == false)
  {
   wrIdx = p_que->tail;
   memcpy(&(p_que->p_array[wrIdx ]),p_element,sizeof(dataType));
   p_que->tail ++;
   p_que->length ++;
   retVal = true;
  }
}
	
return retVal;
}


bool que_dequeueElement(Queue_t *p_que , dataType *p_outElement)
{
 bool retVal = false;
 uint8_t rdIdx = 0;
	
 if((p_que != 0) && (p_outElement != 0))
 {
  if(que_isEmpty(p_que) == false)
  {
   rdIdx = p_que->head;
   memcpy(p_outElement,&(p_que->p_array[rdIdx]),sizeof(dataType));
   memset(&(p_que->p_array[p_que->head]) , 0 , sizeof(dataType));
   p_que->head ++;
   p_que->length --;
   retVal = true;
  }
}
	
return retVal;
}

main.c dosyası (Implementasyon)

#include "que.h"

void main(void) {
	
	Queue_t que = {0};
	Student_t student = {0};
	
	que_init(&que);
	
	student.clasroom = 1;
	student.number = 5;
	
	que_enqueueElement(&que , &student);
	
	student.clasroom = 1;
	student.number = 6;
	
	que_enqueueElement(&que , &student);
	
	if(que_dequeueElement(&que , &student) == true)
	{
		printf("First element \n");
		printf("%d\n", student.clasroom);
		printf("%d\n", student.number);
		printf("\n");
	}
	
	if(que_dequeueElement(&que , &student) == true)
	{
		printf("Second element \n");
		printf("%d\n", student.clasroom);
		printf("%d\n", student.number);
		printf("\n");
	}

	if(que_dequeueElement(&que , &student) == true)
	{
		printf("Third element \n");
		printf("%d\n", student.clasroom);
		printf("%d\n", student.number);
		printf("\n");
	}	
}

İmplementasyon çalıştırıldığında 3.elemanın dequeue edilemediğini görebilirsiniz. 2 adet eleman enqueue dilmiş, elemanlar sırası ile dequeue edilmiştir. FIFO yapısı aktif olduğundan, dequeue işlemi uygulandığında ilk enqueue edilen eleman elde edilmiştir.

Çağatay KAYNAK
Gömülü Yazılım Mühendisi
cagataykaynak@gmail.com