Data Structures (डेटा संरचनाएं)

डेटा संरचना (Data Structure): कंप्यूटर मेमोरी में डेटा तत्वों का एक विशेष तार्किक या गणितीय संगठन है जो डेटा पर विभिन्न संक्रियाओं (जैसे खोज, प्रविष्टि, विलोपन) को अत्यंत दक्ष बनाता है। Abstract Data Type (ADT) वह गणितीय मॉडल है जो यह परिभाषित करता है कि डेटा पर कौन से कार्य किए जा सकते हैं, बिना यह बताए कि मेमोरी में उनका कार्यान्वयन कैसे होगा।

डेटा संरचनाओं का वर्गीकरण निम्नलिखित आधारों पर किया जाता है:

• आदिम (Primitive) बनाम गैर-आदिम (Non-Primitive): प्रिमिटिव प्रकार (जैसे int, float, char) सीधे प्रोसेसर निर्देशों द्वारा संचालित होते हैं। गैर-प्रिमिटिव डेटा संरचनाएं प्रिमिटिव प्रकारों के संयोजन से निर्मित मिश्रित संरचनाएं हैं (जैसे ऐरे, स्टैक, क्यू, लिंक्ड लिस्ट)।
• रैखिक (Linear) बनाम गैर-रैखिक (Non-Linear): रैखिक संरचनाओं में तत्व एक क्रमिक अनुक्रम में व्यवस्थित होते हैं जहाँ प्रत्येक तत्व का एक निश्चित पूर्ववर्ती (predecessor) और उत्तरवर्ती (successor) होता है। गैर-रैखिक संरचनाओं में तत्व बहु-स्तरीय पदानुक्रम या नेटवर्क में जुड़े होते हैं (जैसे ट्री एवं ग्राफ)।
• स्थैतिक (Static) बनाम गतिशील (Dynamic): स्थैतिक संरचना में कंपाइल समय पर निश्चित आकार की मेमोरी आवंटित होती है (जैसे फिक्स्ड ऐरे); गतिशील संरचना में रन-टाइम के दौरान आवश्यकतानुसार हीप मेमोरी आवंटित व मुक्त की जाती है (जैसे लिंक्ड लिस्ट)।

किसी भी डेटा संरचना पर छह मूलभूत संक्रियाएं निष्पादित की जा सकती हैं:

• ट्रैवर्सल (Traversal): संरचना के प्रत्येक तत्व को क्रमबद्ध रूप से ठीक एक बार देखना और संसाधित करना।
• प्रविष्टि (Insertion): संरचना में एक नए डेटा तत्व को निर्दिष्ट स्थान पर जोड़ना।
• विलोपन (Deletion): संरचना से किसी अवांछित तत्व को हटाना तथा मेमोरी को मुक्त करना।
• खोज (Searching): किसी दी गई 'की' (Key) का स्थान या मेमोरी पता ज्ञात करना।
• सॉर्टिंग (Sorting): तत्वों को आरोही (Ascending) अथवा अवरोही (Descending) क्रम में व्यवस्थित करना।
• मर्जिंग (Merging): दो पृथक व्यवस्थित संरचनाओं के तत्वों को एक संयुक्त व्यवस्थित संरचना में मिलाना।

ऐरे (Array): सजातीय (समान प्रकार के) तत्वों का एक समूह जो मेमोरी में परस्पर क्रमागत स्थानों पर संग्रहीत होता है। आधार पते (Base Address) और तत्व के आकार की सहायता से किसी भी तत्व का भौतिक पता $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.items = []
        self.capacity = capacity
        
    def is_empty(self):
        return len(self.items) == 0
        
    def is_full(self):
        return len(self.items) >= self.capacity
        
    def push(self, val):
        if self.is_full():
            raise OverflowError("Stack Overflow: स्टैक पूर्णतः भरा है!")
        self.items.append(val)
        
    def pop(self):
        if self.is_empty():
            raise IndexError("Stack Underflow: स्टैक पूर्णतः रिक्त है!")
        return self.items.pop()
        
    def peek(self):
        if self.is_empty():
            return None
        return self.items[-1]

अंकगणितीय व्यंजकों को तीन मानक रूपों में लिखा जा सकता है:

• इनफिक्स संकेतन: ऑपरेटर दो ऑपरेंड्स के मध्य में स्थित होता है (जैसे A + B * C)। मानव पठन हेतु सरल किंतु कंप्यूटर में कोष्ठक और प्राथमिकता नियमों की आवश्यकता होती है।
• प्रिफिक्स संकेतन (पॉलिश): ऑपरेटर ऑपरेंड्स से पहले आता है (जैसे + A * B C)। यह कोष्ठक-मुक्त संकेतन है।
• पोस्टफिक्स संकेतन (रिवर्स पॉलिश - RPN): ऑपरेटर ऑपरेंड्स के ठीक बाद आता है (जैसे A B C * +)। स्टैक-आधारित मशीनों व कंपाइलरों द्वारा इसका मूल्यांकन अत्यंत तीव्र गति से होता है।

