Queue Abstract Data Type (With Implementation)

Reading Time: 3 minutes

අද Algo පාඩමෙන් කතා කරන්න යන්නේ Queue සම්බන්ධව. මේකෙදි Queue එකක් කියලා අර්ථ දක්වන්න තියෙන්නෙත් සාමාන්‍ය ජීවිතේදි අපි අත්දකින Queue එකම තමයි. ඒ කියන්නේ පේලියක් කියන එක. අපි මුලින්ම බලමු Queue එකක තියෙන ලක්ෂණ මොනවද කියලා.

FIFO?

FIFO කියන එකෙන් අදහස් වෙන්නේ First In First Out කියන එක. ඒ කියන්නේ අපි සාමාන්‍ය ජීවිතේදි දකින පේලි වලත් වෙන්නේ ඉස්සරලාම පේලියට එකතු වුණ කෙනා තමයි මුලින්ම පේලියෙන් එළියට යන්නේ. හැබැයි මතකද අපි කලින් ලිපියෙ Stacks ගැන කියන වෙලාවෙදි LIFO එකක් ගැන කිවුවා. ඒක බැලුවෙ නැත්නම් මෙතනින් බලන්න. ඒකෙදි අපි කලේ මේකෙ විරුද්ධ වැඩේ.

Basic Operations

Queue එකක තියෙන මූලිකම මෙහෙයුම් කිහිපය තමයි මේ පහලින් තියෙන්නේ.

1. Enqueue
2. Dequeue
3. Peek
4. isFull
5. isEmplty

මේ Method ටිකත් අපි කලින් කතා කරපු Stack එකට ගොඩක් සමානයි.

Peek : 

Data එකක් එළියට ගන්නේ නැතිව මුලින්ම(Front) තියෙන Data එක බලන Method එක.

Algorithm:

begin procedure peek

   return queue[front]
   
end procedure

Implementation ( C )

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

isFull : 

Queue එක සම්පූර්ණයෙන්ම පිරිලාද නැද්ද Check කරන Method එක. මේකෙදි අපි කරන්නේ Queue එකේ Rear Point එක Queue එකේ Max Size එකට සමාන වුණොත් True Return කරනවා.

Algorithm:

begin procedure isfull

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

Implementation ( C )

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

isEmpty : 

Queue එක හිස් වෙලා තියනවද කියලා Check කරන Method එක. Queue එකක් Empty ද නැද්ද කියලා බලන්නේ Front එකේ Value එක Queue එකේ තියෙන්න පුළුවන් අඩුම අගයට එහෙම නැත්නම් 0ට වඩා අඩුයිද කියලා Check කරන එක.

Algorithm:

begin procedure isempty

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

Implementation ( C )

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

Enqueue : 

Queue එකට Data Insert කරන Method එක. මේකෙදි අපි පියවර කිහිපයක් අනුගමනය කරනවා Data එකක් Queue එක ඇතුලට දාන්න කලින් අපි එකින් එක පියවර විස්තර ඇතිව බලමු.

පළමු පියවර : Queue එක දැනට Full ද කියලා Check කරන එක. ඒ කියන්නේ Queue එක Full වෙලා තිබුණොත් අපිට තවත් Data Insert කරන්න බෑනෙ. ඒක මේ Check එකෙන් පස්සේ Full වෙලා තිබුණොත් නතර කරනවා

දෙවන පියවර : Queue එක Full වෙලා තිබුණේ නැත්නම් අපි Rear Point එක 1කින් වැඩි කරනවා. ඒ කියන්නේ Next Empty Space එකට.

තුන්වන පියවර : දැන් Rear Point එක තියෙන තැනට අපිට අවශ්‍ය Data එක Insert කරනවා.

Algorithm:

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

Implementation ( C )

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

Dequeue : 

Queue එකෙන් Data එළියට ගන්න Method එක. මේක කරන්නත් අපි උඩදි කතා කරා වගේ පියවර කිහිපයක් යන්න ඕන.

පළමු පියවර : Queue එක Empty ද කියලා Check කරන්න ඕන. මොකද අපිට Empty Queue එකකින් Data එකක් එළියට ගන්න බෑ.

දෙවන පියවර : Queue එක Empty වෙලා තිබුණොත් Underflow Error එකක් Display කරනවා. නැත්නම් Front Pointer එක ඊළඟ Element එකට Point කරනවා.

Algorithm:

procedure dequeue
   if queue is empty
      return underflow
   end if

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

Implementation ( C )

int dequeue() {

   if(isempty())
      return 0;

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

   return data;
}

දැන් අපි මේ එකින් එක බලපු Methods ටික එකතු කරලා සම්පූර්ණ Queue එකක Implementation එක බලමු.

Language : C

typedef void * queue_data_type;
struct queue_item {
	queue_data_type contents;
	struct queue_item* next;
};
struct queue_root {
	struct queue_item* head;
	struct queue_item* tail;
};

void init_queue(struct queue_root* queue){
	queue->head = queue->tail = NULL;
}

void push_queue(struct queue_root* queue, int size, queue_data_type contents){
	struct queue_item *item = malloc(sizeof(item));
	item->contents = contents;
	item->next = NULL;
	if (queue->head == NULL){
		queue->head = queue->tail = item;
	} else {
		queue->tail = queue->tail->next = item;
	}
}

queue_data_type pop_queue(struct queue_root* queue){
	queue_data_type popped;
	if (queue->head == NULL){
		return NULL; // causes a compile warning.  Just check for ==NULL when popping.
	} else {
		popped = queue->head->contents;
		struct queue_item* next = queue->head->next;
		free(queue->head);
		queue->head = next;
		if (queue->head == NULL)
			queue->tail = NULL;
	}
	return popped;
}

void process_queue(struct queue_root* queue, void (*func)(queue_data_type)){
	if (queue == NULL)
		return;
	struct queue_item* current = queue->head;
	while (current != NULL){
		next = current->next
		func(current->contents);
		current = next;
	}
}

හරි එහෙනම් මොනවා හරි ප්‍රශ්ණයක් තිබුණොත් Comment එකක් දාන්න.