Data Structures (ডেটা স্ট্রাকচার)

ডেটা স্ট্রাকচার (Data Structure): মেমরিতে বিপুল পরিমাণ ডেটা এমনভাবে সুবিন্যস্ত রাখা যাতে বিভিন্ন গাণিতিক ও যৌক্তিক অপারেশন (যেমন সন্ধান, সংযোজন, অপসারণ) সর্বনিম্ন সময়ে ও মেমরিতে সম্পন্ন করা যায়। Abstract Data Type (ADT) হলো ডেটার এমন এক গাণিতিক রূপরেখা যা ডেটার ওপর কী কী অপারেশন করা যাবে তা নির্দিষ্ট করে, কিন্তু মেমরিতে কীভাবে তা বাস্তবায়িত হবে তা অভ্যন্তরীণভাবে গোপন রাখে।

ডেটা স্ট্রাকচারের শ্রেণিবিন্যাস প্রধানত দুটি ভাগে বিভক্ত:

• প্রিমিটিভ বনাম নন-প্রিমিটিভ: প্রিমিটিভ ডেটা টাইপ (যেমন int, float, char) সরাসরি প্রসেসরের নির্দেশ দ্বারা পরিচালিত হয়। নন-প্রিমিটিভ ডেটা স্ট্রাকচার প্রিমিটিভ উপাদানগুলোর সমন্বয়ে গঠিত জটিল রূপ (যেমন অ্যারে, স্ট্যাক, কিউ, লিঙ্কড লিস্ট)।
• লিনিয়ার বনাম নন-লিনিয়ার: লিনিয়ার ডেটা স্ট্রাকচারে উপাদানগুলো ক্রমানুসারে একটির পর একটি অবস্থান করে, যেখানে প্রথম ও শেষ উপাদান ব্যতীত প্রতিটির একটি পূর্বসূরী (predecessor) ও উত্তরসূরী (successor) থাকে। নন-লিনিয়ার ডেটা স্ট্রাকচারে উপাদানগুলো বহু-স্তরে বা জালিকার আকারে বিন্যস্ত থাকে (যেমন ট্রি ও গ্রাফ)।
• স্ট্যাটিক বনাম ডায়নামিক: স্ট্যাটিক কাঠামোতে কম্পাইল টাইমে নির্দিষ্ট আকারের মেমরি বরাদ্দ হয় (যেমন ফিক্সড অ্যারে); ডায়নামিক কাঠামোতে প্রোগ্রাম চলার সময় প্রয়োজন অনুযায়ী হিপ মেমরি বরাদ্দ ও মুক্ত করা হয় (যেমন লিঙ্কড লিস্ট)।

যেকোনো পূর্ণাঙ্গ ডেটা স্ট্রাকচারে প্রধানত ছয়টি মৌলিক অপারেশন সম্পন্ন করা যায়:

• ট্রাভার্সাল (Traversal): কাঠামোর প্রতিটি উপাদানকে নির্দিষ্ট ক্রমে অন্তত একবার পরিদর্শন ও প্রসেস করা।
• ইনসার্শন (Insertion): কাঠামোর নির্দিষ্ট অবস্থানে নতুন উপাদান যুক্ত করা।
• ডিলিশন (Deletion): কাঠামো থেকে নির্দিষ্ট উপাদান অপসারণ করে মেমরি মুক্ত করা।
• সার্চিং (Searching): নির্দিষ্ট কি-এর (Key) মান মেমরিতে আছে কি না এবং তার অবস্থান খুঁজে বের করা।
• সর্টিং (Sorting): উপাদানগুলোকে মানের ঊর্ধ্বক্রম বা নিম্নক্রমে সুবিন্যস্ত করা।
• মার্জিং (Merging): দুটি পৃথক সুবিন্যস্ত কাঠামোর উপাদানগুলোকে একটি একক সুবিন্যস্ত কাঠামোতে একত্রিত করা।

অ্যারে (Array): একই জাতীয় ডেটা উপাদানের ধারাবাহিক সংকলন যা মেমরিতে পরস্পর সংলগ্ন স্থানে সংরক্ষিত থাকে। বেস অ্যাড্রেস এবং উপাদানের আকার জানা থাকলে যেকোনো উপাদানের মেমরি অবস্থান $O(1)$ সময়ে সরাসরি নির্ণয় করা যায়:

• 1D অ্যারে অ্যাড্রেস সূত্র: বেস অ্যাড্রেস $B$, উপাদানের বাইট সাইজ $W$, এবং লোয়ার বাউন্ড $LB$ হলে: $$\text{Address}(A[k]) = B + W \times (k - LB)$$
• 2D অ্যারে রো-মেজর অর্ডার (RMO): উপাদানের সংরক্ষণ সারি অনুসারে ক্রমান্বয়ে হয়। $R \times C$ আকারের অ্যারেতে: $$\text{Address}(A[i][j]) = B + W \times [C \times (i - LBR) + (j - LBC)]$$
• 2D অ্যারে কলাম-মেজর অর্ডার (CMO): উপাদানের সংরক্ষণ কলাম অনুসারে ক্রমান্বয়ে হয়: $$\text{Address}(A[i][j]) = B + W \times [(i - LBR) + R \times (j - LBC)]$$

মেমরিতে নির্দিষ্ট উপাদানের অবস্থান নির্ণয়ের দুটি প্রধান পদ্ধতি নিচে তুলে ধরা হলো:

# পাইথনে নির্ভুল বাইনারি সার্চ অ্যালগরিদম
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        # ওভারফ্লো প্রতিরোধী মধ্যবিন্দু গণনা:
        mid = low + (high - low) // 2
        
        if arr[mid] == target:
            return mid  # উপাদানটি mid ইনডেক্সে পাওয়া গেছে
        elif arr[mid] < target:
            low = mid + 1  # ডান অর্ধে অনুসন্ধান
        else:
            high = mid - 1  # বাম অর্ধে অনুসন্ধান
            
    return -1  # উপাদানটি অ্যারেতে অনুপস্থিত

স্ট্যাক (Stack): একটি সীমাবদ্ধ লিনিয়ার ডেটা স্ট্রাকচার যা কঠোরভাবে Last-In, First-Out (LIFO) নীতি অনুসরণ করে। এতে উপাদান প্রবেশ করানো (Push) এবং অপসারণ করা (Pop) উভয়ই কেবল একটি নির্দিষ্ট শীর্ষবিন্দু বা Top of Stack (TOS)-এ ঘটে।

• টপ পয়েন্টার (top): স্ট্যাকের শীর্ষ উপাদানের ইনডেক্স নির্দেশ করে। ফাঁকা স্ট্যাকে top = -1।
• স্ট্যাক ওভারফ্লো (Stack Overflow): স্ট্যাকটি সম্পূর্ণ পূর্ণ থাকা অবস্থায় (top == MAX - 1) পুনরায় push করার চেষ্টা করলে ওভারফ্লো ঘটে।
• স্ট্যাক আন্ডারফ্লো (Stack Underflow): ফাঁকা স্ট্যাক থেকে (top == -1) কোনো উপাদান pop বা peek করার চেষ্টা করলে আন্ডারফ্লো ঘটে।

# পাইথনে অবজেক্ট-ওরিয়েন্টেড স্ট্যাক রূপায়ন
class Stack:
    def init(self, capacity=10):
        self.stack = []
        self.capacity = capacity
        
    def is_empty(self):
        return len(self.stack) == 0
        
    def is_full(self):
        return len(self.stack) >= self.capacity
        
    def push(self, val):
        if self.is_full():
            raise OverflowError("Stack Overflow: স্ট্যাক সম্পূর্ণ পূর্ণ!")
        self.stack.append(val)
        
    def pop(self):
        if self.is_empty():
            raise IndexError("Stack Underflow: স্ট্যাক ফাঁকা!")
        return self.stack.pop()
        
    def peek(self):
        if self.is_empty():
            return None
        return self.stack[-1]

গাণিতিক সমীকরণ লেখার তিনটি প্রধান রূপ রয়েছে:

• ইনফিক্স নোটেশন: অপারেটর দুটি অপারেন্ডের মাঝে থাকে (যেমন A + B * C)। মানুষের জন্য সহজ হলেও কম্পিউটারে বন্ধনী ও অগ্রাধিকারের নিয়ম মেনে চলতে হয়।
• প্রিফিক্স নোটেশন (পলিশ): অপারেটর অপারেন্ডের পূর্বে থাকে (যেমন + A * B C)। কোনো বন্ধনীর প্রয়োজন হয় না।
• পোস্টফিক্স নোটেশন (রিভার্স পলিশ - RPN): অপারেটর অপারেন্ডের ঠিক পরে থাকে (যেমন A B C * +)। কম্পিউটার ও কম্পাইলার স্ট্যাকের মাধ্যমে অত্যন্ত দ্রুত এটি হিসাব করতে পারে।

কিউ (Queue): একটি লিনিয়ার ডেটা স্ট্রাকচার যা কঠোরভাবে First-In, First-Out (FIFO) নীতি মেনে চলে। এতে দুটি স্বাধীন প্রান্তিক পয়েন্টার কাজ করে:

