स्टैक (अमूर्त डेटाटाइप)
कंप्यूटर विज्ञान में, स्टैक एक अमूर्त डेटा प्रकार है जो तत्वों के संग्रह (सार डेटा प्रकार) के रूप में कार्य करता है, जिसमें दो मुख्य ऑपरेशन होते हैं:
- पुश, जो संग्रह में एक तत्व जोड़ता है, और
- पॉप, जो हाल ही में जोड़े गए तत्व को हटा देता है जिसे अभी तक हटाया नहीं गया था।
इसके अतिरिक्त, एक पीक ऑपरेशन, स्टैक को संशोधित किए बिना, जोड़े गए अंतिम तत्व का मान वापस कर सकता है। इस संरचना को एक स्टैक कहना भौतिक वस्तुओं के एक सेट के अनुरूप है, जो प्लेटों के स्टैक जैसे एक दूसरे के ऊपर खड़ी होती है।
जिस क्रम में एक स्टैक से एक तत्व जोड़ा या हटाया जाता है, उसे एलआईएफओ द्वारा संदर्भित अंतिम, पहले आउट के रूप में वर्णित किया जाता है। [nb 1] भौतिक वस्तुओं के स्टैक के साथ, यह संरचना किसी आइटम को लेना आसान बनाती है स्टैक के ऊपर से, लेकिन स्टैक में गहराई तक डेटा तक पहुँचने के लिए पहले कई अन्य वस्तुओं को हटाने की आवश्यकता हो सकती है।[1]
एक रेखीय डेटा संरचना, या अधिक संक्षेप में एक अनुक्रमिक संग्रह के रूप में माना जाता है, पुश और पॉप संचालन संरचना के केवल एक छोर पर होता है, जिसे स्टैक के शीर्ष के रूप में संदर्भित किया जाता है। यह डेटा संरचना स्टैक को एकल लिंक्ड सूची के रूप में और शीर्ष तत्व के सूचक के रूप में प्रयुक्त करना संभव बनाती है। एक सीमित क्षमता रखने के लिए एक स्टैक प्रयुक्त किया जा सकता है। यदि स्टैक भरा हुआ है और किसी अन्य तत्व को स्वीकार करने के लिए पर्याप्त स्थान नहीं है, तो स्टैक ओवरफ़्लो की स्थिति में है।
गहराई-पहली खोज को प्रयुक्त करने के लिए स्टैक की आवश्यकता होती है।
इतिहास
स्टैक ने 1946 में कंप्यूटर विज्ञान साहित्य में प्रवेश किया, जब एलन एम. ट्यूरिंग ने "बरी" और "अनबरी" शब्दों का इस्तेमाल कॉल करने और उपनेमकाओं से लौटने के साधन के रूप में किया।[2][3]1945 में कोनराड ज़्यूस के Z4 (कंप्यूटर) में सबरूटीन को पहले ही प्रयुक्त कर दिया गया था।
तकनीकी विश्वविद्यालय म्यूनिख के क्लाउस सैमल्सन और फ्रेडरिक एल. बाउर ने 1955 में एक स्टैक के विचार का प्रस्ताव रखा[4][5] और 1957 में एक पेटेंट दायर किया।[6][7][8][9] मार्च 1988 में, जिस समय सेमेलसन की मृत्यु हो गई थी, बाउर को स्टैक सिद्धांत के आविष्कार के लिए IEEE कंप्यूटर पायनियर अवार्ड मिला।[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 LIFO शब्दार्थ के साथ संचालन; इसके अतिरिक्त, stack टेम्प्लेट क्लास मौजूदा कंटेनरों को केवल पुश/पॉप ऑपरेशंस के साथ प्रतिबंधित एपीआई प्रदान करने के लिए अनुकूलित करता है। पीएचपी में 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")
}
}
हार्डवेयर स्टैक
आर्किटेक्चर स्तर पर स्टैक का एक सामान्य उपयोग मेमोरी आवंटित करने और एक्सेस करने के साधन के रूप में होता है।
एक स्टैक की बुनियादी वास्तुकला
एक विशिष्ट स्टैक कंप्यूटर मेमोरी का एक निश्चित मूल और एक चर आकार वाला क्षेत्र है। प्रारंभ में स्टैक का आकार शून्य है। एक स्टैक पॉइंटर, सामान्यतः एक हार्डवेयर रजिस्टर के रूप में, स्टैक पर हाल ही में संदर्भित स्थान को इंगित करता है; जब स्टैक का आकार शून्य होता है, तो स्टैक पॉइंटर स्टैक की उत्पत्ति की ओर इशारा करता है।
सभी स्टैक पर प्रयुक्त होने वाले दो ऑपरेशन हैं:
- एक पुश ऑपरेशन, जिसमें स्टैक पॉइंटर द्वारा इंगित स्थान पर एक डेटा आइटम रखा जाता है, और स्टैक पॉइंटर में पता डेटा आइटम के आकार द्वारा समायोजित किया जाता है;
- एक पॉप या पुल ऑपरेशन: स्टैक पॉइंटर द्वारा इंगित वर्तमान स्थान पर एक डेटा आइटम हटा दिया जाता है, और स्टैक पॉइंटर को डेटा आइटम के आकार से समायोजित किया जाता है।
स्टैक ऑपरेशंस के मूल सिद्धांत पर कई भिन्नताएं हैं। मेमोरी में प्रत्येक स्टैक का एक निश्चित स्थान होता है, जहां से यह शुरू होता है। जैसे ही स्टैक में डेटा आइटम जोड़े जाते हैं, स्टैक पॉइंटर को स्टैक की वर्तमान सीमा को इंगित करने के लिए विस्थापित किया जाता है, जो मूल से दूर फैलता है।
स्टैक पॉइंटर्स स्टैक की उत्पत्ति या मूल के ऊपर या नीचे सीमित पतों की ओर इशारा कर सकते हैं (जिस दिशा में स्टैक बढ़ता है उस पर निर्भर करता है); हालाँकि, स्टैक पॉइंटर स्टैक के मूल को पार नहीं कर सकता है। दूसरे शब्दों में, यदि स्टैक का मूल पता 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
एक स्टैक को सामान्यतः कंप्यूटर में मेमोरी सेल के एक ब्लॉक द्वारा दर्शाया जाता है, जिसमें नीचे एक निश्चित स्थान पर होता है, और स्टैक में वर्तमान शीर्ष सेल का पता रखने वाला स्टैक पॉइंटर होता है। ऊपर और नीचे की शब्दावली का उपयोग इस बात पर ध्यान दिए बिना किया जाता है कि स्टैक वास्तव में कम मेमोरी पतों की ओर बढ़ता है या उच्च मेमोरी पतों की ओर।
किसी आइटम को स्टैक पर धकेलने से स्टैक पॉइंटर को आइटम के आकार के अनुसार समायोजित किया जाता है (या तो कमी या वृद्धि, उस दिशा के आधार पर जिस दिशा में स्टैक मेमोरी में बढ़ता है), इसे अगले सेल पर इंगित करता है, और नए शीर्ष आइटम को कॉपी करता है स्टैक क्षेत्र। सटीक कार्यान्वयन के आधार पर, एक पुश ऑपरेशन के अंत में, स्टैक पॉइंटर स्टैक में अगले अप्रयुक्त स्थान को इंगित कर सकता है, या यह स्टैक में सबसे ऊपरी आइटम को इंगित कर सकता है। यदि स्टैक वर्तमान शीर्षतम आइटम की ओर इशारा करता है, तो स्टैक पॉइंटर को स्टैक पर एक नए आइटम को धकेलने से पहले अपडेट किया जाएगा; यदि यह स्टैक में अगले उपलब्ध स्थान की ओर इशारा करता है, तो नए आइटम को स्टैक पर धकेलने के बाद इसे अपडेट किया जाएगा।
स्टैक को पॉप करना केवल पुश करने का विलोम है। स्टैक में सबसे ऊपरी आइटम को हटा दिया जाता है और स्टैक पॉइंटर को पुश ऑपरेशन में उपयोग किए गए विपरीत क्रम में अपडेट किया जाता है।
मुख्य स्मृति में स्टैक
कई सीआईएससी-प्रकार के सेंट्रल प्रोसेसिंग यूनिट (सीपीयू) डिज़ाइन, जिनमें x86, Z80 और 6502 सम्मिलित हैं, में समर्पित कॉल, रिटर्न, पुश और पॉप निर्देशों के साथ कॉल स्टैक स्टैक पॉइंटर के रूप में उपयोग के लिए एक समर्पित रजिस्टर है, जो समर्पित रजिस्टर को स्पष्ट रूप से अपडेट करता है, इस प्रकार कोड घनत्व में वृद्धि करता है। कुछ सीआईएससी प्रोसेसर, जैसे पीडीपी-11 और 68000, में स्टैक के कार्यान्वयन के लिए विशेष एड्रेसिंग मोड भी होते हैं, सामान्यतः अर्ध-समर्पित स्टैक पॉइंटर के साथ (जैसे 68000 में A7)। इसके विपरीत, अधिकांश आरआईएससी सीपीयू डिजाइनों में समर्पित स्टैक निर्देश नहीं होते हैं और इसलिए अधिकांश, यदि सभी नहीं, रजिस्टरों को आवश्यकतानुसार स्टैक पॉइंटर्स के रूप में उपयोग किया जा सकता है।
रजिस्टरों या समर्पित स्मृति में स्टैक
कुछ मशीनें अंकगणित और तार्किक संक्रियाओं के लिए स्टैक का उपयोग करती हैं; ऑपरेंड को स्टैक पर धकेल दिया जाता है, और अंकगणित और तार्किक संचालन स्टैक पर शीर्ष एक या एक से अधिक आइटम पर कार्य करते हैं, उन्हें स्टैक से पॉपिंग करते हैं और परिणाम को स्टैक पर धकेलते हैं। इस तरह से काम करने वाली मशीनों को स्टैक मशीन कहा जाता है।
कई मेनफ्रेम और मिनी कंप्यूटर स्टैक मशीन थे, जिनमें सबसे प्रसिद्ध बरोज़ लार्ज सिस्टम्स थे। अन्य उदाहरणों में सीआईएससी एचपी-3000 मशीनें और Tandem कंप्यूटर्स की सीआईएससी मशीनें सम्मिलित हैं।
x87 तैरनेवाला स्थल आर्किटेक्चर स्टैक के रूप में व्यवस्थित रजिस्टरों के एक सेट का एक उदाहरण है जहां व्यक्तिगत रजिस्टरों (वर्तमान शीर्ष के सापेक्ष) तक सीधी पहुंच भी संभव है।
एक अंतर्निहित तर्क के रूप में टॉप-ऑफ-स्टैक होने से बस (कंप्यूटिंग) बैंडविड्थ (कंप्यूटिंग) और कैश मैमोरी के अच्छे उपयोग के साथ एक छोटे मशीन कोड पदचिह्न की स्वीकृति मिलती है, लेकिन यह प्रोसेसर पर कुछ प्रकार के अनुकूलन को भी रोकता है जो सभी के लिए रजिस्टर फ़ाइल में यादृच्छिक पहुंच की स्वीकृति देता है (दो या तीन) ऑपरेंड एक स्टैक संरचना सुपरस्क्लेर कार्यान्वयन को रजिस्टर नाम बदलने (सट्टा निष्पादन के लिए) के साथ प्रयुक्त करने के लिए कुछ अधिक जटिल बनाती है, हालांकि यह अभी भी संभव है, जैसा कि आधुनिक x87 कार्यान्वयन द्वारा उदाहरण दिया गया है।
सन स्पार्क, एएमडी एम-29000, और इंटेल आई-960 सभी आर्किटेक्चर के उदाहरण हैं जो रजिस्टर-स्टैक के भीतर रजिस्टर विंडो का उपयोग करते हुए एक अन्य रणनीति के रूप में कार्य तर्कों और वापसी मूल्यों के लिए धीमी मुख्य मेमोरी के उपयोग से बचने के लिए हैं।
ऐसे कई छोटे माइक्रोप्रोसेसर भी हैं जो स्टैक को सीधे हार्डवेयर में प्रयुक्त करते हैं और कुछ माइक्रोकंट्रोलर्स के पास एक निश्चित-गहराई वाला स्टैक होता है जो सीधे पहुंच योग्य नहीं होता है। उदाहरण हैं पीआईसीमाइक्रोकंट्रोलर, कंप्यूटर काउबॉय एमयूपी-21, हैरिस आरटीएक्स लाइन, और नोविक्स एनसी 4016 कई स्टैक-आधारित माइक्रोप्रोसेसरों का उपयोग प्रोग्रामिंग भाषा फोर्थ को माइक्रोकोड स्तर पर प्रयुक्त करने के लिए किया गया था।
स्टैक के अनुप्रयोग
अभिव्यक्ति मूल्यांकन और सिंटैक्स पार्सिंग
रिवर्स पोलिश नोटेशन का उपयोग करने वाले कैलकुलेटर मान रखने के लिए स्टैक संरचना का उपयोग करते हैं। अभिव्यक्तियों को उपसर्ग, पोस्टफिक्स या इन्फिक्स नोटेशन में प्रदर्शित किया जा सकता है और स्टैक का उपयोग करके एक रूप से दूसरे रूप में रूपांतरण पूरा किया जा सकता है। कई कंपाइलर निम्न-स्तरीय कोड में अनुवाद करने से पहले एक्सप्रेशन, प्रोग्राम ब्लॉक आदि के सिंटैक्स को पार्स करने के लिए स्टैक का उपयोग करते हैं। अधिकांश प्रोग्रामिंग भाषाएँ संदर्भ-मुक्त भाषाएँ हैं, जो उन्हें स्टैक-आधारित मशीनों के साथ पार्स करने की स्वीकृति देती हैं।
बैकट्रैकिंग
स्टैक का एक अन्य महत्वपूर्ण अनुप्रयोग बैकट्रैकिंग है। भूलभुलैया में सही रास्ता खोजने का एक सरल उदाहरण पर विचार करें। शुरुआती बिंदु से गंतव्य तक बिंदुओं की एक श्रृंखला होती है। हम एक बिंदु से शुरू करते हैं। अंतिम मंजिल तक पहुँचने के लिए कई रास्ते हैं। मान लीजिए हम एक यादृच्छिक मार्ग चुनते हैं। एक निश्चित रास्ते पर चलने के बाद हमें एहसास होता है कि हमने जो रास्ता चुना है वह गलत है। इसलिए हमें एक ऐसा रास्ता खोजने की जरूरत है जिससे हम उस रास्ते की शुरुआत में लौट सकें। यह स्टैक के उपयोग से किया जा सकता है। स्टैक्स की मदद से हम उस बिंदु को याद करते हैं जहां हम पहुंचे हैं। यह उस बिंदु को स्टैक में धकेल कर किया जाता है। यदि हम गलत रास्ते पर समाप्त हो जाते हैं, तो हम स्टैक से अंतिम बिंदु को पॉप कर सकते हैं और इस प्रकार अंतिम बिंदु पर लौट सकते हैं और सही रास्ता खोजने के लिए अपनी खोज जारी रख सकते हैं। इसे बैकट्रैकिंग कहा जाता है।
बैकट्रैकिंग एल्गोरिथम का प्रोटोटाइपिकल उदाहरण डेप्थ-फर्स्ट सर्च है, जो एक ग्राफ के सभी शीर्षों को ढूंढता है, जिस पर एक निर्दिष्ट प्रारंभिक शीर्ष से पहुंचा जा सकता है। बैकट्रैकिंग के अन्य अनुप्रयोगों में रिक्त स्थान के माध्यम से खोज करना सम्मिलित है जो अनुकूलन समस्या के संभावित समाधान का प्रतिनिधित्व करता है। शाखा और बाउंड ऐसी जगह में सभी संभावित समाधानों को पूरी तरह से खोजे बिना ऐसी बैकट्रैकिंग खोजों को करने के लिए एक तकनीक है।
संकलन-समय स्मृति प्रबंधन
कई प्रोग्रामिंग भाषा स्टैक-उन्मुख प्रोग्रामिंग भाषा हैं, जिसका अर्थ है कि वे स्टैक से अपने तर्कों को लेने और स्टैक पर किसी भी रिटर्न वैल्यू को वापस रखने के रूप में सबसे बुनियादी संचालन (दो नंबर जोड़ना, एक वर्ण को प्रिंट करना) को परिभाषित करते हैं। उदाहरण के लिए, पोस्टस्क्रिप्ट में एक रिटर्न स्टैक और एक ऑपरेंड स्टैक होता है, और एक ग्राफिक्स स्टेट स्टैक और एक डिक्शनरी स्टैक भी होता है। कई वर्चुअल मशीन स्टैक-ओरिएंटेड भी हैं, जिनमें पी-कोड मशीन और जावा वर्चुअल मशीन सम्मिलित हैं।
लगभग सभी कॉलिंग कन्वेंशन—जिस तरह से सबरूटीन्स अपने पैरामीटर प्राप्त करते हैं और परिणाम लौटाते हैं—एक विशेष स्टैक ("कॉल स्टैक") का उपयोग प्रक्रिया/फंक्शन कॉलिंग और नेस्टिंग के बारे में जानकारी रखने के लिए किया जाता है ताकि कॉल किए गए फ़ंक्शन के संदर्भ में स्विच किया जा सके और कॉलिंग समाप्त होने पर कॉलर फ़ंक्शन को पुनर्स्थापित करें। तर्कों को बचाने और स्टैक पर मूल्य वापस करने के लिए फ़ंक्शन कॉल करने वाले और कैली के बीच एक रनटाइम प्रोटोकॉल का पालन करते हैं। स्टैक नेस्टेड या प्रत्यावर्तन फ़ंक्शन कॉल का समर्थन करने का एक महत्वपूर्ण तरीका है। इस प्रकार के स्टैक का उपयोग कंपाइलर द्वारा CALL और RETURN स्टेटमेंट्स (या उनके समकक्ष) का समर्थन करने के लिए किया जाता है और प्रोग्रामर द्वारा सीधे हेरफेर नहीं किया जाता है।
कुछ प्रोग्रामिंग लैंग्वेज डेटा को स्टोर करने के लिए स्टैक का उपयोग करती हैं जो एक प्रक्रिया के लिए स्थानीय है। प्रक्रिया दर्ज होने पर स्थानीय डेटा आइटम के लिए स्थान स्टैक से आवंटित किया जाता है, और जब प्रक्रिया समाप्त हो जाती है तो इसे हटा दिया जाता है। सी प्रोग्रामिंग भाषा सामान्यतः इस तरह से प्रयुक्त की जाती है। डेटा और प्रक्रिया कॉल दोनों के लिए एक ही स्टैक का उपयोग करने के महत्वपूर्ण सुरक्षा निहितार्थ हैं (नीचे देखें) जिनमें से एक प्रोग्राम में गंभीर सुरक्षा बगों को पेश करने से बचने के लिए एक प्रोग्रामर को जागरूक होना चाहिए।
कुशल एल्गोरिदम
कई एल्गोरिदम मुख्य डेटा संरचना के रूप में एक स्टैक (अधिकांश प्रोग्रामिंग भाषाओं के सामान्य फ़ंक्शन कॉल स्टैक से अलग) का उपयोग करते हैं जिसके साथ वे अपनी जानकारी व्यवस्थित करते हैं। इसमे सम्मिलित है:
- ग्राहम स्कैन, बिंदुओं की द्वि-आयामी प्रणाली के उत्तल पतवार के लिए एक एल्गोरिथ्म इनपुट के एक उपसमुच्चय का एक उत्तल हल स्टैक में रखा जाता है, जिसका उपयोग पतवार में एक नया बिंदु जोड़ने पर सीमा में अवतलता को खोजने और हटाने के लिए किया जाता है।[18]
- मोनोटोन मैट्रिक्स की पंक्ति मिनिमा को खोजने के लिए स्मॉक एल्गोरिथ्म का हिस्सा ग्रैहम स्कैन के समान तरीके से स्टैक का उपयोग करता है।[19]
- सभी निकटतम छोटे मान, खोजने की समस्या, किसी सरणी में प्रत्येक संख्या के लिए, निकटतम पूर्ववर्ती संख्या जो उससे छोटी है। इस समस्या के लिए एक एल्गोरिदम निकटतम छोटे मान के लिए उम्मीदवारों के संग्रह को बनाए रखने के लिए स्टैक का उपयोग करता है। सरणी में प्रत्येक स्थिति के लिए, स्टैक को तब तक पॉप किया जाता है जब तक कि उसके शीर्ष पर एक छोटा मान नहीं मिल जाता है, और फिर नई स्थिति में मान को स्टैक पर धकेल दिया जाता है।[20]
- निकटतम-पड़ोसी श्रृंखला एल्गोरिथ्म, समूहों के स्टैक को बनाए रखने के आधार पर एग्लोमेरेटिव पदानुक्रमित क्लस्टरिंग के लिए एक विधि, जिनमें से प्रत्येक स्टैक पर अपने पूर्ववर्ती का निकटतम पड़ोसी है। जब इस पद्धति को ऐसे समूहों की एक जोड़ी मिलती है जो परस्पर निकटतम पड़ोसी हैं, तो वे पॉपअप और विलय कर दिए जाते हैं।[21]
सुरक्षा
कुछ कंप्यूटिंग वातावरण स्टैक का उपयोग उन तरीकों से करते हैं जो उन्हें सुरक्षा उल्लंघनों और हमलों के प्रति संवेदनशील बना सकते हैं। ऐसे वातावरण में काम करने वाले प्रोग्रामरों को इन कार्यान्वयनों के नुकसान से बचने के लिए विशेष ध्यान रखना चाहिए।
उदाहरण के लिए, कुछ प्रोग्रामिंग लैंग्वेज कॉल की गई प्रक्रिया और लिंकिंग जानकारी दोनों डेटा को स्टोर करने के लिए एक सामान्य स्टैक का उपयोग करती हैं जो प्रक्रिया को उसके कॉलर पर वापस जाने की स्वीकृति देती है। इसका मतलब यह है कि प्रोग्राम डेटा को उसी स्टैक से अंदर और बाहर ले जाता है जिसमें प्रक्रिया कॉल के लिए महत्वपूर्ण वापसी पते होते हैं। यदि डेटा को स्टैक पर गलत स्थान पर ले जाया जाता है, या एक बड़े आकार के डेटा आइटम को स्टैक स्थान पर ले जाया जाता है जो इसे सम्मिलित करने के लिए पर्याप्त बड़ा नहीं है, तो प्रक्रिया कॉल की वापसी जानकारी दूषित हो सकती है, जिससे प्रोग्राम विफल हो सकता है।
दुर्भावनापूर्ण पक्ष एक स्टैक स्मैशिंग हमले का प्रयास कर सकते हैं जो इस प्रकार के कार्यान्वयन का लाभ उठाते हुए एक प्रोग्राम को ओवरसाइज़्ड डेटा इनपुट प्रदान करता है जो इनपुट की लंबाई की जांच नहीं करता है। इस तरह का प्रोग्राम डेटा को पूरी तरह से स्टैक पर किसी स्थान पर कॉपी कर सकता है, और ऐसा करने से यह उन प्रक्रियाओं के लिए वापसी पते बदल सकता है जिन्होंने इसे बुलाया है। एक हमलावर एक विशिष्ट प्रकार के डेटा को खोजने के लिए प्रयोग कर सकता है जो ऐसे प्रोग्राम को प्रदान किया जा सकता है जैसे कि वर्तमान प्रक्रिया का वापसी पता स्टैक के भीतर एक क्षेत्र को इंगित करने के लिए रीसेट किया जाता है (और हमलावर द्वारा प्रदान किए गए डेटा के भीतर), जिसमें बदले में ऐसे निर्देश होते हैं जो अनधिकृत संचालन करते हैं।
इस प्रकार का हमला बफर ओवरफ्लो हमले पर एक भिन्नता है और सॉफ्टवेयर में सुरक्षा उल्लंघनों का एक बहुत ही लगातार स्रोत है, मुख्यतः क्योंकि कुछ सबसे लोकप्रिय कंपाइलर डेटा और प्रक्रिया कॉल दोनों के लिए एक साझा स्टैक का उपयोग करते हैं, और इसकी लंबाई को सत्यापित नहीं करते हैं। डेटा आइटम प्रायः, प्रोग्रामर डेटा आइटम के आकार को सत्यापित करने के लिए कोड नहीं लिखते हैं, और जब एक बड़े या छोटे डेटा आइटम को स्टैक पर कॉपी किया जाता है, तो सुरक्षा उल्लंघन हो सकता है।
यह भी देखें
- डेटा संरचनाओं की सूची
- केयूए (सार डेटा प्रकार)
- डबल-एंडेड केयूए
- फीफो (कंप्यूटिंग और इलेक्ट्रॉनिक्स)
- स्टैक-आधारित मेमोरी आवंटन
- स्टैक ओवरफ़्लो
- स्टैक-उन्मुख प्रोग्रामिंग भाषा
टिप्पणियाँ
संदर्भ
- ↑ 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.
- ↑ 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).)
- ↑ 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)
- ↑ 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.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)
- ↑ 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.
- ↑ 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.
- ↑ Samelson, Klaus; Bauer, Friedrich Ludwig (1959). "Sequentielle Formelübersetzung" [Sequential Formula Translation]. Elektronische Rechenanlagen (in Deutsch). 1 (4): 176–182.
- ↑ Samelson, Klaus; Bauer, Friedrich Ludwig (1960). "Sequential Formula Translation". Communications of the ACM. 3 (2): 76–83. doi:10.1145/366959.366968. S2CID 16646147.
- ↑ "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.
- ↑ 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)
- ↑ Kämmerer, Wilhelm [in Deutsch] (1958). Ziffern-Rechenautomat mit Programmierung nach mathematischem Formelbild (Habilitation thesis) (in Deutsch). Friedrich-Schiller-Universität, Jena, Germany.
- ↑ Kämmerer, Wilhelm [in Deutsch] (1960). Ziffernrechenautomaten.
{{cite book}}:|work=ignored (help) - ↑ 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.
- ↑ 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.
- ↑ Horowitz, Ellis (1984). Fundamentals of Data Structures in Pascal. Computer Science Press. p. 67.
- ↑ 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) - ↑ 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.
- ↑ 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..
- ↑ 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..
- ↑ 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..
This article incorporates public domain material from Black, Paul E. "Bounded stack". Dictionary of Algorithms and Data Structures.
अग्रिम पठन
- Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp. 238–243.
- Langmaack, Hans [in Deutsch] (2015) [2014-11-14]. Written at Kiel, Germany. Friedrich L. Bauers und Klaus Samelsons Arbeiten in den 1950er-Jahren zur Einführung der Begriffe Kellerprinzip und Kellerautomat [Friedrich L. Bauer's and Klaus Samelson's works in the 1950s on the introduction of the terms cellar principle and cellar automaton] (PDF) (in Deutsch). Jena, Germany: Institut für Informatik, Christian-Albrechts-Universität zu Kiel. pp. 19–29. Archived (PDF) from the original on 2022-11-14. Retrieved 2022-11-14. (11 pages) (NB. Published in Fothe & Wilke.)
- Goos, Gerhard [in Deutsch] (2017-08-07). Geschichte der deutschsprachigen Informatik - Programmiersprachen und Übersetzerbau [History of informatics in German-speaking countries - Programming languages and compiler design] (PDF) (in Deutsch). Karlsruhe, Germany: Fakultät für Informatik, Karlsruhe Institute of Technology (KIT). Archived (PDF) from the original on 2022-05-19. Retrieved 2022-11-14. (11 pages)
बाहरी संबंध
