स्टैक (अमूर्त डेटाटाइप)

From Vigyanwiki

प्लेटों के स्टैक के समान, जोड़ना या हटाना केवल शीर्ष पर ही संभव है।
पुश और पॉप संचालन के साथ स्टैक रनटाइम का सरल प्रतिनिधित्व।

कंप्यूटर विज्ञान में, स्टैक एक अमूर्त डेटाटाइप है जो एलिमेंट (तत्व) के संग्रह मे अमूर्त डेटाटाइप के रूप में कार्य करता है, जिसमें दो मुख्य संचालन होते हैं:

  • पुश संचालन, जो संग्रह में एक एलिमेंट संबद्ध करता है।
  • पॉप संचालन, जो हाल ही में संबद्ध किए गए एलिमेंट को हटा देता है जिसे अभी तक हटाया नहीं गया था।

इसके अतिरिक्त, एक पीक संचालन, स्टैक को संशोधित किए बिना, संबद्ध किए गए अंतिम एलिमेंट का मान वापस कर सकता है। इस संरचना को एक स्टैक कहना भौतिक वस्तुओं के एक समूह के अनुरूप होता है, जो प्लेटों के स्टैक जैसे एक दूसरे के ऊपर स्थित होता है।

जिस क्रम में एक स्टैक से एक एलिमेंट जोड़ा या हटाया जाता है उसे एलआईएफओ द्वारा संदर्भित अंतिम या पहले लेआउट के रूप में वर्णित किया जाता है। [nb 1] भौतिक वस्तुओं के स्टैक के साथ, यह संरचना किसी भी वस्तु को प्राप्त करने मे आसान बनाती है स्टैक के ऊपर से, लेकिन स्टैक में गहराई तक डेटा को अभिगम्य करने के लिए पहले कई अन्य वस्तुओं को हटाने की आवश्यकता हो सकती है।[1]

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

इतिहास

See also: जन लुकासिविक्ज़ § कार्य

स्टैक ने 1946 में कंप्यूटर विज्ञान साहित्य में प्रवेश किया। जब एलन एम. ट्यूरिंग ने "बरी" और "अनबरी" शब्दों फंक्शन को कॉल करने और सबरूटीन के स्थानांतरण के रूप में उपयोग किया।[2][3] 1945 में कोनराड ज़्यूस के जेड-4 (कंप्यूटर) में सबरूटीन को पहले ही प्रयुक्त कर दिया गया था।

तकनीकी विश्वविद्यालय म्यूनिख के क्लाउस सैमल्सन और फ्रेडरिक एल. बाउर ने 1955 में एक स्टैक के विचार का प्रस्ताव प्रस्तुत किया।[4][5] और 1957 में एक पेटेंट का प्रस्ताव किया।[6][7][8][9] मार्च 1988 में, जिस समय सेमेलसन की मृत्यु हो गई थी बाउर को स्टैक सिद्धांत के आविष्कार के लिए इलेक्ट्रिकल और इलेक्ट्रॉनिक्स इंजीनियरिंग संस्थान (आईईईई) कंप्यूटर पायनियर पुरस्कार मिला।[10][5] इसी प्रकार की अवधारणाओं को स्वतंत्र रूप से 1954 की पहली छमाही में चार्ल्स लियोनार्ड हैम्बलिन द्वारा और 1958 में विल्हेम कैमर [डी] द्वारा विकसित किया गया था।[11][12][13]

स्टैक को प्रायः कैफेटेरिया में प्लेटों के स्प्रिंग-युक्त स्टैक के सादृश्य का उपयोग करके वर्णित किया जाता है।[14][1][15] स्टैक के ऊपर साफ प्लेटें रखी जाती हैं, जो पहले से उपस्थित किसी भी प्लेट को नीचे की ओर प्रेषित करती हैं। जब एक प्लेट को स्टैक से हटा दिया जाता है तो उसके नीचे वाली नई शीर्ष प्लेट बन जाती है।

गैर-आवश्यक संचालन

कई कार्यान्वयनों के स्टैक में आवश्यक "पुश" और "पॉप" संचालन की तुलना में अधिक संचालन होते हैं। एक गैर-आवश्यक संचालन का एक उदाहरण "टॉप ऑफ़ स्टैक" या "पीक" है, जो शीर्ष एलिमेंट को स्टैक से हटाए बिना देखता है।[16] यह एक "पॉप-संचालन" के साथ किया जा सकता है, जिसके बाद एक ही डेटा को स्टैक पर वापस करने के लिए "पुश" किया जाता है, इसलिए इसे एक आवश्यक संचालन नहीं माना जाता है। यदि स्टैक रिक्त है तब "स्टैक टॉप" या "पॉप" संचालन के निष्पादन पर एक अंतर्प्रवाह स्थिति उत्पन्न होगी। इसके अतिरिक्त, स्टैक के रिक्त होने और उसके आकार को वापस करने वाले कार्यान्वयन के लिए कई कार्यान्वयन स्थिति प्रदान करते हैं।

सॉफ्टवेयर स्टैक

कार्यान्वयन

स्टैक को या तो एक ऐरे डेटा संरचना या एक लिंक्ड की गई सूची के माध्यम से आसानी से कार्यान्वित किया जा सकता है, क्योंकि स्टैक केवल सूचियों की एक विशेष स्थिति हैं।[17] किसी भी स्थिति में स्टैक के रूप में डेटा संरचना की पहचान कार्यान्वयन नहीं होती है, लेकिन इंटरफ़ेस उपयोगकर्ता को केवल कुछ अन्य सहायक संचालन के साथ ऐरे या लिंक्ड सूची में डेटा पॉप या पुश करने की स्वीकृति है। निम्नलिखित स्यूडोकोड का उपयोग करते हुए दोनों कार्यान्वयनों को प्रदर्शित किया जाता है।

ऐरे डेटा संरचना

एक (बाध्य) स्टैक को प्रयुक्त करने के लिए एक ऐरे का उपयोग निम्नानुसार किया जा सकता है। पहला एलिमेंट सामान्यतः शून्य ऑफसेट पर नीचे होता है, जिसके परिणामस्वरूप array[0] पहला एलिमेंट स्टैक द्वारा निर्धारित किया जाता है और अंतिम एलिमेंट पॉप हो जाता है। प्रोग्राम को स्टैक के आकार (लंबाई) का नियंत्रण रखना चाहिए, एक वेरिएबल टॉप का उपयोग करके जो अब तक पुश किए गए डेटा की संख्या को रिकॉर्ड करता है, इसलिए ऐरे में उस डेटा की ओर संकेत करता है जहां अगला एलिमेंट को प्रयुक्त किया जाना है शून्य मानते हुए ऐरे पर आधारित सूची को इस प्रकार स्टैक के तीन-एलिमेंट संरचना मे प्रभावी रूप से कार्यान्वित किया जा सकता है: 

structure stack:
 maxsize : integer
 top : integer
 items : array of item

procedure initialize(stk : stack, size : integer):
 stk.items ← new array of size items, initially empty
 stk.maxsize ← size
 stk.top ← 0

ओवरफ्लो के लिए जाँच के बाद, पुश संचालन एक एलिमेंट जोड़ता है और शीर्ष सूचकांक को बढ़ाता है: 

procedure push(stk : stack, x : item):
 if stk.top = stk.maxsize:
  report overflow error
 else:
  stk.items[stk.top] ← x
  stk.top ← stk.top + 1

इसी तरह, पॉप ओवरफ्लो की जाँच के बाद शीर्ष सूचकांक को घटाता है और उस डेटा को वापस करता है जो पहले शीर्ष पर था: 

procedure pop(stk : stack):
 if stk.top = 0:
  report underflow error
 else:
  stk.top ← stk.top − 1
  r ← stk.items[stk.top]
  return r

ऐरे का उपयोग करके एक स्टैक को प्रयुक्त करना संभव होता है जो आवश्यकता अनुसार बढ़ या घट सकता है। स्टैक का आकार केवल स्थैतिक ऐरे का आकार है जो स्टैक का एक बहुत ही कुशल कार्यान्वयन है क्योंकि स्थैतिक एरे के अंत से डेटा को जोड़ने या हटाने के लिए परिशोधित O (1) समय की आवश्यकता होती है।

लिंक्ड सूची

स्टैक को प्रयुक्त करने का एक अन्य विकल्प एकल लिंक्ड सूची का उपयोग करना है। एक स्टैक तब सूची के "शीर्ष" के लिए एक संकेतक होता है जिसमें सूची के आकार का नियंत्रण रखने के लिए एक कॉउंटर-ऐरे होता है: 

structure frame:
 data : item
 next : frame or nil

structure stack:
 head : frame or nil
 size : integer

procedure initialize(stk : stack):
 stk.head ← nil
 stk.size ← 0

पुश और पॉप संचालन डेटा सूची के शीर्ष पर होते हैं, इस कार्यान्वयन में ओवरफ्लो (जब तक कि मेमोरी समाप्त न हो जाए) संभव नहीं होता है: 

procedure push(stk : stack, x : item):
 newhead ← new frame
 newhead.data ← x
 newhead.next ← stk.head
 stk.head ← newhead
 stk.size ← stk.size + 1

procedure pop(stk : stack):
 if stk.head = nil:
  report underflow error
 r ← stk.head.data
 stk.head ← stk.head.next
 stk.size ← stk.size - 1
 return r

स्टैक और प्रोग्रामिंग भाषाएं

पर्ल, लिस्प (प्रोग्रामिंग भाषा), जावास्क्रिप्ट और पायथन जैसी कुछ भाषाएं स्टैक संचालन को उनके मानक सूची/ऐरे डेटाटाइप पर पुश और पॉप संचालन प्रयुक्त कराती हैं। कुछ भाषाएँ, विशेष रूप से फोर्थ (प्रोग्रामिंग भाषा) समूह (परिशिष्ट भाग), भाषा-परिभाषित स्टैक के आसपास डिज़ाइन की गई हैं जो प्रोग्रामर द्वारा प्रत्यक्ष रूप से प्रदर्शित और परिवर्तित की जाती हैं।

सामान्य लिस्प में स्टैक में संशोधन करने का एक उदाहरण निम्नलिखित है (">" लिस्प एंटरप्रेटर का संकेत है ">" से प्रारम्भ नहीं होने वाली पंक्तियाँ अभिव्यक्ति के लिए एंटरप्रेटर प्रोग्राम की प्रतिक्रियाएँ हैं:) 

> (setf stack (list 'a 'b 'c))  ;; set the variable "stack"
(A B C)
> (pop stack)  ;; get top (leftmost) element, should modify the stack
A
> stack        ;; check the value of stack
(B C)
> (push 'new stack)  ;; push a new top onto the stack
(NEW B C)

C++ मानक लाइब्रेरी कंटेनर प्रकारों में से कई में एलआईएफओ शब्दार्थ के साथ push_back और pop_back संचालन होते हैं इसके अतिरिक्त, स्टैक टेम्प्लेट क्लास सम्मिलित कंटेनरों को केवल पुश/पॉप संचालन के साथ प्रतिबंधित एपीआई प्रदान करने के लिए प्रदर्शित करते है। पीएचपी में SplStack क्लास है। जावा की लाइब्रेरी में एक Stack क्लास है जो Vector की विशेषज्ञता है। निम्नलिखित जावा (प्रोग्रामिंग) भाषा में उस वर्ग का उपयोग करते हुए एक उदाहरण प्रोग्राम है। 

import java.util.Stack;

class StackDemo {
    public static void main(String[]args) {
        Stack<String> stack = new Stack<String>();
        stack.push("A");    // Insert "A" in the stack
        stack.push("B");    // Insert "B" in the stack
        stack.push("C");    // Insert "C" in the stack
        stack.push("D");    // Insert "D" in the stack
        System.out.println(stack.peek());    // Prints the top of the stack ("D")
        stack.pop();    // removing the top ("D")
        stack.pop();    // removing the next top ("C")
    }
}

हार्डवेयर स्टैक

Main article: स्टैक-आधारित मेमोरी आवंटन

संरचनात्मक स्तर पर स्टैक का एक सामान्य उपयोग मेमोरी आवंटित करने और एक्सेस करने के साधन के रूप में होता है।

स्टैक की मूल संरचना

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

सभी स्टैक पर प्रयुक्त होने वाले दो संचालन हैं:

  • पुश संचालन, जिसमें स्टैक पॉइंटर द्वारा इंगित स्थान पर एक डेटा रखा जाता है और स्टैक पॉइंटर में एड्रेस डेटा वस्तु के आकार द्वारा समायोजित किया जाता है।
  • पॉप या पुल संचालन: स्टैक पॉइंटर द्वारा इंगित वर्तमान स्थान पर एक डेटा वस्तु को हटा दिया जाता है और स्टैक पॉइंटर को डेटा वस्तु के आकार से समायोजित किया जाता है।

स्टैक संचालन के मूल सिद्धांत पर कई भिन्नताएं हैं। मेमोरी में प्रत्येक स्टैक का एक निश्चित स्थान होता है, जहां से यह प्रारम्भ होता है। जैसे ही स्टैक में डेटा वस्तु को जोड़ा जाता हैं, स्टैक पॉइंटर को स्टैक की वर्तमान सीमा को इंगित करने के लिए विस्थापित किया जाता है जो मूल से दूर विस्तृत होता है।

स्टैक पॉइंटर्स स्टैक की उत्पत्ति या मूल डेटा के ऊपर या नीचे सीमित एड्रेस की ओर संकेत कर सकते हैं (जिस दिशा में स्टैक बढ़ता है उस पर निर्भर करता है) हालाँकि, स्टैक पॉइंटर स्टैक के मूल को स्थगित नहीं कर सकता है। दूसरे शब्दों में, यदि स्टैक का मूल एड्रेस 1000 पर है और स्टैक नीचे की ओर बढ़ता है (एड्रेस 999, 998 और इसी प्रकार), तब स्टैक पॉइंटर को कभी भी 1000 (1001, 1002, आदि) से आगे नहीं बढ़ाना चाहिए। यदि स्टैक पर एक पॉप संचालन स्टैक पॉइंटर को स्टैक के मूल से आगे बढ़ने का कारण बनता है, तो स्टैक अंडरफ़्लो होता है। यदि एक पुश संचालन स्टैक पॉइंटर को स्टैक की अधिकतम सीमा से अधिक बढ़ाने या घटाने का कारण बनता है, तो स्टैक ओवरफ़्लो होता है।

कुछ डेटा जो स्टैक पर बहुत अधिक निर्भर करते हैं, अतिरिक्त संचालन प्रदान कर सकते हैं, उदाहरण के लिए:

  • प्रतिलिपि: शीर्ष वस्तु को पॉप किया जाता है, और फिर (दो बार) प्रेषित किया जाता है, ताकि पूर्व शीर्ष वस्तु की एक अतिरिक्त प्रतिलिपि इसके नीचे मूल डेटा के साथ शीर्ष पर हो।
  • पीक: सबसे ऊपरी वस्तु का निरीक्षण किया जाता है लेकिन स्टैक पॉइंटर और स्टैक का आकार नहीं परिवर्तित होता है जिसका अर्थ है कि वस्तु स्टैक पर रहता है इसे कई लेखों में 'टॉप' संचालन भी कहा जाता है।
  • स्वैप या विनिमय: स्टैक विनिमय स्थानों पर दो सबसे ऊपरी वस्तु।
  • रोटेट या रोल : n शीर्षतम वस्तु स्टैक पर रोटेट फैशन में ले जाए जाते हैं। उदाहरण के लिए, यदि n = 3, स्टैक पर वस्तु 1, 2 और 3 क्रमशः स्टैक पर 2, 3 और 1 की स्थिति में ले जाए जाते हैं। इस संचालन के कई रूप संभव हैं, जिनमें से सबसे सामान्य को "बाए रोटेट" और "दाए रोटेट" कहा जाता है।
  • स्टैक को प्रायः नीचे से ऊपर की ओर बढ़ते हुए देखा जाता है जैसे वास्तविक विश्व के स्टैक जिन्हें बाएँ से दाएँ बढ़ते हुए भी देखा जा सकता है जिससे सबसे ऊपर वाला सबसे दाहिना हो जाता है या यहाँ तक कि ऊपर से नीचे की ओर बढ़ता हुआ भी देखा जा सकता है। महत्वपूर्ण विशेषता यह है कि स्टैक के नीचे एक निश्चित स्थिति में है। इस खंड में उदाहरण ऊपर से नीचे के विकास दृश्य का एक उदाहरण है: शीर्ष (28) स्टैक नीचे है, क्योंकि स्टैक शीर्ष (9) वह स्थान है जहां से वस्तु पुश या पॉप किए जाते हैं। एक दायाँ घुमाव पहले एलिमेंट को तीसरे स्थान पर, दूसरे को पहले और तीसरे को दूसरे स्थान पर ले जाएगा। यहाँ इस प्रक्रिया के दो समकक्ष दृश्य होते हैं:
apple       banana
banana ===right rotate==> cucumber
cucumber      apple

cucumber      apple
banana ===left rotate==> cucumber
apple       banana

एक स्टैक को सामान्यतः कंप्यूटर में मेमोरी सेल के एक ब्लॉक द्वारा दर्शाया जाता है, जिसमें नीचे एक निश्चित स्थान पर होता है और स्टैक में वर्तमान शीर्ष सेल का एड्रेस रखने वाला स्टैक पॉइंटर होता है। ऊपर और नीचे की शब्दावली का उपयोग इस बात पर ध्यान दिए बिना किया जाता है कि स्टैक वास्तव में कम मेमोरी एड्रेसों की ओर बढ़ता है या उच्च मेमोरी एड्रेसों की ओर बढ़ता है।

किसी वस्तु को स्टैक पर प्रयुक्त करने से स्टैक पॉइंटर को वस्तु के आकार के अनुसार समायोजित किया जाता है या तो कमी या वृद्धि, उस दिशा के आधार पर जिस दिशा में स्टैक मेमोरी में बढ़ती है इसे अगले सेल पर इंगित करता है और नए शीर्ष वस्तु को स्टैक करता है प्रयुक्त कार्यान्वयन के आधार पर, एक पुश संचालन के अंत में, स्टैक पॉइंटर स्टैक में अगले अप्रयुक्त स्थान को इंगित कर सकता है या यह स्टैक में सबसे ऊपरी वस्तु को इंगित कर सकता है। यदि स्टैक वर्तमान शीर्षतम वस्तु की ओर संकेत करता है, तो स्टैक पॉइंटर को स्टैक पर एक नए वस्तु को प्रयुक्त करने से पहले अपडेट किया जाता है। यदि यह स्टैक में अगले उपलब्ध स्थान की ओर संकेत करता है, तो नए वस्तु को स्टैक पर प्रयुक्त करने के बाद इसे अपडेट किया जाता है।

स्टैक को पॉप करना केवल पुश करने का विलोम है। स्टैक में सबसे ऊपरी वस्तु को हटा दिया जाता है और स्टैक पॉइंटर को पुश संचालन में उपयोग किए गए विपरीत क्रम में अपडेट किया जाता है।

मुख्य मेमोरी में स्टैक

कई सीआईएससी-प्रकार के सेंट्रल प्रोसेसिंग यूनिट (सीपीयू) डिज़ाइन जिनमें एक्स-86, जेड-80 और 6502 सम्मिलित हैं सीआईएससी मे कॉल, रिटर्न, पुश और पॉप निर्देशों के साथ कॉल स्टैक स्टैक पॉइंटर के रूप में उपयोग के लिए एक समर्पित रजिस्टर होता है जो समर्पित रजिस्टर को स्पष्ट रूप से अपडेट करता है इस प्रकार कोड घनत्व में वृद्धि करता है। कुछ सीआईएससी प्रोसेसर, जैसे पीडीपी-11 और 68000, में स्टैक के कार्यान्वयन के लिए विशेष एड्रेसिंग मोड भी होते हैं सामान्यतः अर्ध-समर्पित स्टैक पॉइंटर के साथ (जैसे 68000 में ए-7) इसके विपरीत, अधिकांश आरआईएससी सीपीयू डिजाइनों में समर्पित स्टैक निर्देश नहीं होते हैं और इसलिए अधिकांश, यदि सभी नहीं, रजिस्टरों को आवश्यकता अनुसार स्टैक पॉइंटर्स के रूप में उपयोग किया जा सकता है।

रजिस्टरों या समर्पित मेमोरी में स्टैक

Main article: स्टैक मशीन

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

कई मेनफ्रेम कंप्यूटर और मिनी कंप्यूटर स्टैक मशीन थे जिनमें सबसे प्रसिद्ध बरोज़ लार्ज सिस्टम्स था अन्य उदाहरणों में सीआईएससी एचपी-3000 मशीनें और टैंडेम कंप्यूटर की सीआईएससी मशीनें सम्मिलित हैं।

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

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

सन स्पार्क, एएमडी एम-29000 और इंटेल आई-960 सभी सीपीयू संरचना के उदाहरण हैं जो रजिस्टर-स्टैक के अंदर रजिस्टर विंडो का उपयोग करते हुए एक अन्य प्रक्रिया के रूप में प्रोग्राम तर्कों और वापसी मान के लिए मुख्य मेमोरी का उपयोग करते हैं।

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

स्टैक के अनुप्रयोग

अभिव्यक्ति मूल्यांकन और सिंटैक्स निरूपण

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

बैकट्रैकिंग

Main article: बैक ट्रैकिंग

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

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

संकलन-समय स्मृति प्रबंधन

Main articles: स्टैक-आधारित मेमोरी आवंटन and स्टैक मशीन
एक विशिष्ट कॉल स्टैक, प्रक्रिया कॉल के कई स्तरों के लिए स्थानीय डेटा और कॉल जानकारी संग्रहीत करता है। यह स्टैक अपने मूल स्थान से नीचे की ओर बढ़ता है। स्टैक पॉइंटर स्टैक पर वर्तमान सबसे ऊपरी डेटा को इंगित करता है। एक पुश संचालन पॉइंटर को घटाता है और डेटा को स्टैक पर कॉपी करता है; एक पॉप संचालन स्टैक से डेटा कॉपी करता है और फिर पॉइंटर को बढ़ाता है। प्रोग्राम में बुलाई जाने वाली प्रत्येक प्रक्रिया स्टैक पर पुश करके प्रक्रिया वापसी जानकारी (पीले रंग में) और स्थानीय डेटा (अन्य रंगों में) को संग्रहीत करती है। इस प्रकार का स्टैक कार्यान्वयन अत्यंत सामान्य है, लेकिन यह बफ़र अधिकता अटैक (पाठ देखें) के प्रति संवेदनशील है।

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

लगभग सभी कॉलिंग फंक्शन—जिस प्रकार से सबरूटीन्स अपने पैरामीटर प्राप्त करते हैं और परिणाम वापस करते हैं—एक विशेष स्टैक "कॉल स्टैक" का उपयोग प्रक्रिया/फंक्शन कॉलिंग और नेस्टिंग के विषय में जानकारी रखने के लिए किया जाता है ताकि कॉल किए गए फ़ंक्शन के संदर्भ में स्विच किया जा सके और कॉलिंग समाप्त होने पर कॉलर फ़ंक्शन को पुनर्स्थापित किया जा सके। तर्कों को सुरक्षित करने और स्टैक पर मान वापस करने के लिए फ़ंक्शन कॉल करने वाले और कैली के बीच एक रनटाइम प्रोटोकॉल का अनुसरण करते हैं। स्टैक नेस्टेड या प्रत्यावर्तन फ़ंक्शन कॉल का समर्थन करने का एक महत्वपूर्ण तरीका है। इस प्रकार के स्टैक का उपयोग कंपाइलर द्वारा CALL और RETURN स्टेटमेंट्स या उनके समकक्ष होने का समर्थन करने के लिए किया जाता है और इसमे प्रोग्रामर द्वारा प्रत्यक्ष रूप से परिवर्तन नहीं किया जाता है।

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

सक्षम एल्गोरिदम

कई एल्गोरिदम मुख्य डेटा संरचना के रूप में एक स्टैक (अधिकांश प्रोग्रामिंग भाषाओं के सामान्य फ़ंक्शन कॉल स्टैक से अलग) का उपयोग करते हैं जिसके साथ वे अपनी जानकारी सम्मिलित करते हैं। जो निम्नलिखित सम्मिलित है:

  • ग्राहम स्कैन, बिंदुओं की द्वि-आयामी प्रणाली के बिंदुओं के लिए एक एल्गोरिथ्म इनपुट के एक उपसमुच्चय का एक उत्तल हल स्टैक में रखा जाता है, जिसका उपयोग फेट एल्गोरिदम में एक नया बिंदु जोड़ने पर सीमा में अवतलता को खोजने और हटाने के लिए किया जाता है।[18]
  • मोनोटोन आव्यूह की पंक्ति मे निम्न मान को खोजने के लिए स्मॉक एल्गोरिथ्म का भाग ग्रैहम स्कैन के समान तरीके से स्टैक का उपयोग करता है।[19]
  • सभी निकटतम छोटे मान, खोजने की समस्या, किसी सरणी में प्रत्येक संख्या के लिए, निकटतम पूर्ववर्ती संख्या जो उससे छोटी है। इस समस्या के लिए एक एल्गोरिदम निकटतम छोटे मान के लिए उम्मीदवारों के संग्रह को बनाए रखने के लिए स्टैक का उपयोग करता है। सरणी में प्रत्येक स्थिति के लिए, स्टैक को तब तक पॉप किया जाता है जब तक कि उसके शीर्ष पर एक छोटा मान नहीं प्राप्त हो जाता है और फिर नई स्थिति में मान को स्टैक पर प्रयुक्त किया जाता है।[20]
  • निकटतम श्रृंखला एल्गोरिथ्म, समूहों के स्टैक को बनाए रखने के आधार पर एग्लोमेरेटिव पदानुक्रमित एल्गोरिदम के लिए एक विधि, जिनमें से प्रत्येक स्टैक पर अपने पूर्ववर्ती का निकटतम मान है। जब इस पद्धति को ऐसे समूहों की एक जोड़ी प्राप्त होती है तब वे परस्पर निकटतम श्रृंखला मे पॉप कर दिए जाते हैं।[21]

सुरक्षा

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

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

इस प्रकार का अटैक बफर ओवरफ्लो अटैक पर एक भिन्नता है और सॉफ्टवेयर में सुरक्षा उल्लंघनों का एक बहुत बड़ा स्रोत है क्योंकि सबसे लोकप्रिय कंपाइलर डेटा और प्रक्रिया कॉल दोनों के लिए एक साझा स्टैक का उपयोग किया हैं जो इसकी लंबाई को सत्यापित नहीं करते हैं। डेटा वस्तु प्रायः प्रोग्रामर डेटा वस्तु के आकार को सत्यापित करने के लिए कोड नहीं लिखते हैं और जब ये एक बड़े या छोटे डेटा वस्तु के स्टैक पर प्रयोग किया जाते है, तो इससे सुरक्षा मे विभिन्न अंतः क्षेप हो सकते है।

यह भी देखें

टिप्पणियाँ

  1. ↑ By contrast, a queue operates first in, first out, referred to by the acronym FIFO.


संदर्भ

  1. ↑ Jump up to: 1.0 1.1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 232–233. ISBN 0-262-03384-4.
  2. ↑ Turing, Alan Mathison (1946-03-19) [1945]. Proposals for Development in the Mathematics Division of an Automatic Computing Engine (ACE). (NB. Presented on 1946-03-19 before the Executive Committee of the National Physical Laboratory (Great Britain).)
  3. ↑ Carpenter, Brian Edward; Doran, Robert William (1977-01-01) [October 1975]. "The other Turing machine". The Computer Journal. 20 (3): 269–279. doi:10.1093/comjnl/20.3.269. (11 pages)
  4. ↑ Samelson, Klaus (1957) [1955]. Written at Internationales Kolloquium über Probleme der Rechentechnik, Dresden, Germany. Probleme der Programmierungstechnik (in Deutsch). Berlin, Germany: VEB Deutscher Verlag der Wissenschaften. pp. 61–68. (NB. This paper was first presented in 1955. It describes a number stack (Zahlenkeller), but names it linear auxiliary memory (linearer Hilfsspeicher).)
  5. ↑ Jump up to: 5.0 5.1 Fothe, Michael; Wilke, Thomas, eds. (2015) [2014-11-14]. Written at Jena, Germany. Keller, Stack und automatisches Gedächtnis – eine Struktur mit Potenzial [Cellar, stack and automatic memory - a structure with potential] (PDF) (Tagungsband zum Kolloquium 14. November 2014 in Jena). GI Series: Lecture Notes in Informatics (LNI) – Thematics (in Deutsch). Vol. T-7. Bonn, Germany: Gesellschaft für Informatik (GI) / Köllen Druck + Verlag GmbH. ISBN 978-3-88579-426-4. ISSN 1614-3213. Archived (PDF) from the original on 2020-04-12. Retrieved 2020-04-12. [1] (77 pages)
  6. ↑ Bauer, Friedrich Ludwig; Samelson, Klaus (1957-03-30). "Verfahren zur automatischen Verarbeitung von kodierten Daten und Rechenmaschine zur Ausübung des Verfahrens" (in Deutsch). Munich, Germany: Deutsches Patentamt. DE-PS 1094019. Retrieved 2010-10-01.
  7. ↑ Bauer, Friedrich Ludwig; Goos, Gerhard [in Deutsch] (1982). Informatik – Eine einführende Übersicht (in Deutsch). Vol. Part 1 (3 ed.). Berlin: Springer-Verlag. p. 222. ISBN 3-540-11722-9. Die Bezeichnung 'Keller' hierfür wurde von Bauer und Samelson in einer deutschen Patentanmeldung vom 30. März 1957 eingeführt.
  8. ↑ Samelson, Klaus; Bauer, Friedrich Ludwig (1959). "Sequentielle Formelübersetzung" [Sequential Formula Translation]. Elektronische Rechenanlagen (in Deutsch). 1 (4): 176–182.
  9. ↑ Samelson, Klaus; Bauer, Friedrich Ludwig (1960). "Sequential Formula Translation". Communications of the ACM. 3 (2): 76–83. doi:10.1145/366959.366968. S2CID 16646147.
  10. ↑ "IEEE-Computer-Pioneer-Preis – Bauer, Friedrich L." Technical University of Munich, Faculty of Computer Science. 1989-01-01. Archived from the original on 2017-11-07.
  11. ↑ Hamblin, Charles Leonard (May 1957). An Addressless Coding Scheme based on Mathematical Notation (PDF) (typescript). N.S.W. University of Technology. pp. 121-1–121-12. Archived (PDF) from the original on 2020-04-12. Retrieved 2020-04-12. (12 pages)
  12. ↑ Kämmerer, Wilhelm [in Deutsch] (1958). Ziffern-Rechenautomat mit Programmierung nach mathematischem Formelbild (Habilitation thesis) (in Deutsch). Friedrich-Schiller-Universität, Jena, Germany.
  13. ↑ Kämmerer, Wilhelm [in Deutsch] (1960). Ziffernrechenautomaten. {{cite book}}: |work= ignored (help)
  14. ↑ Ball, John A. (1978). Algorithms for RPN calculators (1 ed.). Cambridge, Massachusetts, USA: Wiley-Interscience, John Wiley & Sons, Inc. ISBN 978-0-471-03070-6.
  15. ↑ Godse, Atul P.; Godse, Deepali A. (2010-01-01). Computer Architecture. Technical Publications. pp. 1–56. ISBN 978-8-18431534-9. Retrieved 2015-01-30.
  16. ↑ Horowitz, Ellis (1984). Fundamentals of Data Structures in Pascal. Computer Science Press. p. 67.
  17. ↑ Pandey, Shreesham (2020-06-07). "Data Structures in a Nutshell" (in English). Rochester, New York, USA. SSRN 4145204. Archived from the original on 2022-11-12. Retrieved 2022-11-27. {{cite journal}}: Cite journal requires |journal= (help); |archive-date= / |archive-url= timestamp mismatch (help)
  18. ↑ Graham, Ronald "Ron" Lewis (1972). An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set (PDF). Information Processing Letters 1. Vol. 1. pp. 132–133. Archived (PDF) from the original on 2022-10-22.
  19. ↑ Aggarwal, Alok; Klawe, Maria M.; Moran, Shlomo; Shor, Peter; Wilber, Robert (1987). "Geometric applications of a matrix-searching algorithm". Algorithmica. 2 (1–4): 195–208. doi:10.1007/BF01840359. MR 0895444. S2CID 7932878..
  20. ↑ Berkman, Omer; Schieber, Baruch; Vishkin, Uzi (1993). "Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values". Journal of Algorithms. 14 (3): 344–370. CiteSeerX 10.1.1.55.5669. doi:10.1006/jagm.1993.1018..
  21. ↑ Murtagh, Fionn (1983). "A survey of recent advances in hierarchical clustering algorithms" (PDF). The Computer Journal. 26 (4): 354–359. doi:10.1093/comjnl/26.4.354..


अग्रिम पठन


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=स्टैक_(अमूर्त_डेटाटाइप)&oldid=254603’