अमूर्त डेटा प्रकार

Not to be confused with बीजगणितीय डेटा प्रकार.

कंप्यूटर विज्ञान में अमूर्त डेटा प्रकार (एडीटी) डेटा प्रकारों के लिए एक गणितीय मॉडल है। अमूर्त डेटा प्रकार को उसके व्यवहार (सिमेंटिक्स (कंप्यूटर विज्ञान)) द्वारा परिभाषित किया जाता है। डेटा के उपयोगकर्ता (कंप्यूटिंग) के दृष्टिकोण से विशेष रूप से संभावित मूल्यों के संदर्भ में इस प्रकार के डेटा पर संभावित संचालन और इन परिचालनों का व्यवहार गणितीय मॉडल डेटा संरचनाओं के विपरीत है। जो डेटा के ठोस प्रतिनिधित्व हैं और एक कार्यान्वयनकर्ता के दृष्टिकोण हैं, परन्तु उपयोगकर्ता नहीं है।

औपचारिक रूप से एडीटी को वस्तुओं के एक वर्ग के रूप में परिभाषित किया जा सकता है। जिसका तार्कपूर्ण व्यवहार मूल्यों के एक समुच्चय और संचालन के समुच्चय द्वारा परिभाषित किया गया है। यह गणित में बीजगणितीय संरचना के अनुरूप है। व्यवहार से क्या अभिप्राय लेखक द्वारा भिन्न होता है। व्यवहार दो मुख्य प्रकार के औपचारिक विनिर्देशों के साथ स्वयंसिद्ध (बीजगणितीय) विनिर्देश और अमूर्त मॉडल होता है। ये क्रमशः अमूर्त मशीन के स्वयंसिद्ध शब्दार्थ और परिचालन शब्दार्थ के अनुरूप हैं। कुछ लेखकों में समय (कंप्यूटिंग संचालन के लिए) और स्थान (मूल्यों का प्रतिनिधित्व करने के लिए) दोनों के संदर्भ में कम्प्यूटेशनल जटिलता सिद्धांत (क्रय मूल्य) भी सम्मिलित है। व्यवहार में कई सामान्य डेटा प्रकार एडीटीएस नहीं हैं क्योंकि अमूर्तता सही नहीं है और उपयोगकर्ताओं को अंकगणितीय अतिप्रवाह जैसे विषयों के बारे में पता होना चाहिए। जो प्रतिनिधित्व के कारण होते हैं। उदाहरण के लिए पूर्णांकों को प्रायः निश्चित-चौड़ाई मान (32-बिट या 64-बिट बाइनरी संख्या) के रूप में संग्रहीत किया जाता है और इस प्रकार अधिकतम मान पार होने पर पूर्णांक अतिप्रवाह का अनुभव होता है।

एडीटी एक सैद्धांतिक अवधारणा है। कंप्यूटर विज्ञान में कलन विधि, डेटा संरचना और सॉफ्टवेयर तन्त्र के प्रारूप और विश्लेषण में उपयोग किया जाता है और कंप्यूटर भाषाओं की विशिष्ट विशेषताओं के अनुरूप नहीं है। कंप्यूटर की मुख्य भाषाएँ सीधे औपचारिक रूप से निर्दिष्ट एडीटी का समर्थन नहीं करती हैं। चूंकि विभिन्न भाषा सुविधाएँ एडीटी के कुछ नियमों के अनुरूप हैं और एडीटी के साथ सरलता से भ्रमित हो जाती हैं। इनमें अमूर्त प्रकार, अपारदर्शी डेटा प्रकार, प्रोटोकॉल (ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग) और अनुबंध द्वारा प्रारूप सम्मिलित हैं। सीएलयू (प्रोग्रामिंग लैंग्वेज) भाषा के विकास के भाग के रूप में एडीटी को पहली बार 1974 में बारबरा लिस्कोव और स्टीफन एन ज़िल्स द्वारा प्रस्तावित किया गया था।

सार डेटा प्रकार

उदाहरण के लिए पूर्णांक एक एडीटी होते हैं। जिन्हें मान ..., -2, -1, 0, 1, 2, ... के रूप में परिभाषित किया जाता है और जोड़, घटाव, गुणा और भाग की संक्रियाओं के साथ-साथ से अधिक के रूप में परिभाषित किया जाता है। जो परिचित गणित के अनुसार व्यवहार करते हैं। पूर्णांक विभाजन की देखभाल के साथ, कम, आदि स्वतंत्र रूप से कंप्यूटर द्वारा पूर्णांकों का प्रतिनिधित्व कैसे किया जाता है। स्पष्ट रूप से व्यवहार में विभिन्न स्वयंसिद्धों (संबद्धता और जोड़ की क्रमविनिमेयता आदि) का पालन करना और संचालन पर पूर्व नियम (शून्य से विभाजित नहीं किया जा सकता) सम्मिलित है। सामान्यतः पूर्णांकों को डेटा संरचना में बाइनरी संख्या के रूप प्रायः दो के पूरक के रूप में दर्शाया जाता है। किन्तु बाइनरी-कोडित दशमलव या एक के पूरक में हो सकता है। किन्तु अधिकांश उद्देश्यों के लिए उपयोगकर्ता प्रतिनिधित्व के ठोस विकल्प के अतिरिक्त अमूर्तता के साथ काम कर सकता है और केवल डेटा का उपयोग कर सकते हैं। जैसे कि प्रकार वास्तव में सार थे।

एक एडीटी में न केवल संचालन होते हैं बल्कि मूल्यों का एक डोमेन भी होता है, और परिभाषित संचालन पर बाधाएं होती हैं। एक इंटरफ़ेस सामान्यतः केवल संचालन को संदर्भित करता है, और शायद संचालन पर कुछ बाधाएं, जैसे कि पूर्व-शर्तें और पश्च-शर्तें; किन्तु संचालन के बीच संबंध जैसी अन्य बाधाओं के लिए नहीं।