• ফ্রন্ট পয়েন্টার (front): যে প্রান্ত থেকে উপাদান মুছে ফেলা হয় (dequeue)।
• রিয়ার পয়েন্টার (rear): যে প্রান্তে নতুন উপাদান যুক্ত করা হয় (enqueue)।
• লিনিয়ার কিউ-এর ফলস ওভারফ্লো (False Overflow): ক্রমান্বয়ে উপাদান প্রবেশ ও অপসারণের ফলে rear অ্যারের শেষ প্রান্তে পৌঁছে যায় (rear == MAX - 1)। তখন front-এর পূর্বে মেমরি খালি থাকলেও নতুন উপাদান প্রবেশ করানো যায় না এবং কিউ ওভারফ্লো দেখায়।

বৃত্তাকার কিউ (Circular Queue) ফলস ওভারফ্লো দূর করতে অ্যারের শেষ প্রান্তকে মডিউলো গাণিতিক নিয়মে প্রথম প্রান্তের সাথে যুক্ত করে:

• চক্রাকার অগ্রগতি: rear = (rear + 1) % MAX এবং front = (front + 1) % MAX।
• সম্পূর্ণ পূর্ণ শর্ত: (rear + 1) % MAX == front।
• সম্পূর্ণ ফাঁকা শর্ত: front == -1।

অ্যারের স্থির আকার এবং উপাদান স্থানান্তর জনিত $O(n)$ অপচয় রোধ করতে লিঙ্কড লিস্ট (Linked List) ব্যবহৃত হয়। এতে হিপ মেমরিতে পৃথক নোড (Node) তৈরি করে পয়েন্টারের সাহায্যে সংযুক্ত করা হয়। প্রতিটি নোডে দুটি প্রধান অংশ থাকে:

• ডেটা ফিল্ড (Data): মূল মান বা তথ্য সংরক্ষণ করে।
• লিঙ্ক বা নেক্সট ফিল্ড (Next): পরবর্তী নোডের মেমরি অ্যাড্রেস ধারণ করে। শেষ নোডের নেক্সট মান None (বা NULL) হয়।
• হেড পয়েন্টার (Head): তালিকার প্রথম নোডকে নির্দেশ করে। তালিকা খালি থাকলে head is None।

লিঙ্কড লিস্টের তিনটি প্রধান রূপ রয়েছে:

• একক লিঙ্কড লিস্ট (SLL): কেবল একমুখী পথ। শুরুতে নতুন নোড যুক্ত করার সময় কোনো উপাদান না সরিয়ে সরাসরি $O(1)$ সময়ে করা যায়।
• দ্বৈত লিঙ্কড লিস্ট (DLL): প্রতিটি নোডে দুটি পয়েন্টার থাকে (prev ও next)। উভয় দিকেই ট্রাভার্সাল সম্ভব।
• বৃত্তাকার লিঙ্কড লিস্ট (CLL): শেষ নোডের নেক্সট পয়েন্টার None না হয়ে পুনরায় head-কে নির্দেশ করে।

ট্রি (Tree): একটি নন-লিনিয়ার হায়ারারকিক্যাল ডেটা স্ট্রাকচার যা একগুচ্ছ নোড এবং সংযোগকারী এজ (Edge) দ্বারা গঠিত। এতে একটি নির্দিষ্ট রুট নোড (Root Node) থাকে এবং বাকি নোডগুলো উপ-বৃক্ষে বিভক্ত থাকে।

• ডিগ্রি (Degree): একটি নোডের মোট প্রত্যক্ষ চাইল্ড নোডের সংখ্যা।
• লিফ নোড (Leaf Node): যে নোডের ডিগ্রি শূন্য অর্থাৎ কোনো সন্তান বা চাইল্ড নেই।
• উচ্চতা (Height): রুট থেকে যেকোনো লিফ পর্যন্ত দীর্ঘতম পথের মোট এজের সংখ্যা। $h$ উচ্চতার একটি বাইনারি ট্রির সর্বাধিক নোড সংখ্যা $N_{\max} = 2^{h+1} - 1$।
• বাইনারি ট্রি (Binary Tree): এমন ট্রি যেখানে প্রতিটি নোডের সর্বাধিক দুটি চাইল্ড থাকতে পারে (বাম চাইল্ড ও ডান চাইল্ড)।

বাইনারি সার্চ ট্রি (BST): একটি বিশেষায়িত বাইনারি ট্রি যা কঠোরভাবে নিচের নিয়ম মেনে চলে: