কিউ (Queue) হল একটি লিনিয়ার ডেটা স্ট্রাকচার যেখানে অপারেশনের ক্রম FIFO (First In First Out)।
অ্যারে হল একটি ডেটা স্ট্রাকচার যাতে একই ডেটা টাইপের উপাদানগুলো কনটিনিউয়াস মেমরি লোকেশনে থাকে।
কিউ-তে ইনসারশন এবং ডিলিশন অপারেশন কিউর দুটি প্রান্তে হয়। ইমপ্লিমেন্টেশনটি স্ট্যাকের চেয়ে কিছুটা জটিল।
অ্যারে ব্যবহার করে কিউ ইমপ্লিমেন্টেশনে, আমরা সাইজ n-এর একটি queue অ্যারে তৈরি করি দুটি ভেরিয়েবল top এবং end সহ।
প্রাথমিকভাবে অ্যারেটি খালি থাকে অর্থাৎ top এবং end উভয় ০ ইনডেক্সে থাকে। এবং উপাদান যোগ হওয়ার সাথে সাথে (insertion) end ভেরিয়েবলের মান বাড়ে। end-এর মান n পর্যন্ত বাড়তে পারে অর্থাৎ অ্যারের ম্যাক্সিমাম দৈর্ঘ্য।
যখন কিউ থেকে উপাদান মুছে ফেলা হয় (deletion), top ভেরিয়েবলের মান বাড়ে। top-এর মান end-এর মান পর্যন্ত বাড়তে পারে।
কিউ অপারেশন ইমপ্লিমেন্টেশন
Enqueue − কিউতে উপাদান যোগ করার অপারেশন। উপাদান যোগ করার আগে চেক করব কিউ ফুল কিনা। শর্ত: end < n হলে queue[end]-এ ডেটা স্টোর করুন এবং end++ করুন। ওভারফ্লো কন্ডিশন: অ্যারে ফুল হলে অর্থাৎ end == n।
Dequeue − কিউ থেকে উপাদান ডিলিট করার অপারেশন। ডিলিট করার আগে চেক করব কিউ খালি কিনা। শর্ত: top == end হলে অ্যারে খালি। উপাদান থাকলে কিউ ডিকিউ করব: অ্যারের সকল উপাদান এক পজিশন বামে শিফট করব।
Front − কিউর প্রথম উপাদান বের করা অর্থাৎ array[top]। এই অপারেশন শুধু অ্যারে খালি না হলে সম্ভব।
Display − কিউর সকল উপাদান প্রদর্শন করা। অর্থাৎ কিউ ট্রাভার্স করা।
অ্যালগরিদম
ENQUEUE: Step 1: if (end == n), print: "OVERFLOW". Exit Step 2: queue[end] = data and end++ DEQUEUE: Step 1: If (top == end), print: "empty Queue". Exit Step 2: shift all elements one position left. end--;
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
struct Queue {
int top, end, n;
int* queue;
Queue(int c) {
top = end = 0;
n = c;
queue = new int[c];
}
~Queue() { delete[] queue; }
void Enqueue(int data) {
if (n == end) {
printf("\nQueue is full\n");
return;
} else {
queue[end] = data;
end++;
}
return;
}
void Dequeue() {
if (top == end) {
printf("\nQueue is empty\n");
return;
} else {
for (int i = 0; i < end - 1; i++) {
queue[i] = queue[i + 1];
}
end--;
}
return;
}
void Display() {
int i;
if (top == end) {
printf("\nQueue is Empty\n");
return;
}
for (i = top; i < end; i++) {
printf(" %d <-- ", queue[i]);
}
return;
}
void Front() {
if (top == end) {
printf("\nQueue is Empty\n");
return;
}
printf("\nFront Element is: %d", queue[top]);
return;
}
};
int main(void) {
Queue q(4);
q.Display();
q.Enqueue(12);
q.Enqueue(89);
q.Enqueue(65);
q.Enqueue(34);
q.Display();
q.Enqueue(92);
q.Display();
q.Dequeue();
q.Dequeue();
q.Display();
q.Front();
return 0;
}
আউটপুট
Queue is Empty 12 <-- 89 <-- 65 <-- 34 <-- Queue is full 12 <-- 89 <-- 65 <-- 34 <-- 65 <-- 34 <-- Front Element is: 65