उदाहरण के लिए, एक सार स्टैक (अमूर्त डेटा प्रकार), जो एक लास्ट-इन-फर्स्ट-आउट संरचना है, को तीन ऑपरेशनों द्वारा परिभाषित किया जा सकता है: push, जो स्टैक पर एक डेटा आइटम सम्मिलित करता है; पॉप, जो डेटा आइटम को इससे हटा देता है; और peek या top, जो स्टैक के शीर्ष पर डेटा आइटम को बिना हटाए एक्सेस करता है। एक सार कतार (अमूर्त डेटा प्रकार), जो एक पहले-में-पहले-आउट संरचना है, में भी तीन ऑपरेशन होंगे: enqueue, जो कतार में एक डेटा आइटम सम्मिलित करता है; dequeue, जो इसमें से पहला डेटा आइटम हटा देता है; और सामने, जो क्यू में पहले डेटा आइटम को एक्सेस और सर्व करता है। यदि ये संपूर्ण परिभाषाएँ होतीं, तो इन दो डेटा प्रकारों और उनके बहुत भिन्न अपेक्षित क्रम व्यवहार में अंतर करने का कोई तरीका नहीं होता। इस प्रकार, एक बाधा पेश की जाती है कि स्टैक के लिए यह निर्दिष्ट करता है कि प्रत्येक पॉप हमेशा सबसे हाल ही में धकेले गए आइटम को लौटाता है (और हटाता है) जो अभी तक पॉप नहीं किया गया है, और कतार के लिए (इसके विपरीत) निर्दिष्ट करता है कि पॉप कम से कम हाल ही में धकेले गए आइटम पर काम करता है .

एल्गोरिदम के एल्गोरिदम का विश्लेषण करते समय, यह भी निर्दिष्ट किया जा सकता है कि सभी ऑपरेशन एक ही समय लेते हैं चाहे कितने डेटा आइटम ढेर में धकेल दिए गए हों, और यह कि स्टैक प्रत्येक तत्व के लिए भंडारण की निरंतर मात्रा का उपयोग करता है। चूंकि, समय सीमा को हमेशा एडीटी की परिभाषा का हिस्सा नहीं माना जाता है।

परिचय

सार डेटा प्रकार विशुद्ध रूप से सैद्धांतिक इकाइयाँ हैं, जिनका उपयोग (अन्य बातों के अलावा) अमूर्त एल्गोरिदम के विवरण को सरल बनाने के लिए, डेटा संरचनाओं को वर्गीकृत और मूल्यांकन करने के लिए, और औपचारिक रूप से प्रोग्रामिंग भाषाओं के प्रकार तन्त्र का वर्णन करने के लिए किया जाता है। चूंकि, एक एडीटी विशिष्ट डेटा प्रकारों या डेटा संरचनाओं द्वारा, कई तरीकों से और कई प्रोग्रामिंग भाषाओं में कार्यान्वयन हो सकता है; या एक औपचारिक विनिर्देश भाषा में वर्णित है। एडीटीs को प्रायः मॉड्यूलर प्रोग्रामिंग के रूप में लागू किया जाता है: मॉड्यूल का इंटरफ़ेस (कंप्यूटर साइंस) एडीटी संचालन के अनुरूप प्रक्रियाओं की घोषणा करता है, कभी-कभी टिप्पणी (कंप्यूटर प्रोग्रामिंग) के साथ जो बाधाओं का वर्णन करता है। यह सूचना छिपाने की रणनीति क्लाइंट (कंप्यूटिंग) प्रोग्राम को परेशान किए बिना मॉड्यूल के कार्यान्वयन को बदलने की अनुमति देती है।

सार डेटा प्रकार शब्द को कई बीजगणितीय संरचनाओं के सामान्यीकृत दृष्टिकोण के रूप में भी माना जा सकता है, जैसे जाली, समूह और छल्ले। अमूर्त डेटा प्रकारों की धारणा डेटा अमूर्तता की अवधारणा से संबंधित है, जो वस्तु-उन्मुख प्रोग्रामिंग भाषा में महत्वपूर्ण है| सॉफ्टवेयर इंजीनियरिंग के लिए अनुबंध पद्धतियों द्वारा ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग और प्रारूप।

एक सार डेटा प्रकार परिभाषित करना

एक अमूर्त डेटा प्रकार को डेटा ऑब्जेक्ट्स के गणितीय मॉडल के रूप में परिभाषित किया जाता है जो डेटा प्रकार के साथ-साथ इन ऑब्जेक्ट्स पर काम करने वाले कार्यों को भी बनाता है। उन्हें परिभाषित करने के लिए कोई मानक सम्मेलन नहीं हैं। अनिवार्य (या परिचालन) और कार्यात्मक (या स्वयंसिद्ध) परिभाषा शैलियों के बीच एक व्यापक विभाजन तैयार किया जा सकता है।

आदेशात्मक-शैली परिभाषा

अनिवार्य प्रोग्रामिंग भाषाओं के सिद्धांत में, एक सार डेटा संरचना को एक इकाई के रूप में माना जाता है जो कि परिवर्तनशील है - जिसका अर्थ है कि यह अलग-अलग समय पर अलग-अलग राज्यों में हो सकता है। कुछ ऑपरेशन एडीटी की स्थिति को बदल सकते हैं; इसलिए, जिस क्रम में संचालन का मूल्यांकन किया जाता है वह महत्वपूर्ण है, और अलग-अलग समय पर निष्पादित होने पर समान संस्थाओं पर समान संचालन के अलग-अलग प्रभाव हो सकते हैं। यह एक कंप्यूटर के निर्देशों या अनिवार्य भाषा के आदेशों और प्रक्रियाओं के अनुरूप है। इस दृष्टिकोण को रेखांकित करने के लिए यह कहना प्रथागत है कि मूल्यांकन के अतिरिक्त परिचालनों को निष्पादित या लागू किया जाता है, अमूर्त एल्गोरिदम का वर्णन करते समय प्रायः उपयोग की जाने वाली अनिवार्य शैली के समान। (अधिक विवरण के लिए डोनाल्ड नुथ द्वारा कंप्यूटर प्रोग्रामिंग की कला देखें)।

सार चर

एडीटी की अनिवार्य-शैली की परिभाषाएं प्रायः अमूर्त चर की अवधारणा पर निर्भर करती हैं, जिसे सबसे सरल गैर-तुच्छ एडीटी माना जा सकता है। एक अमूर्त चर V एक परिवर्तनशील इकाई है जो दो संक्रियाओं को स्वीकार करता है:

• store(V, x) जहाँ x अनिर्दिष्ट प्रकृति का मान है;
• fetch(V), जो एक मान देता है,

उस विवशता के साथ

• fetch(V) हमेशा उसी वेरिएबल V पर नवीनतम store(V, x) ऑपरेशन में उपयोग किए गए मान x को लौटाता है।

भंडारण से पहले लाने की अनुमति नहीं दी जा सकती है, एक निश्चित परिणाम के लिए परिभाषित किया गया है, या (कम वांछनीय रूप से), व्यवहार को अनिर्दिष्ट छोड़ दें।

कई प्रोग्रामिंग भाषाओं की तरह, ऑपरेशन store(V, x) को प्रायः V ← x (या कुछ समान अंकन) लिखा जाता है, और fetch(V) निहित होता है जब कोई चर V का उपयोग उस संदर्भ में किया जाता है जहाँ एक मान की आवश्यकता होती है। इस प्रकार, उदाहरण के लिए, V ← V + 1 को सामान्यतः store(V,fetch(V) + 1) के लिए शॉर्टहैंड समझा जाता है।

इस परिभाषा में, यह स्पष्ट रूप से माना जाता है कि नाम हमेशा अलग होते हैं: एक चर U में मान संग्रहीत करने से एक अलग चर V की स्थिति पर कोई प्रभाव नहीं पड़ता है। इस धारणा को स्पष्ट करने के लिए, कोई बाधा जोड़ सकता है जो

• यदि U और V भिन्न चर हैं, तो अनुक्रम {store(U, x); store(V, y) } { store(V, y) के बराबर है; स्टोर(यू, एक्स)}।

आम तौर पर, एडीटी परिभाषाएँ प्रायः मानती हैं कि कोई भी ऑपरेशन जो एक एडीटी उदाहरण की स्थिति को बदलता है, उसी एडीटी के किसी अन्य उदाहरण की स्थिति पर कोई प्रभाव नहीं पड़ता है, जब तक कि एडीटी स्वयंसिद्ध कुछ उदाहरणों को कनेक्टेड के रूप में परिभाषित नहीं करता है (अलियासिंग (कंप्यूटिंग) देखें) एक विशिष्ट तरीका। सबसे आम ऐसे कनेक्शनों में सम्मिलित हैं:

• अलियासिंग, जिसमें दो या दो से अधिक नाम सटीक एक ही डेटा ऑब्जेक्ट को संदर्भित करते हैं।
• रचना, जिसमें एडीटी को (समान या अन्य) एडीटीs के उदाहरण सम्मिलित करने के लिए परिभाषित किया गया है।
• संदर्भ, जिसमें एडीटी को (समान या अन्य) एडीटी के उदाहरण के संदर्भ में परिभाषित किया गया है।

उदाहरण के लिए, सार रिकॉर्ड (कंप्यूटर विज्ञान) को सम्मिलित करने के लिए एक अमूर्त चर की परिभाषा का विस्तार करते समय, एक रिकॉर्ड चर आर के क्षेत्र एफ पर संचालन, स्पष्ट रूप से एफ को सम्मिलित करता है, जो आर से अलग है, किन्तु इसका एक हिस्सा भी है।

एडीटी की परिभाषा अपने उदाहरणों के लिए संग्रहीत मूल्य (एस) को एक विशिष्ट समुच्चय एक्स के सदस्यों तक सीमित कर सकती है, जिसे उन चरों की श्रेणी कहा जाता है। उदाहरण के लिए, एक ढेर या कतार जैसे समुच्चय के लिए एक एडीटी, कतार में सभी वस्तुओं को पूर्णांक होने के लिए बाध्य कर सकता है, या कम से कम सभी को एक ही प्रकार का हो सकता है (देखें Homogeneity_and_heterogeneity_(statistics))। प्रोग्रामिंग भाषाओं की तरह, ऐसे प्रतिबंध एल्गोरिदम के विवरण और विश्लेषण को सरल बना सकते हैं और इसकी पठनीयता में सुधार कर सकते हैं।

ध्यान दें कि यह परिभाषा fetch(V) के मूल्यांकन के परिणाम के बारे में कुछ भी नहीं बताती है जब V प्रारंभिक नहीं है, अर्थात, V पर कोई store ऑपरेशन करने से पहले। An एल्गोरिथम जो ऐसा करता है उसे अमान्य माना जा सकता है, या तो (ए) क्योंकि एडीटी इस तरह के ऑपरेशन को प्रतिबंधित करता है, या (बी) केवल इसलिए कि इसका प्रभाव एडीटी द्वारा परिभाषित नहीं किया गया है। हालांकि, कुछ महत्वपूर्ण एल्गोरिदम हैं जिनकी दक्षता दृढ़ता से इस धारणा पर निर्भर करती है कि ऐसा fetch कानूनी है, और वेरिएबल की सीमा में कुछ मनमाना मान देता है।)

उदाहरण निर्माण

कुछ एल्गोरिदम को कुछ एडीटी (जैसे नए चर, या नए ढेर) के नए उदाहरण बनाने की आवश्यकता होती है। इस तरह के एल्गोरिदम का वर्णन करने के लिए, सामान्यतः एडीटी परिभाषा में create() ऑपरेशन सम्मिलित होता है जो एडीटी का एक उदाहरण देता है, सामान्यतः स्वयंसिद्धों के बराबर

• create() का परिणाम एल्गोरिथम द्वारा पहले से उपयोग किए जा रहे किसी भी उदाहरण से अलग है।

अन्य उदाहरणों के साथ आंशिक अलियासिंग को भी बाहर करने के लिए इस स्वयंसिद्ध को मजबूत किया जा सकता है. व्यावहारिक उपयोग के लिए, जैसे स्वयंसिद्ध अभी भी create() के कार्यान्वयन की अनुमति दे सकता है जो पहले से बनाए गए उदाहरण को प्राप्त करने के लिए प्रोग्राम के लिए दुर्गम हो गया है; चूंकि, परिभाषित करना कि ऐसा उदाहरण भी समान है, विशेष रूप से अमूर्त में (हालांकि स्मृति का एक पुन: उपयोग किया गया ब्लॉक भी कुछ इंद्रियों में केवल एक ही वस्तु है)।

उदाहरण: सार ढेर (अनिवार्य)

एक अन्य उदाहरण के रूप में, अमूर्त स्टैक की अनिवार्य-शैली की परिभाषा निर्दिष्ट कर सकती है कि स्टैक S की स्थिति को केवल संचालन द्वारा संशोधित किया जा सकता है

• push(S, x), जहाँ x अनिर्दिष्ट प्रकृति का कुछ मान है;
• पॉप(S), जो परिणाम के रूप में एक मूल्य देता है,

उस विवशता के साथ

• किसी भी मान x और किसी अमूर्त चर V के लिए, संचालन का क्रम {push(S, x); वी ← पॉप(S) }, V ← x के बराबर है।

चूँकि असाइनमेंट V ← x, परिभाषा के अनुसार, S की स्थिति को नहीं बदल सकता है, इस स्थिति का तात्पर्य है कि V ← pop(S) S को उस स्थिति में पुनर्स्थापित करता है जो push(एस, एक्स)। इस स्थिति से और अमूर्त चर के गुणों से, यह इस प्रकार है, उदाहरण के लिए, अनुक्रम

{ पुश(S, x); पुश(एस, वाई); यू ← पॉप(एस); पुश(S, z); वी ← पॉप(एस); डब्ल्यू ← पॉप(एस)}

जहां x, y, और z कोई मान हैं, और U, V, W जोड़ीदार विशिष्ट चर हैं, के समतुल्य है

{ यू ← वाई; वी ← जेड; डब्ल्यू ← एक्स}

यहाँ यह स्पष्ट रूप से माना जाता है कि स्टैक इंस्टेंस पर संचालन अन्य स्टैक सहित किसी अन्य एडीटी इंस्टेंस की स्थिति को संशोधित नहीं करता है; वह है,

• किसी भी मान x, y, और किसी भी विशिष्ट स्टैक S और T के लिए, अनुक्रम { push(S, x); push(T, y) } { push(T, y) के बराबर है; पुश(एस, एक्स)}।

एक सार स्टैक परिभाषा में सामान्यतः एक बूलियन मान-मूल्यवान फ़ंक्शन खाली(S) और एक बनाना() ऑपरेशन सम्मिलित होता है जो एक स्टैक उदाहरण लौटाता है, इसके समकक्ष स्वयंसिद्धों के साथ

• create() ≠ S किसी भी पिछले स्टैक के लिए S (एक नया बनाया गया स्टैक पिछले सभी स्टैक से अलग है);
• खाली(बनाना()) (नया बनाया गया ढेर खाली है);
• नहीं खाली(पुश(S, x)) (किसी चीज़ को ढेर में धकेलने से वह गैर-रिक्त हो जाती है)।

एक उदाहरण शैली

कभी-कभी एडीटी को परिभाषित किया जाता है जैसे कि एल्गोरिथम के निष्पादन के दौरान इसका केवल एक उदाहरण मौजूद था, और सभी ऑपरेशन उस उदाहरण पर लागू किए गए थे, जो स्पष्ट रूप से नोट नहीं किया गया है। उदाहरण के लिए, उपरोक्त अमूर्त स्टैक को ऑपरेशन push(x) और pop() के साथ परिभाषित किया जा सकता था, जो केवल मौजूदा स्टैक पर काम करता है। इस शैली में एडीटी परिभाषाओं को सरलता से एडीटी के कई सह-अस्तित्व वाले उदाहरणों को स्वीकार करने के लिए फिर से लिखा जा सकता है, एक स्पष्ट उदाहरण पैरामीटर (जैसे पिछले उदाहरण में S) को प्रत्येक ऑपरेशन में जोड़ा जाता है जो अंतर्निहित उदाहरण का उपयोग करता है या संशोधित करता है।

दूसरी ओर, कुछ एडीटीs को कई उदाहरण ग्रहण किए बिना सार्थक रूप से परिभाषित नहीं किया जा सकता है। यह वह मामला है जब एक एकल ऑपरेशन एडीटी के पैरामीटर के रूप में दो अलग-अलग उदाहरण लेता है। एक उदाहरण के लिए, तुलना(S, T) ऑपरेशन के साथ अमूर्त स्टैक की परिभाषा को बढ़ाने पर विचार करें जो यह जाँचता है कि स्टैक S और T में समान क्रम में समान आइटम हैं या नहीं।

कार्यात्मक-शैली परिभाषा

एडीटी को परिभाषित करने का एक और तरीका, कार्यात्मक प्रोग्रामिंग की भावना के करीब, संरचना के प्रत्येक राज्य को एक अलग इकाई के रूप में माना जाता है। इस दृष्टि से, एडीटी को संशोधित करने वाले किसी भी ऑपरेशन को एक फ़ंक्शन (गणित) के रूप में तैयार किया जाता है जो पुराने राज्य को तर्क के रूप में लेता है और परिणाम के भाग के रूप में नया राज्य देता है। अनिवार्य संचालन के विपरीत, इन कार्यों का कोई दुष्प्रभाव (कंप्यूटर विज्ञान) नहीं है। इसलिए, जिस क्रम में उनका मूल्यांकन किया जाता है वह सारहीन है, और समान तर्कों (समान इनपुट राज्यों सहित) पर लागू समान ऑपरेशन हमेशा समान परिणाम (और आउटपुट स्थिति) लौटाएगा।

कार्यात्मक दृश्य में, विशेष रूप से, अनिवार्य चर के शब्दार्थ के साथ एक अमूर्त चर को परिभाषित करने का कोई तरीका (या आवश्यकता) नहीं है (अर्थात, fetch और store संचालन के साथ) . मानों को वेरिएबल्स में संग्रहीत करने के अतिरिक्त, उन्हें फ़ंक्शन के तर्क के रूप में पास किया जाता है।

उदाहरण: सार ढेर (कार्यात्मक)

उदाहरण के लिए, एक अमूर्त ढेर की एक पूर्ण कार्यात्मक-शैली परिभाषा तीन परिचालनों का उपयोग कर सकती है:

• push: एक स्टैक स्थिति और मनमाना मान लेता है, एक स्टैक स्थिति लौटाता है;
• शीर्ष: एक ढेर स्थिति लेता है, एक मान देता है;
• पॉप: स्टैक स्थिति लेता है, स्टैक स्थिति लौटाता है।

कार्यात्मक-शैली की परिभाषा में create ऑपरेशन की कोई आवश्यकता नहीं है। दरअसल, स्टैक इंस्टेंस की कोई धारणा नहीं है। स्टैक स्टेट्स को सिंगल स्टैक स्ट्रक्चर के संभावित स्टेट्स के रूप में माना जा सकता है, और दो-स्टैक स्टेट्स जिनमें समान क्रम में समान मान होते हैं, को समान स्टेट्स माना जाता है। यह दृश्य वास्तव में कुछ ठोस कार्यान्वयनों के व्यवहार को प्रतिबिंबित करता है, जैसे कि हैश विपक्ष के साथ लिंक्ड सूचियाँ।

create() के अतिरिक्त, सार स्टैक की एक कार्यात्मक-शैली परिभाषा एक विशेष स्टैक स्थिति के अस्तित्व को मान सकती है, खाली स्टैक, जिसे Λ या () जैसे विशेष प्रतीक द्वारा निर्दिष्ट किया जाता है; या bottom() ऑपरेशन परिभाषित करें जो कोई तर्क नहीं लेता है और इस विशेष स्टैक स्थिति को लौटाता है। ध्यान दें कि स्वयंसिद्धों का अर्थ है

• पुश(Λ, x) ≠ Λ.

स्टैक की कार्यात्मक-शैली की परिभाषा में किसी को खाली विधेय की आवश्यकता नहीं होती है: इसके अतिरिक्त, कोई यह परीक्षण कर सकता है कि स्टैक खाली है या नहीं, यह परीक्षण करके कि क्या यह Λ के बराबर है।

ध्यान दें कि ये सिद्धांत top(s) या pop(s) के प्रभाव को परिभाषित नहीं करते हैं, जब तक कि s push। चूँकि push स्टैक को गैर-खाली छोड़ देता है, वे दो ऑपरेशन अपरिभाषित हैं (इसलिए अमान्य) जब s = Λ। दूसरी ओर, स्वयंसिद्ध (और साइड इफेक्ट की कमी) का अर्थ है कि push(s, x) = push(t, y) यदि और केवल यदि x = वाई और एस = टी।

जैसा कि गणित की कुछ अन्य शाखाओं में होता है, यह मान लेना भी प्रथागत है कि स्टैक अवस्थाएँ केवल वे हैं जिनका अस्तित्व स्वयंसिद्धों से सीमित संख्या में चरणों में सिद्ध किया जा सकता है। उपरोक्त अमूर्त स्टैक उदाहरण में, इस नियम का अर्थ है कि प्रत्येक स्टैक मूल्यों का एक परिमित अनुक्रम है, जो pops की सीमित संख्या के बाद खाली स्टैक (Λ) बन जाता है। अपने आप में, ऊपर दिए गए स्वयंसिद्ध अनंत स्टैक के अस्तित्व को बाहर नहीं करते हैं (जो हमेशा के लिए पॉपपेड हो सकते हैं, हर बार एक अलग स्थिति उत्पन्न करते हैं) या गोलाकार ढेर (जो एक परिमित संख्या के बाद उसी स्थिति में वापस आ जाते हैं) of पॉपs)। विशेष रूप से, वे ऐसे राज्यों को बाहर नहीं करते हैं जैसे pop(s) = s या push(s, x) = s कुछ x के लिए। हालांकि, चूंकि दिए गए कार्यों के साथ ऐसे ढेर राज्य प्राप्त नहीं किए जा सकते हैं, इसलिए उन्हें अस्तित्व में नहीं माना जाता है।

जटिलता सम्मिलित करना है या नहीं

स्वयंसिद्धों के संदर्भ में व्यवहार के अलावा, एडीटी ऑपरेशन की परिभाषा में, उनके एल्गोरिदम का विश्लेषण भी सम्मिलित करना संभव है। C++ मानक टेम्पलेट लाइब्रेरी के प्रारूपर अलेक्जेंडर स्टेपानोव ने तर्क देते हुए STL विनिर्देशन में जटिलता की गारंटी सम्मिलित की:

The reason for introducing the notion of abstract data types was to allow interchangeable software modules. You cannot have interchangeable modules unless these modules share similar complexity behavior. If I replace one module with another module with the same functional behavior but with different complexity tradeoffs, the user of this code will be unpleasantly surprised. I could tell him anything I like about data abstraction, and he still would not want to use the code. Complexity assertions have to be part of the interface.

— Alexander Stepanov

अमूर्त डेटा टाइपिंग के लाभ

एनकैप्सुलेशन

अमूर्तता (कंप्यूटर विज्ञान) एक वादा प्रदान करता है कि एडीटी के किसी भी कार्यान्वयन में कुछ गुण और क्षमताएं हैं; एडीटी ऑब्जेक्ट का उपयोग करने के लिए यह जानना आवश्यक है। यह प्रोग्रामिंग भाषा में डेटा प्रकार के साथ प्रयोग करने के लिए तैयार है परिधीय और गैर परिधीय डेटा प्रकार।

परिवर्तन का स्थानीयकरण

एडीटी ऑब्जेक्ट का उपयोग करने वाले कोड को एडीटी के कार्यान्वयन को बदलने पर संपादित करने की आवश्यकता नहीं होगी। चूंकि कार्यान्वयन में कोई भी परिवर्तन अभी भी इंटरफ़ेस का अनुपालन करना चाहिए, और चूंकि एडीटी ऑब्जेक्ट का उपयोग करने वाला कोड केवल इंटरफ़ेस में निर्दिष्ट गुणों और क्षमताओं को संदर्भित कर सकता है, कोड में किसी भी बदलाव की आवश्यकता के बिना कार्यान्वयन में परिवर्तन किए जा सकते हैं जहां एडीटी का उपयोग किया जाता है .

लचीलापन

एडीटी के विभिन्न कार्यान्वयन, सभी समान गुणों और क्षमताओं वाले, समतुल्य हैं और एडीटी का उपयोग करने वाले कोड में कुछ हद तक एकांतर रूप से उपयोग किया जा सकता है। विभिन्न परिस्थितियों में एडीटी वस्तुओं का उपयोग करते समय यह बहुत अधिक लचीलापन देता है। उदाहरण के लिए, अलग-अलग परिस्थितियों में एडीटी के विभिन्न कार्यान्वयन अधिक कुशल हो सकते हैं; प्रत्येक का उस स्थिति में उपयोग करना संभव है जहां वे बेहतर हैं, इस प्रकार समग्र दक्षता में वृद्धि होती है।

विशिष्ट संचालन

कुछ ऑपरेशन जो प्रायः एडीटीs (संभवतः अन्य नामों के तहत) के लिए निर्दिष्ट होते हैं

• तुलना करें(s, t), जो परीक्षण करता है कि क्या दो दृष्टान्तों की अवस्थाएँ किसी अर्थ में समान हैं;
• हैश(s), जो उदाहरण की स्थिति से कुछ मानक हैश फंकशन की गणना करता है;
• प्रिंट(s) या शो(s), जो उदाहरण की स्थिति का मानव-पठनीय प्रतिनिधित्व उत्पन्न करता है।

अनिवार्य-शैली एडीटी परिभाषाओं में, प्रायः यह भी पाया जाता है

• create(), जो एडीटी का एक नया उदाहरण देता है;
• प्रारंभिक(s), जो आगे के संचालन के लिए एक नया बनाया गया उदाहरण तैयार करता है, या इसे कुछ प्रारंभिक अवस्था में रीसमुच्चय करता है;
• प्रतिलिपि(s, t), जो उदाहरण s को t के समतुल्य स्थिति में रखती है;
• क्लोन(t), जो s ← create(), कॉपी(s, t) करता है, और s लौटाता है;
• मुफ़्त(s) या नष्ट(s), जो s द्वारा उपयोग की गई मेमोरी और अन्य संसाधनों को पुनः प्राप्त करता है।

मुफ्त ऑपरेशन सामान्य रूप से प्रासंगिक या सार्थक नहीं है, क्योंकि एडीटीs सैद्धांतिक संस्थाएं हैं जो मेमोरी का उपयोग नहीं करती हैं। चूंकि, यह आवश्यक हो सकता है जब किसी को एडीटी का उपयोग करने वाले एल्गोरिथम द्वारा उपयोग किए गए संग्रहण का विश्लेषण करने की आवश्यकता हो। उस स्थिति में, किसी को अतिरिक्त सिद्धांतों की आवश्यकता होती है जो निर्दिष्ट करती है कि प्रत्येक एडीटी इंस्टेंस अपने राज्य के कार्य के रूप में कितनी मेमोरी का उपयोग करता है, और इसमें से कितना मुफ्त द्वारा पूल में लौटाया जाता है।

उदाहरण

कुछ सामान्य एडीटी, जो विभिन्न प्रकार के अनुप्रयोगों में उपयोगी साबित हुए हैं, हैं

• संग्रह (सार डेटा प्रकार)
• कंटेनर (सार डेटा प्रकार)
• सूची (सार डेटा प्रकार)
• स्ट्रिंग (कंप्यूटर विज्ञान)
• सेट (सार डेटा प्रकार)
• मल्टीसेट
• सहयोगी सरणी
• मल्टीमैप
• ग्राफ (सार डेटा प्रकार)
• ट्री (डेटा संरचना)
• ढेर (सार डेटा प्रकार)
• कतार (सार डेटा प्रकार)
• प्राथमिकता कतार
• डबल-एंडेड कतार
• डबल-एंडेड प्राथमिकता कतार

इन एडीटी में से प्रत्येक को कई तरीकों और रूपों में परिभाषित किया जा सकता है, जरूरी नहीं कि समकक्ष। उदाहरण के लिए, एक अमूर्त स्टैक में गिनती ऑपरेशन हो सकता है या नहीं भी हो सकता है जो बताता है कि कितने आइटम पुश किए गए हैं और अभी तक पॉप नहीं हुए हैं। यह विकल्प न केवल इसके ग्राहकों के लिए बल्कि कार्यान्वयन के लिए भी एक अंतर बनाता है।

सार चित्रमय डेटा प्रकार

1979 में कंप्यूटर ग्राफिक्स के लिए एडीटी का विस्तार प्रस्तावित किया गया था: एक सार चित्रमय डेटा प्रकार (AGDT)। इसे नादिया मैग्नेनेट थल्मन और डेनियल थाल्मन द्वारा पेश किया गया था। एजीडीटी एक संरचित तरीके से ग्राफिकल ऑब्जेक्ट्स बनाने की सुविधा के साथ एडीटी के लाभ प्रदान करते हैं।