क्यू (Queue): एक रैखिक डेटा संरचना जो First-In, First-Out (FIFO) सिद्धांत पर कार्य करती है। इसमें दो स्वतंत्र छोर सूचक होते हैं:

• फ्रंट पॉइंटर (front): वह छोर जहाँ से तत्वों को हटाया (dequeue) जाता है।
• रियर पॉइंटर (rear): वह छोर जहाँ नए तत्वों को जोड़ा (enqueue) जाता है।
• रैखिक क्यू का फॉल्स ओवरफ्लो (False Overflow): क्रमिक विलोपन के कारण front आगे बढ़ता है और rear अंतिम सिरे (rear == MAX - 1) पर पहुँच जाता है। आगे खाली स्थान होने के बावजूद नया तत्व नहीं जोड़ा जा सकता और क्यू त्रुटिवश ओवरफ्लो दर्शाती है।

वृत्ताकार क्यू (Circular Queue): फॉल्स ओवरफ्लो को समाप्त करने हेतु यह अंतिम इंडेक्स को मॉड्यूलस अंकगणित द्वारा पुनः प्रारंभिक इंडेक्स से जोड़ती है:

• चक्रीय वृद्धि: rear = (rear + 1) % MAX एवं front = (front + 1) % MAX।
• पूर्णता की शर्त: (rear + 1) % MAX == front।
• रिक्तता की शर्त: front == -1।

ऐरे की निश्चित आकार सीमा और तत्वों के विस्थापन ($O(n)$ shifting) से बचने के लिए लिंक्ड लिस्ट (Linked List) का उपयोग होता है। इसमें हीप मेमोरी में स्वतंत्र नोड्स (Nodes) निर्मित होते हैं जिन्हें पॉइंटर्स द्वारा जोड़ा जाता है। प्रत्येक नोड में दो मुख्य भाग होते हैं:

• डेटा फील्ड (Data): वास्तविक मान या पेलोड संग्रहीत करता है।
• नेक्स्ट फील्ड (Next): अगले नोड का मेमोरी पता संग्रहीत करता है। अंतिम नोड का नेक्स्ट मान None (अथवा NULL) होता है।
• हेड पॉइंटर (Head): पहले नोड का संदर्भ रखता है। सूची रिक्त होने पर head is None होता है।

लिंक्ड लिस्ट के तीन प्रमुख रूप प्रचलित हैं:

• एकल लिंक्ড लिस्ट (SLL): एकदिशीय अग्रगामी नेविगेशन। शीर्ष पर प्रविष्टि मात्र पॉइंटर बदलकर $O(1)$ समय में हो जाती है।
• द्वैत लिंक्ड लिस्ट (DLL): प्रत्येक नोड में दो पॉइंटर्स (prev एवं next) होते हैं। यह द्विदिशीय नेविगेशन प्रदान करता है।
• वृत्ताकार लिंक्ड लिस्ट (CLL): अंतिम नोड None के स्थान पर पुनः head नोड को इंगित करता है।

ट्री (Tree): एक गैर-रैखिक पदानुक्रमित संरचना है जिसमें नोड्स और उन्हें जोड़ने वाले एज (Edges) होते हैं। इसमें केवल एक मुख्य रूट नोड (Root Node) होता है तथा शेष नोड्स उप-वृक्षों (Subtrees) में विभाजित होते हैं।

• डिग्री (Degree): किसी नोड के प्रत्यक्ष संतति (children) नोड्स की कुल संख्या।
• पर्ण नोड (Leaf Node): वह नोड जिसकी डिग्री शून्य हो (कोई संतान नहीं)।
• ऊंचाई (Height): रूट से सबसे दूर स्थित पर्ण नोड तक के सबसे लंबे पथ की लंबाई। $h$ ऊंचाई के बाइनरी ट्री में अधिकतम नोड संख्या $N_{\max} = 2^{h+1} - 1$ होती है।
• बाइनरी ट्री: ऐसा ट्री जिसमें प्रत्येक नोड के अधिकतम दो बच्चे हो सकते हैं (बायाँ बच्चा एवं दायाँ बच्चा)।

बाइनरी सर्च ट्री (BST): एक विशेष बाइनरी ट्री है जो निम्नलिखित नियम का कड़ाई से पालन करता है: