স্ট্যাক ও কিউপড়তে ৪ মিনিট লাগবে

ডেক (Deque)

এমন একটা সারিবদ্ধ লাইন যেখানে সামনে বা পেছনে — যেকোনো দিক দিয়েই ঢোকা বা বের হওয়া যায়

push_front: O(1)push_back: O(1)pop_front: O(1)pop_back: O(1)search: O(n)space: O(n)

ডেক (Deque, উচ্চারণটা 'ডেক') শব্দটার আসল রূপ হলো Double-Ended Queue (ডাবল-এন্ডেড কিউ)। এটা অনেকটা সাধারণ কিউয়ের (Queue বা সারির) মতোই, কিন্তু এর একটা সুপারপাওয়ার আছে: এর দুদিক দিয়েই (সামনে এবং পেছনে) অনায়াসে যেকোনো কিছু ঢোকানো বা বের করা যায়।

ধরুন একটা ট্রেনের বগি, যার সামনে এবং পেছনে দুই দিকেই দরজা আছে। যাত্রীরা সামনের দরজা দিয়েও উঠতে বা নামতে পারে, আবার পেছনের দরজা দিয়েও উঠতে বা নামতে পারে। ডেক ঠিক এভাবেই কাজ করে।

চারটা জাদুকরী অপারেশন — সবগুলোই চোখের পলকে (Instant)

push_front — একদম সামনে নতুন কিছু যোগ করা
push_back — একদম পেছনে নতুন কিছু যোগ করা
pop_front — সামনের দিক থেকে একটা সরিয়ে নেওয়া
pop_back — পেছনের দিক থেকে একটা সরিয়ে নেওয়া

এই চারটা কাজই O(1) স্পিডে বা সাথে সাথে হয়ে যায়। কারণ ডেক তার সামনে আর পেছন — দুটো জায়গাই পয়েন্টার দিয়ে ট্র‍্যাক করে রাখে, তাই মাঝখানের কাউকে সরাতে বা শিফট (shifting) করতে হয় না।

◈ Explore the deque

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

স্ট্যাক (Stack) আর কিউ (Queue) — এক প্যাকেজেই দুই স্বাদ

ডেককে চাইলে আপনি স্ট্যাক বা কিউ, যেকোনো রূপেই ব্যবহার করতে পারেন:

যদি শুধু push_back আর pop_back ব্যবহার করেন → তবে এটা একদম স্ট্যাক (LIFO)-এর মতো কাজ করবে।
যদি শুধু push_back আর pop_front ব্যবহার করেন → তবে এটা একদম সাধারণ কিউ (FIFO)-এর মতো কাজ করবে।

এই অদ্ভুত ফ্লেক্সিবিলিটির কারণেই ডেক প্রোগ্রামিংয়ের দুনিয়ায় এত কাজের।

স্লাইডিং উইন্ডো ম্যাক্সিমাম (Sliding Window Maximum)

ডেকের সবচেয়ে ফেমাস আর ক্লাসিক ব্যবহার হলো স্লাইডিং উইন্ডো ম্যাক্সিমাম প্রবলেম সলভ করা। যখন একটা নির্দিষ্ট সাইজের উইন্ডো বা ফ্রেম কোনো অ্যারের ওপর দিয়ে স্ক্যানারের মতো ধীরে ধীরে আগাতে থাকে, এবং আপনাকে বলা হয় ওই ফ্রেমের ভেতরের সবচেয়ে বড় সংখ্যাটা খুঁজে বের করতে — তখন ডেক জাদুর মতো কাজ করে। সে পেছনের দিক দিয়ে নতুন সংখ্যা ঢোকায় আর সামনের দিক থেকে পুরোনো বা দরকার নেই এমন সংখ্যাগুলোকে ঘাড় ধাক্কা দিয়ে বের করে দেয়। ফলে O(n×k) সময়ের বদলে পুরো কাজটা মাত্র O(n) সময়েই শেষ হয়ে যায়।

প্যালিনড্রোম (Palindrome) চেক করা

প্যালিনড্রোম (যে শব্দ উল্টে দিলেও একই থাকে, যেমন 'MADAM' বা 'RACECAR') চেক করার জন্যও ডেক দারুণ কাজের। শব্দের সব অক্ষরগুলো ডেকের ভেতর ঢুকিয়ে দিন। এরপর push এবং pop ফাংশন কাজে লাগিয়ে একসাথে সামনে এবং পেছনের একটা করে অক্ষর বের করে মেলাতে থাকুন। যদি প্রতিবারই অক্ষরগুলো মিলে যায়, তার মানে শব্দটা নির্ঘাৎ একটা প্যালিনড্রোম!

দ্রষ্টব্য: ডেক হলো ডেটা স্ট্রাকচারের দুনিয়ার সুইস আর্মি নাইফ (Swiss Army knife)-এর মতো — একটা সিম্পল স্ট্রাকচার দিয়ে আপনি খুব নিখুঁত ও ফাস্ট স্পিডে স্ট্যাক এবং কিউয়ের যাবতীয় কাজ সেরে ফেলতে পারবেন।