कार्यान्वयन

Further information: Opaque data type

एडीटी को लागू करने का अर्थ है प्रत्येक अमूर्त ऑपरेशन के लिए एक सबरूटीन प्रदान करना। एडीटी उदाहरणों को कुछ ठोस डेटा संरचना द्वारा दर्शाया जाता है जो एडीटी के विनिर्देशों के अनुसार उन प्रक्रियाओं द्वारा हेरफेर किया जाता है।

आम तौर पर, कई अलग-अलग ठोस डेटा संरचनाओं का उपयोग करके एक ही एडीटी को लागू करने के कई तरीके हैं। इस प्रकार, उदाहरण के लिए, एक अमूर्त ढेर को एक लिंक्ड सूची या एक ऐरे डेटा संरचना द्वारा कार्यान्वित किया जा सकता है।

ग्राहकों को कार्यान्वयन पर निर्भर रहने से रोकने के लिए, एडीटी को प्रायः एक या अधिक मॉड्यूल (प्रोग्रामिंग) में एक अपारदर्शी डेटा प्रकार के रूप में पैक किया जाता है, जिसके इंटरफ़ेस में केवल संचालन के हस्ताक्षर (संख्या और प्रकार के पैरामीटर और परिणाम) होते हैं। मॉड्यूल के कार्यान्वयन - अर्थात्, प्रक्रियाओं के निकाय और उपयोग की जाने वाली ठोस डेटा संरचना - को तब मॉड्यूल के अधिकांश ग्राहकों से छिपाया जा सकता है। इससे ग्राहकों को प्रभावित किए बिना कार्यान्वयन को बदलना संभव हो जाता है। यदि कार्यान्वयन उजागर होता है, तो इसे एक पारदर्शी डेटा प्रकार के रूप में जाना जाता है।

एडीटी लागू करते समय, प्रत्येक उदाहरण (अनिवार्य-शैली परिभाषाओं में) या प्रत्येक राज्य (कार्यात्मक-शैली परिभाषाओं में) सामान्यतः किसी प्रकार के हैंडल (कंप्यूटिंग) द्वारा दर्शाया जाता है। आधुनिक वस्तु-उन्मुख भाषाएँ, जैसे C++ और Java प्रोग्रामिंग भाषा, सार डेटा प्रकारों के एक रूप का समर्थन करती हैं। जब एक वर्ग का उपयोग एक प्रकार के रूप में किया जाता है, तो यह एक सार प्रकार होता है जो एक छिपे हुए प्रतिनिधित्व को संदर्भित करता है। इस मॉडल में, एडीटी को सामान्यतः एक वर्ग (कंप्यूटर विज्ञान) के रूप में लागू किया जाता है, और एडीटी का प्रत्येक उदाहरण सामान्यतः उस वर्ग का एक ऑब्जेक्ट (कंप्यूटर विज्ञान) होता है। मॉड्यूल का इंटरफ़ेस सामान्यतः निर्माणकर्ताओं को सामान्य प्रक्रियाओं के रूप में घोषित करता है, और अधिकांश अन्य एडीटी संचालन उस वर्ग के तरीके (कंप्यूटर प्रोग्रामिंग) के रूप में होते हैं। चूंकि, ऐसा दृष्टिकोण एडीटी में पाए जाने वाले कई प्रतिनिधित्वात्मक वेरिएंट को सरलता से एनकैप्सुलेट नहीं करता है। यह वस्तु-उन्मुख कार्यक्रमों की व्यापकता को भी कम कर सकता है। एक शुद्ध वस्तु-उन्मुख कार्यक्रम में जो इंटरफेस को प्रकार के रूप में उपयोग करता है, प्रकार व्यवहार को संदर्भित करता है, प्रतिनिधित्व नहीं।

=== उदाहरण: अमूर्त ढेर === का कार्यान्वयन एक उदाहरण के रूप में, यहाँ C (प्रोग्रामिंग लैंग्वेज) में उपरोक्त अमूर्त स्टैक का कार्यान्वयन है।

इम्पीरेटिव-स्टाइल इंटरफ़ेस

एक अनिवार्य-शैली इंटरफ़ेस हो सकता है: <वाक्यविन्यास लैंग = सीपीपी> टाइपपीफ स्ट्रक्चर स्टैक_रेप स्टैक_रेप; // प्रकार: ढेर उदाहरण प्रतिनिधित्व (अपारदर्शी रिकॉर्ड) टाइपपीफ स्टैक_रेप * स्टैक_टी; // टाइप करें: स्टैक इंस्टेंस (अपारदर्शी सूचक) को हैंडल करें टाइपपीफ शून्य * स्टैक_आइटम; // प्रकार: स्टैक उदाहरण में संग्रहीत मूल्य (मनमाना पता)

स्टैक_टी स्टैक_क्रिएट (शून्य); // एक नया खाली स्टैक उदाहरण बनाता है शून्य स्टैक_पुश (स्टैक_टी एस, स्टैक_आइटम एक्स); // स्टैक के शीर्ष पर एक आइटम जोड़ता है स्टैक_आइटम स्टैक_पॉप (स्टैक_टी एस); // शीर्ष आइटम को स्टैक से हटा दें और इसे वापस कर दें बूल स्टैक_एम्प्टी (स्टैक_टी एस); // जाँचता है कि क्या स्टैक खाली है </वाक्यविन्यास हाइलाइट>

इस इंटरफ़ेस का उपयोग निम्नलिखित तरीके से किया जा सकता है: <वाक्यविन्यास लैंग = सीपीपी>

1. सम्मिलित <stack.h> // में स्टैक इंटरफ़ेस सम्मिलित है

स्टैक_टी एस = स्टैक_क्रिएट (); // एक नया खाली स्टैक उदाहरण बनाता है इंट एक्स = 17; स्टैक_पुश (एस, और एक्स); // स्टैक के शीर्ष पर x का पता जोड़ता है शून्य * वाई = स्टैक_पॉप (एस); // स्टैक से x का पता हटाता है और इसे वापस करता है if (stack_empty(s)) { } // स्टैक खाली होने पर कुछ करता है </वाक्यविन्यास हाइलाइट>

इस इंटरफ़ेस को कई तरह से लागू किया जा सकता है। कार्यान्वयन मनमाने ढंग से अक्षम हो सकता है, क्योंकि उपरोक्त एडीटी की औपचारिक परिभाषा निर्दिष्ट नहीं करती है कि ढेर कितनी जगह का उपयोग कर सकता है, न ही प्रत्येक ऑपरेशन में कितना समय लगना चाहिए। यह यह भी निर्दिष्ट नहीं करता है कि कॉल x ← pop(s) के बाद स्टैक स्थिति मौजूद रहती है या नहीं।

व्यवहार में औपचारिक परिभाषा में यह निर्दिष्ट होना चाहिए कि स्थान धकेले गए आइटमों की संख्या के समानुपाती है और अभी तक पॉप नहीं हुआ है; और ऊपर दिए गए प्रत्येक ऑपरेशन को उस संख्या से स्वतंत्र रूप से निरंतर समय में पूरा करना चाहिए। इन अतिरिक्त विशिष्टताओं का अनुपालन करने के लिए, कार्यान्वयन दो पूर्णांकों (एक आइटम संख्या और सरणी आकार) के साथ एक लिंक की गई सूची, या एक सरणी (गतिशील आकार बदलने के साथ) का उपयोग कर सकता है।

कार्यात्मक-शैली इंटरफ़ेस

कार्यात्मक प्रोग्रामिंग भाषाओं के लिए कार्यात्मक-शैली एडीटी परिभाषाएं अधिक उपयुक्त हैं, और इसके विपरीत। चूंकि, सी जैसी अनिवार्य भाषा में भी कोई कार्यात्मक-शैली इंटरफ़ेस प्रदान कर सकता है। उदाहरण के लिए: <वाक्यविन्यास लैंग = सीपीपी> टाइपपीफ स्ट्रक्चर स्टैक_रेप स्टैक_रेप; // प्रकार: ढेर राज्य प्रतिनिधित्व (अपारदर्शी रिकॉर्ड) टाइपपीफ स्टैक_रेप * स्टैक_टी; // टाइप करें: एक स्टैक स्थिति (अपारदर्शी सूचक) को संभालें टाइपपीफ शून्य * स्टैक_आइटम; // प्रकार: स्टैक स्थिति का मान (मनमाना पता)

स्टैक_टी स्टैक_खाली (शून्य); // खाली स्टैक स्थिति लौटाता है स्टैक_टी स्टैक_पुश (स्टैक_टी एस, स्टैक_आइटम एक्स); // स्टैक स्थिति के शीर्ष पर एक आइटम जोड़ता है और परिणामी स्टैक स्थिति देता है स्टैक_टी स्टैक_पॉप (स्टैक_टी एस); // शीर्ष आइटम को स्टैक स्थिति से हटाता है और परिणामी स्टैक स्थिति देता है स्टैक_आइटम स्टैक_टॉप (स्टैक_टी एस); // स्टैक स्थिति का शीर्ष आइटम लौटाता है </वाक्यविन्यास हाइलाइट>

एडीटी पुस्तकालय

कई आधुनिक प्रोग्रामिंग भाषाएं, जैसे कि सी ++ और जावा, मानक पुस्तकालयों के साथ आती हैं जो कई सामान्य एडीटी को लागू करती हैं, जैसे ऊपर सूचीबद्ध हैं।

अंतर्निहित सार डेटा प्रकार

कुछ प्रोग्रामिंग भाषाओं के विनिर्देश जानबूझकर कुछ अंतर्निहित डेटा प्रकारों के प्रतिनिधित्व के बारे में अस्पष्ट हैं, केवल उन कार्यों को परिभाषित करते हैं जो उन पर किए जा सकते हैं। इसलिए, उन प्रकारों को अंतर्निर्मित एडीटी के रूप में देखा जा सकता है। उदाहरण कई स्क्रिप्टिंग भाषाओं में सरणियाँ हैं, जैसे कि ऑक, लुआ (प्रोग्रामिंग भाषा), और पर्ल, जिसे सार सूची के कार्यान्वयन के रूप में माना जा सकता है।

यह भी देखें

• संकल्पना (जेनेरिक प्रोग्रामिंग)
• औपचारिक तरीके
• कार्यात्मक विनिर्देश
• सामान्यीकृत बीजगणितीय डेटा प्रकार
• प्रारंभिक बीजगणित
• लिस्कोव प्रतिस्थापन सिद्धांत
• सिद्धांत टाइप करें
• दीवारें और दर्पण

संदर्भ

• Liskov, Barbara; Zilles, Stephen (1974). "Programming with abstract data types". Proceedings of the ACM SIGPLAN Symposium on Very High Level Languages. SIGPLAN Notices. Vol. 9. pp. 50–59. CiteSeerX 10.1.1.136.3043. doi:10.1145/800233.807045.
• Dale, Nell; Walker, Henry M. (1996). Abstract Data Types: Specifications, Implementations, and Applications. Jones & Bartlett Learning. ISBN 978-0-66940000-7.

अग्रिम पठन

• Mitchell, John C.; Plotkin, Gordon (July 1988). "Abstract Types Have Existential Type" (PDF). ACM Transactions on Programming Languages and Systems. 10 (3): 470–502. doi:10.1145/44501.45065. S2CID 1222153. Archived (PDF) from the original on 2022-10-09.

बाहरी संबंध

• Media related to Abstract data types at Wikimedia Commons
• Abstract data type in NIST Dictionary of Algorithms and Data Structures