১৪-৪ঃ Doubly Linked List এর সাহায্যে Queue তৈরি করা

গত মডিউলে আমরা জেনেছি কেনো Queue ইমপ্লিমেন্টেশনের জন্য Array হতে Doubly Linked List বেশি ইফিশিয়েন্ট। আজকে আমরা দেখবো কীভাবে Doubly Linked List এর সাহায্যে Queue implement করা যায়। যেহেতু Singly Linked List এর সকল অপারেশন Doubly Linked List এর সাহায্যে করা যায় , তাই এইক্ষেত্রে Queue এর Implementation টাও একই। প্রথমে দেখে নেয়া যাক Queue এর অপারেশন গুলার সাথে Singly Linked List এর কি কি মিল পাওয়া যায়

উপরের ছবিতে আমরা Queue এর প্রধান অপারেশন গুলা দেখেছি যার মধ্যে আছে 1. push() -> এই অপারেশনের মাধ্যমে আমরা Queue এর শেষে একটি ভ্যালু Insertion করতে পারি। যা Doubly Linked এর tail এ ভ্যালু Insert করার মতো. 2. front() -> এই অপারেশনের সাহায্যে আমরা Queue এর শুরুতে কোন ভ্যালু আছে তা জানতে পারি। এই অপারেশন টি Doubly Linked List এর প্রথম ভ্যালু অর্থাৎ Head এক্সেস করার মতো । 3. pop() -> এই অপারেশনের মাধ্যমে আমরা Queue তা বা লাইনে সবার শুরুতে যে ভ্যালু আছে তা Queue থেকে মুছে দিতে পারি। যা Douby Linked List এর Head ডিলিট করার অপারেশনের মতো। তাছাড়াও আরো কিছু ফাংশন আছে , যেমনঃ 4. size() -> এই অপারেশনের মাধ্যমে আমরা Queue তে কতটি ভ্যালু আছে তা জানতে পারি। Initially আমরা সাইজ টিকে ০ তে ইনিশিয়ালাইজ করতে পারি। এরপর Queue তে push অর্থাৎ Doubly Linked List এ কোনো ভ্যালু Insertion এর সময় সাইজ এর মান ১ বাড়িয়ে দিতে পারি এবং Queue তে pop অর্থাৎ Doubly Linked List এ কোনো ভ্যালু Delete করার ক্ষেত্রে সাইজ ১ কমিয়ে দিতে পারি 5. empty() -> এই ফাংশনের সাহায্যে আমরা দেখতে পারি Queue খালি কিনা। যেহেতু আমরা সাইজ ট্রেক রাখছি , তাই আমরা size চেক করে বলে দিতে পারি Queue খালি আছে কিনা। Queue খালি থাকলে তবে এই ফাংশনটি True রিটার্ন করবে , এবং খালি না থাকলে false রিটার্ন করবে। আসুন এইবার কোডে Implement করে দেখা যাকঃ Code:

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int val;
    Node *next;
    Node *prev;
    Node(int val)
    {
        this->val = val;
        this->next = NULL;
        this->prev = NULL;
    }
};// প্রথমে Doubly Linked List এর একটি Node class বানিয়ে নিলাম যাতে করে Doubly Linked List তৈরি করতে পারি 


class myQueue // এরপর একটি myQueue নামক ক্লাস বানিয়ে নিলাম যেখানে আমরা আমাদের তৈরি করা Queue এর স্ট্রাকচার ও বিভিন্ন ফাংশন তৈরি করে নিতে পারি 
{
public:
// Queue তৈরির জন্য একটি Doubly Linked List এর Head এবং Tail ইনিশিয়ালাইজ করে নিচ্ছি
    Node *head = NULL;
    Node *tail = NULL;
    int sz = 0; // Queue এর  সাইজ ট্রেক রাখার জন্য একটি size ভ্যারিয়েবল রাখছি। শুরুতে যেহেতু Queue টি খালি , তাই সাইজ ০ 


    void push(int val)// Queue তে ভ্যালু পুশ করার জন্য একটি ফাংশন তৈরি করে নিলাম যা ঐ     ভ্যালুটি রিসিভ করে Queue তে পুশ করে দিবে। 
    {
        sz++; // যেহেতু Queue তে একটি নতুন ভ্যালু push হচ্ছে তাই এর সাইজ ১ বাড়িয়ে দিচ্ছি
        
        // নিচে Doubly Linked List এর tail track রাখার মাধ্যমে O(1) এর শেষে একটি ভ্যালু Insertion করার কোড দেখানো হলো  
        Node *newNode = new Node(val);
        if (head == NULL)
        {
            head = newNode;
            tail = newNode;
            return;
        }
        tail->next = newNode;
        newNode->prev = tail;
        tail = tail->next;
    }
    void pop()// Queue এর শুরু থেকে অর্থাৎ লাইনে যে ভ্যালু সবার আগে আছে তা Queue থেকে রিমুভ করার জন্য একটি ফাংশন তৈরি করা হলো 
    {
        sz--; // যেহেতু একটি ভ্যালু Queue থেকে pop করা হচ্ছে তাই এর সাইজ এক কমিয়ে দেয়া হচ্ছে 
        
        // নিচে Doubly Linked List এর প্রথম ভ্যালু অর্থাৎ Head ডিলিট করার কোড দেয়া আছে যার কমপ্লেক্সিটি O(1) 
        Node *deleteNode = head;
        head = head->next;
        if (head == NULL)
        {
            tail = NULL;
            delete deleteNode;
            return;
        }
        head->prev = NULL;
        delete deleteNode;
    }
    int front()// Queue এর শুরুতে এখন কোন ভ্যালু আছে তা জানার জন্য এই ফাংশন ব্যবহার করা হয় 
    {
        return head->val;
    }
    int size() // Queue এর সাইজ বের করার ফাংশন
    {
        return sz; // সাইজ ট্রেকার ভ্যারিয়েবল টি রিটার্ন করা হচ্ছে 
    }
    bool empty() // Queue টি খালি কিনা চেক করা হচ্ছে 
    {
        if (sz == 0)  // যদি size ট্রেকার ০ হয় সে ক্ষেত্রে queue টি খালি 
            return true;
        else // অন্যথায় তা খালি নয় 
            return false;
    }
};

int main()
{
    myQueue q; // myQueue ক্লাসের একটি অব্জেক্ট তৈরি করা হলো 
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        q.push(x); // n টি মান queue তে পুশ করা হলো 
    }
    
    cout << q.size() << endl ; // returns n
    cout << q.empty() << endl ; // returns false 
    


    while (!q.empty())  // যতক্ষন queue খালি না
    {
        cout << q.front() << endl; // Queue এর প্রথম ভ্যালুটি এক্সেস করা হচ্ছে 
        q.pop(); // queue এর প্রথম ভ্যালুটি queue হতে remove করা হচ্ছে 
    }
    return 0;
}