কিউ ডেটা স্ট্রাকচার – Queue Data Structure

Post updated on 17th July, 2017 at 10:47 am

বল্টু নানান জায়গায় খাওয়া-দাওয়া করে বেড়ায় সেটা ডেটা স্ট্রাকচার সিরিজের স্ট্যাকের পোস্ট থেকে ইতমধ্যে তোমরা জেনে গেছ। বল্টু সিএসইতে পড়ে। তো সেদিন সে ব্যাংকে গেল সেমিস্টার ফী জমা দিতে। আগে ভার্সিটির পেমেন্ট নেয়ার জন্য ব্যাংকে একটা নির্দিষ্ট কাউন্টার থাকত।  তো গতদিন গিয়ে দেখলাম কলেজের জন্য নির্দিষ্ট কোন কাউন্টার নাই। গেট দিয়ে ঢুকেই একটা টোকেন প্রিন্ট করার মেশিন দেখা গেল। টাচ স্ক্রিনে টোকেন প্রিন্ট করার বাটনে ক্লিক করলে ফ্যাঁচ ফ্যাঁচ শব্দ করে একটা টোকেন প্রিন্ট হয়ে বের হয়।

তাতে একটা সিরিয়াল নাম্বার লেখা। বল্টুর সিরিয়াল পাওয়া গেল 420! 😛

বল্টু চিন্তায় পড়ে গেল। দেখতে পেল ব্যাংকের ৫ টা কাউন্টারের মাথার উপরে LED screen এ কয়েকটা নাম্বার জ্বলছে। একটায় ৪০২, আরেকটায় ৪০৫ এরকম বাকিগুলোতে কয়েকটা সিরিয়াল নাম্বার। এটা দিয়ে বুঝাচ্ছে ঐ কাউন্টার ঐ সিরিয়াল নাম্বারের কাস্টমারকে সার্ভিস দিচ্ছে। বল্টু ঠিক বুঝতে পারছিল না এই কাউন্টারগুলো থেকে সিরিয়াল মেইনটেইন করে কিভাবে একজনের পর একজন ডাকা হয়। কাউন্টারের লোকটা কি নিজেই এই সিরিয়াল নাম্বার সিলেক্ট করে কাউকে ডাকে? নাকি অটোমেটেড?

এসব আকাশ-বাতাস ভাবতে ভাবতে সে গাল চুলকাচ্ছে। তখন পাশ থেকে একজনকে ফোনে বলতে শুনলো “আমার আসতে দেরি হবে। কিউতে (Queue মানে লাইন) অনেক মানুষ!” এটা শুনে বল্টুর মাথায় বিদ্যুৎ খেলে গেল! আরে! ভার্সিটির ছোট বেলায় ডেটা স্ট্রাকচারের একটা টপিক ছিল Queue! একটা কিউ এর মধ্যে কাস্টমারদের সিরিয়াল নাম্বারগুলো রাখলেই তো অটোমেটিক্যাল্যি সব কাউন্টার থেকে একজনের পর একজনকে ডাকা যায়! বল্টুও যেহেতু কিউ বুঝে তাই তুমিও বুঝতে পারবা। এইটা রকেট সায়েন্স না! চলো সামনে আগাই…

মনে করো ব্যাংকের কাস্টমারদের সিরিয়াল নাম্বারগুলার একটা লিস্ট তোমার কাছে আছে। লিস্ট না বলে এটাকে queue বলি। কিউটা হচ্ছে ৪০১, ৪০২, ৪০৩, … ৪১৯। বল্টু ঢোকার পরে সিরিয়াল নাম্বার প্রিন্ট হল ৪২০। এই নাম্বারটা কিউয়ের কোথায় রাখবা? ৪০১ এর আগে নাকি ৪১৯ এর পরে? নিশ্চয়ই তুমি ৪১৯ এর পরে রাখবা। এটা হচ্ছে কিউ এর back side. তার কারণ কী? কারণ হচ্ছে, যখন সিরিয়াল্যি একজনের পর একজনকে সার্ভিস দেয়ার ব্যাপার থাকে তখন “আগে আসলে আগে পাবেন” ভিত্তিতে সার্ভিস দেয়া হয়। অর্থাৎ যে প্রথমে আসবে সে প্রথমে সার্ভিস নিয়ে চলে যাবে। ইংরেজিতে একে বলা হয় “First In First Out (FIFO)”. বল্টুর পর আরো কোন কাস্টমার আসলে queue-তে তাদের পজিশন হবে কিউ এর back এ, মানে বল্টুর পরে। এটা গেল লিস্টে ডেটা add করার কনসেপ্ট। কিউয়ের ব্যাকে যখন কোন ডেটা add করা হয় তখন তাকে অ্যাড না বলে বলা হয় enqueue (Stack এর push এর মত)। এটা কিউ ডেটা স্ট্রাকচারের একটা পরিভাষা।

ব্যাংকে পাঁচটা কাউন্টার আছে a, b, c, d, e. এদের মধ্য থেকে c কাউন্টার ফাঁকা হল। সে তখন কী করবে? আমাদের কিউতে যেই লোক একদম শুরুতে (front) আছে তাকে ডাকবে। একটা কিউয়ের একদম শুরুতে যেই ডেটা থাকে তাকে বলা হয় front. স্বাভাবিক ভাবেই শেষের জনকে বলা হয় back/rear. তো ফ্রন্ট থেকে কোন একজন কাস্টমারকে সার্ভিস দেয়ার জন্য ডাকলে এই ডাকার প্রসেসটাকে বলা হয় dequeue. কিউয়ের বৈশিষ্ট্য হচ্ছে dequeue করে front এর ডেটাকে প্রসেস করে তাকে কিউ থেকে বের করে দিবে (Stack এর pop এর মত)। b কাউন্টার খালি হলে সে আবার কিউয়ের front-কে ডাকবে (dequeue)। তাকে সার্ভিস দিয়ে বের করে দিবে। Queue এর দুইটা অপারেশন উল্লেখ করা যেতে পারে। Dequeue এর মধ্যে ফ্রন্ট ডেটাকে অ্যাক্সেস করা ও সেটাকে রিমুভ করা, উভয় অপারেশনই হ্যান্ডেল করা হচ্ছে। তুমি চাইলে কোডে ৩টা ফাংশন রাখতে পারো ৩ টা কাজের জন্য।

• Enqueue – কিউয়ের back এ কোন data অ্যাড করা
• Dequeue – কিউয়ের front এর data-কে প্রসেস করে কিউ থেকে বের করে দেয়া

Enqueue/Push Operation of Queue Data Structure

C++ এর STL ব্যবহার করে সহজেই কিউয়ের অপারেশনগুলো করা যায়। স্ট্যাকের মত কিউয়ের হেডার ফাইল অ্যাড করে কাজ করতে হবে।

#include<queue>
using namespace std;

int main(){

    queue<int> myQueue;

    myQueue.push(419);
    myQueue.push(420);

}

যদি সি ল্যাঙ্গুয়েজ ব্যবহার করে করতে চাই তাহলে এই কাজের জন্য একটা ফাংশন লিখে ফেলিঃ

#define queueSize 100

int myQueue[queueSize], front = 0, rear = -1, dataCounter = 0; //Global data

void enqueue(int value)
{
    if(rear==queueSize)
        printf("Queue is Full. Cannot push any data");
    else
    {
        myQueue[++rear] = value;
        dataCounter++;
    }
}

অ্যারে দিয়ে কিউ ইমপ্লিমেন্ট করার সময় দুইটা data pointer রাখা হয়। front ভেরিয়েবল দিয়ে কিউয়ের ফ্রন্ট ভ্যালুকে অ্যাক্সেস করা হয়। আর rear ভেরিয়েবল দিয়ে কিউয়ের back বা শেষের ভেরিয়েবলের পজিশন ম্যানেজ করা হয়। স্ট্যাকের ক্ষেত্রে দুইটা ভেরিয়েবল দরকার হয় নাই। কারণ একই পথে স্ট্যাকের ডেটা ঢুকতো ও বের হতো। তাই সেখানে শুধু top নামের একটা ভেরিয়েবল দিয়েই কাজ সেরে ফেলা গেছে। কিন্তু কিউয়ের পথ কিন্তু দুইটা। ডেটা insert হয় কিউয়ের ব্যাক সাইড দিয়ে, আর ডেটা প্রসেসিং/রিমুভ হয় সামনের দিক দিয়ে।

ফাংশনের ভিতরে প্রথমেই চেক করা হয়েছে rear বা শেষের ভ্যালুকে এক্সেস করার পয়েন্টারের মান কিউয়ের সাইজের সমান হয়ে গিয়েছে কিনা। যদি সমান হয়ে যায় তার মানে হচ্ছে কিউতে আর কোন জায়গা নাই। Overflow হয়ে গিয়েছে। কিন্তু যদি কিউতে ফাঁকা জায়গা থাকে তাহলে ++rear করে value-টা কিউতে ঢুকিয়ে দেয়া হচ্ছে। rear এর মান গ্লোবাল্যি -1 দেয়া হয়েছিল। অ্যারেতে -1 নামের কোন ইন্ডেক্স নাই, ইন্ডেক্স শুরু হয় ০ থেকে। তাই preincrement operator (++rear) ব্যবহার করা হয়েছে। একই সাথে dataCounter এর মানও ১ বাড়িয়ে দেয়া হয়েছে। এটা দিয়ে আমরা হিসাব রাখব এই কিউতে কতগুলো ডেটা আছে।

Dequeue/Pop Operation of Queue Data Structure

Dequeue এর কাজ আগেই বলা হয়ে গেছে। কিউয়ের front ডেটাকে প্রসেসিং/রিমুভ করার অপারেশন এটা। সি++ এর কোড হতে পারে এরকমঃ

if(myQueue.empty() != true)
{
    int frontValue = myQueue.front(); //return front value
    myQueue.pop(); //remove front value from Queue

}

উপরের কোডটা সি দিয়ে করা যায় এভাবেঃ

void dequeue()
{
    if(front==queueSize)
         printf("Queue is Empty!");
    else
    {
         printf("%d\n", myQueue[front++];
         dataCounter--;
    }

}

প্রথমে চেক করা হয়েছে কিউটা খালি কিনা। খালি হলে তো আর কোন ডেটাকে প্রসেস করা বা সেটাকে রিমুভ করা যাবে না। যদি খালি না হয়ে থাকে তাহলে mySqueue এর front-তম ইন্ডেক্সের মানটা প্রিন্ট করা হয়েছে। এরপর front এর মান বাড়িয়ে দেয়া হয়েছে। পরে আবারো dequeue() কল করা হলে অ্যারের পরের ইন্ডেক্সের মান প্রিন্ট করা হবে। অ্যারেতে ভ্যালু থেকেই যাচ্ছে, কিন্তু front ভেরিয়েবলের মাধ্যমে কিউয়ের শুরুর পয়েন্টটা আমরা কন্ট্রোল করছি। front++ করার মানেই আমরা ধরে নিচ্ছি ফ্রন্টের ভ্যালুটা কিউ থেকে বের করে দেয়া হয়েছে। আর যেহেতু একটা ডেটা কমে গেল তাই dataCounter এর মানও এক কমিয়ে দেয়া হয়েছে।

সি প্রোগ্রামিং ল্যাঙ্গুয়েজে লিখা পুরো কোডটা দেখা যাবে এখান থেকে।

কিউ ব্যবহার করে সলভ করতে পারোঃ UVa 11849