C++ STL-এ Deque বাস্তবায়ন: ডাবল-এন্ডেড কিউ

Deque (Double Ended Queue) একটি কিউ ডেটা স্ট্রাকচার যেখানে ইনসারশন এবং ডিলিশন উভয় প্রান্তে (front এবং rear) সম্ভব। ডেটা দু প্রান্তেই যোগ বা বাদ দেওয়া যায়। এটি ভেক্টরের মতো র‍্যান্ডম অ্যাক্সেস দেয় (O(1)) কিন্তু মেমরি ব্লক-wise অ্যালোকেট করে।

এলগরিদম

শুরু
  ডিক ভেক্টর এবং ইটারেটর ঘোষণা করুন
  ইউজারের পছন্দ অনুযায়ী ইনপুট নিন
  সুইচ অপারেশনে ফাংশন কল করুন:
    d.size()      = ডিকের আকার
    d.push_back() = পিছনে উপাদান যোগ
    d.push_front()= সামনে উপাদান যোগ
    d.pop_back()  = পিছন থেকে উপাদান বাদ
    d.pop_front() = সামনে থেকে উপাদান বাদ
    d.front()     = সামনের উপাদান
    d.back()      = পিছনের উপাদান
  ডিকের উপাদানগুলো প্রিন্ট করুন
শেষ

উদাহরণ কোড: ইন্টারেক্টিভ ডিক প্রোগ্রাম

#include <iostream>
#include <deque>
#include <string>
#include <cstdlib>
using namespace std;

int main() {
    deque<int> d;
    deque<int>::iterator it;
    int choice, item;

    while (true) {
        cout << "1. Size of the Deque" << endl;
        cout << "2. Insert Element at the End" << endl;
        cout << "3. Insert Element at the Front" << endl;
        cout << "4. Delete Element at the End" << endl;
        cout << "5. Delete Element at the Front" << endl;
        cout << "6. Front Element at Deque" << endl;
        cout << "7. Last Element at Deque" << endl;
        cout << "8. Display Deque" << endl;
        cout << "9. Exit" << endl;
        cout << "Enter your Choice: ";
        cin >> choice;

        switch (choice) {
            case 1:
                cout << "Size of the Deque: " << d.size() << endl;
                break;
            case 2:
                cout << "Enter value to be inserted at the end: ";
                cin >> item;
                d.push_back(item);
                break;
            case 3:
                cout << "Enter value to be inserted at the front: ";
                cin >> item;
                d.push_front(item);
                break;
            case 4:
                if (!d.empty()) {
                    item = d.back();
                    d.pop_back();
                    cout << "Element " << item << " deleted" << endl;
                } else cout << "Deque is empty" << endl;
                break;
            case 5:
                if (!d.empty()) {
                    item = d.front();
                    d.pop_front();
                    cout << "Element " << item << " deleted" << endl;
                } else cout << "Deque is empty" << endl;
                break;
            case 6:
                if (!d.empty()) cout << "Front Element: " << d.front() << endl;
                else cout << "Deque is empty" << endl;
                break;
            case 7:
                if (!d.empty()) cout << "Back Element: " << d.back() << endl;
                else cout << "Deque is empty" << endl;
                break;
            case 8:
                cout << "Elements of Deque: ";
                for (it = d.begin(); it != d.end(); ++it)
                    cout << *it << " ";
                cout << endl;
                break;
            case 9:
                exit(0);
            default:
                cout << "Wrong Choice" << endl;
        }
    }
    return 0;
}

নমুনা আউটপুট

1. Size of the Deque
2. Insert Element at the End
3. Insert Element at the Front
4. Delete Element at the End
5. Delete Element at the Front
6. Front Element at Deque
7. Last Element at Deque
8. Display Deque
9. Exit
Enter your Choice: 1
Size of the Deque: 0
...
Enter your Choice: 3
Enter value to be inserted at the front: 2
...
Enter your Choice: 6
Front Element of the Deque: 2
Enter your Choice: 7
Back Element of the Deque: 1
...
Enter your Choice: 8
Elements of Deque: 5 2 1 4
...
Enter your Choice: 9

ডিক vs ভেক্টর vs লিস্ট: ডিক দিয়ে উভয় প্রান্তে O(1) ইনসারশন/ডিলিশন এবং র‍্যান্ডম অ্যাক্সেস O(1) পাওয়া যায়। ভেক্টরে শুধু পিছনে O(1), লিস্টে যেকোনো পজিশনে O(1) কিন্তু র‍্যান্ডম অ্যাক্সেস O(n)।