Data Structure : Queue
Queue Operation with algorithm
ডাটা স্ট্রাকচারে কিউয়ের(Queue) মূল অপারেশনগুলি নিম্নরূপ:
1. ENQUEUE – কিউয়ের(queue) শেষে একটি উপাদান যোগ করে। এটি রিয়ার পয়েন্টার (REAR pointer) ব্যবহার করে করা হয়।
2. DEQUEUE – কিউয়ের(queue) সামনে থেকে একটি উপাদান সরায়। যে উপাদানটি সরানো হয় তাকে ফ্রন্ট পয়েন্টার(FRONT pointer) দ্বারা পয়েন্ট করা থাকে।
3. isEmpty – কিউ(queue) খালি(empty) কিনা তা পরীক্ষা করে। যদি কিউয়ের সাইজ 0 হয় তাহলে ট্রু(TRUE) রিটার্ন করে।
4. is Full – কিউ পূর্ণ কিনা তা পরীক্ষা করে। যদি কিউয়ের সাইজ ম্যাক্স সাইজের সমান হয় তাহলে ট্রু(TRUE) রিটার্ন করে।
কিউয়ের(queue) কিছু গুরুত্বপূর্ণ বৈশিষ্ট্য:
- FIFO (First In First Out) অর্ডার অনুসরণ করে – যে উপাদানটি প্রথমে যোগ করা হয়েছে সেটি প্রথমেই সরানো হয়।
- ইনকিউ এবং ডিকিউ হল প্রাথমিক অপারেশন।
- ইনকিউ পিছনের(REAR) দিকে এবং ডিকিউ ফ্রন্ট(FRONT) দিকে করা হয়।
- অপেক্ষার তালিকা, বাফার ইত্যাদি তৈরিতে ব্যবহৃত হয়।
- অ্যাপ্লিকেশনগুলির মধ্যে CPU scheduling, Disk scheduling, Directories, Print spoolers ইত্যাদি অন্তর্ভুক্ত।
সংক্ষেপে, কিউ হল একটি লিনিয়ার ডাটা স্ট্রাকচার যেটি এক দিক থেকে যোগ করার এবং অন্য দিক থেকে সিকুয়েন্সিয়াল FIFO ম্যানারে সরানোর সুবিধা দেয়। এই দুই অপারেশন দুই ভাবে ইমপ্লিমেন্ট করা সম্ভব 1) Array 2) Link List
Queue এর enqueue এবং dequeue অপারেশনটির algorithm:
// Algorithm:
enqueue/insert element to the queue
procedure enqueue(data)
if queue is full
return overflow
endif
rear ← rear + 1
queue[rear] ← data
return true
end procedure
dequeue/delete element from the queue
procedure dequeue
if queue is empty
return underflow
end if
data = queue[front]
front ← front + 1
return true
end procedureArray: enqueue এবং dequeue অপারেশন এর Source code টি উল্লেখ করা হল –
//Queue Implementation Using Array
#include <stdio.h>
#include <stdlib.h>
#define MAX 50
void enqueue();
void dequeue();
void display();
int queue_array[MAX];
int rear = -1;
int front = -1;
int main()
{
int choice;
while (1)
{
printf("\n1.Enqueue/Insert element to queue \n");
printf("\n2.Dequeue/Delete element from queue \n");
printf("\n3.Display all elements of queue \n");
printf("\n4.Quit \n");
printf("\nEnter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Wrong choice \n");
}
}
}
void enqueue()
{
int data;
if (rear == MAX - 1)
printf("Queue Overflow \n");
else
{
if (front == -1)
front = 0;
printf("Inset the element in queue : ");
scanf("%d", &data);
rear = rear + 1;
queue_array[rear] = data;
}
}
void dequeue()
{
if (front == -1 || front > rear)
{
printf("Queue Underflow \n");
return;
}
else
{
printf("Element dequeue from queue is : %d\n", queue_array[front]);
front = front + 1;
}
}
void display()
{
int i;
if (front == -1)
printf("Queue is empty \n");
else
{
printf("Queue is : \n");
for (i = front; i <= rear; i++)
printf("%d ", queue_array[i]);
printf("\n");
}
}Linked list: enqueue এবং dequeue অপারেশন এর Source code টি উল্লেখ করা হল –
//Queue implementation in C using Link List
#include<stdio.h>
#include<stdlib.h>
struct Queue //structure is declared
{
struct Queue *next; //self referensing structure
int item; //initailizing item in the structure
};
struct Queue *front; //a pointer front is declared in structure
struct Queue *rear; //a pointer rear is declared in structure
void addq(int); //addq function is declared
int delq(); //delq function id declared
void main()
{
int ch, item, val; //variables are declared
while(1)
{
printf("\nEnter 1 to add element in the Queue");
printf("\nEnter 2 to delete element from the Queue");
printf("\nEnter 3 to exit from program");
printf("\nEnter your choice::");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nEnter the item in the list::");
scanf("%d", &item);
addq(item);
break;
case 2: val=delq() ;
printf("\nThe deleted element is %d=",val);
break ;
case 3: exit(1);
default: printf("\nWrong Input") ;
}
}
}
void addq(int item)
{
struct Queue *temp; //a pointer temp is declared within the structure
temp=(struct Queue*)malloc(sizeof(struct Queue));
if(temp==NULL)
{
printf("\nQueue Overflowed");
return;
}
temp->item=item;//the value is entered in the List
temp->next=NULL;
if(rear==NULL)
{
front=temp;
rear=temp;
}
else
{
rear->next=temp;
rear=rear->next; //rear is incremented
}
}
int delq()
{
struct Queue *temp;
int item=0;
if(front==NULL) //checking unerflowed condition
{
printf("\nQueue Underflowed");
return 0;
}
item=front->item;
temp=front;
if(front==NULL) //checking whether front is null or not, if true
{
front=NULL; //front is assign with NULL
rear=NULL;
}
else
{
front=front->next;
free(temp);
}
return item;
}