27. Deque (Double-ended Queue)
Deque (যাকে ডেক হিসেবে উচ্চারণ করা হয়) হলো এমন একটি লিনিয়ার ডেটা স্ট্রাকচার যেখানে সামনে (Front) এবং পেছনে (Rear)—উভয় দিক থেকেই এলিমেন্ট যোগ বা বিয়োগ করা যায়। এটি স্ট্যাক এবং কিউ উভয়েরই বৈশিষ্ট্য বহন করে।
1. Deque কি? (Bidirectional Queue)
সাধারণ কিউ-তে শুধু এক দিক থেকে ঢোকা এবং অন্য দিক থেকে বের হওয়া যায়। কিন্তু ডেক-এ আপনি চাইলে শুরুতেও এলিমেন্ট যোগ করতে পারেন, আবার সামনে থেকেও রিমুভ করতে পারেন।
2. ডেক অপারেশনসমূহ (Deque Operations)
- insertFront(): কিউ-এর সামনে নতুন এলিমেন্ট যোগ করা।
- insertLast(): কিউ-এর পেছনে নতুন এলিমেন্ট যোগ করা (সাধারণ Enqueue)।
- deleteFront(): কিউ-এর সামনে থেকে এলিমেন্ট সরানো (সাধারণ Dequeue)।
- deleteLast(): কিউ-এর পেছন থেকে এলিমেন্ট সরানো।
- getFront(): প্রথম এলিমেন্ট দেখা।
- getRear(): শেষ এলিমেন্ট দেখা।
3. ডেক-এর প্রকারভেদ (Types of Deque)
কখনো কখনো ডেকের অপারেশন সীমিত করা হয়:
Input Restricted Deque
এখানে এক দিক থেকে ইনপুট নেওয়া যায় (শুধু Rear-এ), কিন্তু আউটপুট বা রিমুভ উভয় দিক থেকেই করা যায়।
Output Restricted Deque
এখানে উভয় দিক থেকে ইনপুট নেওয়া যায়, কিন্তু ডিলিট বা আউটপুট শুধু এক দিক (Front) থেকে করা যায়।
4. ইমপ্লিমেন্টেশন পদ্ধতি (Implementation)
সার্কুলার অ্যারে (Circular Array)
অ্যারেতে সামনে ইনসার্ট করার জন্য front = (front - 1 + size) % size লজিক ব্যবহার করা হয়।
ডাবলি লিঙ্কড লিস্ট (Doubly Linked List)
DLL ব্যবহার করলে ডেক ইমপ্লিমেন্ট করা সবচেয়ে সহজ, কারণ প্রতিটি নোডে আগের ও পরের নোডের রেফারেন্স থাকে।
5. ব্যবহারের ক্ষেত্র (Applications)
- Browser History: যেখানে আগের এবং পরের পেজে যাওয়ার সুবিধা থাকে।
- Undo-Redo Operations: সফটওয়্যারে মাল্টিপল আগের স্টেট সেভ করতে।
- Sliding Window Problems: স্লাইডিং উইন্ডোর মধ্যে ম্যাক্সিমাম বা মিনিমাম এলিমেন্ট ট্র্যাক করতে।
- A-Steal Job Scheduling Algorithm: মাল্টি-প্রসেসর সিস্টেমে কাজ ভাগ করে দেওয়ার জন্য।
6. ডেক প্রবলেমস (Deque Problems)
- Palindrome Checker: একটি স্ট্রিং ডেক-এ ইনপুট নিয়ে উভয় পাশ থেকে ক্যারেক্টার মিলিয়ে চেক করা যায় এটি প্যালিনড্রোম কি না।
- Sliding Window Maximum: $O(n)$ সময়ে এই প্রবলেম সলভ করার জন্য ডেক সবচেয়ে কার্যকর।
📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)
| Operation | Time Complexity |
|---|---|
| insertFront / insertLast | O(1) |
| deleteFront / deleteLast | O(1) |
| getFront / getRear | O(1) |
| Search | O(n) |
IMPORTANT
ডেক (Deque) স্ট্যাক বা কিউ যে কোনোটি হিসেবেই কাজ করতে পারে, তাই এটি একটি ভার্সাটাইল ডেটা স্ট্রাকচার।
TIP
যদি আপনার অ্যাপ্লিকেশনে উভয় দিক থেকে ডেটা ম্যানেজমেন্টের প্রয়োজন হয়, তবে স্ট্রিং বা লিস্টের বিকল্প হিসেবে Deque ব্যবহার করুন।