C++ প্রোগ্রাম: ডিকিউ (Dequeue) ইমপ্লিমেন্টেশন

ডিকিউ বা ডাবল এন্ডেড কিউ হলো কিউ ডেটা স্ট্রাকচার사의 জেনারালাইজড ভার্সন যা দুটি এন্ডে ইনসার্ট এবং ডিলিট করার সুবিধা দেয়।

ডিকিউর কিছু বেসিক অপারেশন -

insert_at_beg(): ডিকিউর ফ্রন্টে আইটেম ইনসার্ট করে।

insert_at_end(): ডিকিউর রিয়ারে আইটেম ইনসার্ট করে।

delete_fr_beg(): ডিকিউর ফ্রন্ট থেকে আইটেম ডিলিট করে।

delete_fr_rear(): ডিকিউর রিয়ার থেকে আইটেম ডিলিট করে।

নিচে ডিকিউ ইমপ্লিমেন্ট করার C++ প্রোগ্রাম দেওয়া হলো

অ্যালগরিদম

শুরু
    dequeue ক্লাস ডিক্লেয়ার করো ফ্রন্ট f এবং রিয়ার r এবং নিচের ফাংশনগুলোসহ:
    insert_at_beg(int) ফাংশন - ফ্রন্টে আইটেম ইনসার্ট করতে:
        যদি কিউ পুরোপুরি না ভরে থাকে, ফ্রন্টে এলিমেন্ট ইনসার্ট করো এবং ফ্রন্ট ও রিয়ার আপডেট করো
        অন্যথায় ওভারফ্লো প্রিন্ট করো।
    insert_at_end(int) ফাংশন - রিয়ারে আইটেম ইনসার্ট করতে:
        যদি কিউ পুরোপুরি না ভরে থাকে, রিয়ারে এলিমেন্ট ইনসার্ট করো এবং ফ্রন্ট ও রিয়ার আপডেট করো
        অন্যথায় ওভারফ্লো প্রিন্ট করো।
    delete_fr_front() ফাংশন - ফ্রন্ট থেকে আইটেম ডিলিট করতে:
        যদি কিউ খালি থাকে, অন্ডারফ্লো প্রিন্ট করো অন্যথায় ফ্রন্ট এলিমেন্ট ডিলিট করো এবং ফ্রন্ট আপডেট করো।
    delete_fr_rear() ফাংশন - রিয়ার থেকে আইটেম ডিলিট করতে:
        যদি কিউ খালি থাকে, অন্ডারফ্লো প্রিন্ট করো অন্যথায় রিয়ার এলিমেন্ট ডিলিট করো এবং রিয়ার আপডেট করো।
শেষ

উদাহরণ কোড

#include <iostream> 
using namespace std; 
#define SIZE 10 
class dequeue { 
    int a[20], f, r; 
public: 
    dequeue(); 
    void insert_at_beg(int); 
    void insert_at_end(int); 
    void delete_fr_front(); 
    void delete_fr_rear(); 
    void show(); 
}; 
dequeue::dequeue() { 
    f = -1; 
    r = -1; 
} 
void dequeue::insert_at_end(int i) { 
    if (r >= SIZE - 1) { 
        cout << "\n insertion is not possible, overflow!!!!"; 
    } else { 
        if (f == -1) { 
            f++; 
            r++; 
        } else { 
            r = r + 1; 
        } 
        a[r] = i; 
        cout << "\nInserted item is " << a[r]; 
    } 
} 
void dequeue::insert_at_beg(int i) { 
    if (f == -1) { 
        f = 0; 
        a[++r] = i; 
        cout << "\n inserted element is: " << i; 
    } else if (f != 0) { 
        a[--f] = i; 
        cout << "\n inserted element is: " << i; 
    } else { 
        cout << "\n insertion is not possible, overflow!!!"; 
    } 
} 
void dequeue::delete_fr_front() { 
    if (f == -1) { 
        cout << "deletion is not possible::dequeue is empty"; 
        return; 
    } else { 
        cout << "the deleted element is: " << a[f]; 
        if (f == r) { 
            f = r = -1; 
            return; 
        } else 
            f = f + 1; 
    } 
} 
void dequeue::delete_fr_rear() { 
    if (f == -1) { 
        cout << "deletion is not possible::dequeue is empty"; 
        return; 
    } else { 
        cout << "the deleted element is: " << a[r]; 
        if (f == r) { 
            f = r = -1; 
        } else 
            r = r - 1; 
    } 
} 
void dequeue::show() { 
    if (f == -1) { 
        cout << "Dequeue is empty"; 
    } else { 
        for (int i = f; i <= r; i++) { 
            cout << a[i] << " "; 
        } 
    } 
} 
int main() { 
    int c, i; 
    dequeue d; 
    do { // সুইচ অপারেশন
        cout << "\n 1.insert at beginning"; 
        cout << "\n 2.insert at end"; 
        cout << "\n 3.show"; 
        cout << "\n 4.deletion from front"; 
        cout << "\n 5.deletion from rear"; 
        cout << "\n 6.exit"; 
        cout << "\n enter your choice: "; 
        cin >> c; 
        switch (c) { 
            case 1: 
                cout << "enter the element to be inserted"; 
                cin >> i; 
                d.insert_at_beg(i); 
                break; 
            case 2: 
                cout << "enter the element to be inserted"; 
                cin >> i; 
                d.insert_at_end(i); 
                break; 
            case 3: 
                d.show(); 
                break; 
            case 4: 
                d.delete_fr_front(); 
                break; 
            case 5: 
                d.delete_fr_rear(); 
                break; 
            case 6: 
                exit(1); 
                break; 
            default: 
                cout << "invalid choice"; 
                break; 
        } 
    } while (c != 7); 
}

আউটপুট

1.insert at beginning
2.insert at end
3.show
4.deletion from front
5.deletion from rear
6.exit
enter your choice: 4
deletion is not possible::dequeue is empty
...
(মেনু চালু থাকে)
...
enter your choice: 6