स्थायी संरचना भाग 1: स्थायी ढेर

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



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



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

लगातार ढेर

समस्या का बयान। प्रारंभ में, नंबर 0, n (ढेर की संख्या) के साथ एक खाली स्टैक है, शुरू में एक के बराबर है। आप निम्नलिखित कार्यों को लागू करने के लिए आवश्यक हैं:

• पुश (i, x) - स्टैक संख्या i में तत्व x जोड़ें। परिणामी स्टैक n + 1 होगा।
• pop (i) - स्टैक संख्या i के अंतिम तत्व को लौटाएं और "इसे स्टैक से बाहर फेंकें।" परिणामी स्टैक n + 1 होगा।

सीधे शब्दों में कहें, प्रत्येक ऑपरेशन के बाद पुराने को खराब किए बिना "नया" स्टैक बनाना आवश्यक है।



निर्णय। इस समस्या का सबसे सरल और स्पष्ट समाधान वर्णित प्रक्रिया का अनुकरण करना है, अर्थात। प्रत्येक ऑपरेशन के साथ स्टैक की ईमानदार प्रतिलिपि। जाहिर है, यह सबसे प्रभावी समाधान नहीं है। एक ऑपरेशन की जटिलता हे (n) और आवश्यक मेमोरी की मात्रा O (n * n) है।



एक इष्टतम समाधान के विचार के करीब पहुंचने के लिए, आप एक ग्राफ के रूप में स्टैक की कल्पना करने की कोशिश कर सकते हैं, जहां शीर्ष इसका तत्व है, फिर प्रत्येक शीर्ष से (पूंछ को छोड़कर) हमने स्टैक के पिछले तत्व में एक किनारे लगाया। एक स्टैक के लिए उदाहरण जिसमें '1', '2', '3', '4', '5' क्रमिक रूप से जोड़े गए थे:







यह स्पष्ट है कि पूरे स्टैक को पुनर्स्थापित करने के लिए, स्टैक के "सिर" को जानना हमारे लिए पर्याप्त है। आइए एक स्टैक की n प्रतियों के बजाय n प्रथम तत्वों को संग्रहीत करने का प्रयास करें। फिर पुश और पॉप ऑपरेशन इस तरह दिखाई देंगे:

• पुश (x, i) - मान x के साथ एक नया तत्व बनाता है, जो स्टैक पर पिछले तत्व के रूप में संख्या के साथ तत्व को संदर्भित करता है।
• pop (i) - संख्या i के साथ तत्व में संग्रहीत मान लौटाता है और पिछले तत्व को कॉपी करता है।

आइए हम स्पष्टता के लिए एक उदाहरण एल्गोरिथ्म पर विचार करें। आइए शुरू में हमारे पास एक खाली स्टैक है। सुविधा के लिए, हम इसे एक खाली स्टैक के साथ चिह्नित "सिर" के रूप में संग्रहीत करेंगे:





अगला, पुश (1, 5) करें। 1 का संदर्भ देते हुए 5 के मान से एक नया शीर्ष बनाया जाता है:





आइए पुश (2, 10) और पुश (1, 6) को इसी तरह करें:





जाहिर है, सभी 4 स्टैक अब सही ढंग से बनाए गए हैं और आसानी से बहाल किए गए हैं। आइए अब संचालन पॉप (2) और पॉप (3) क्रम से करने की कोशिश करते हैं:

पॉप (2) 5 रिटर्न देता है और 1 वर्टेक्स को कॉपी करता है। परिणामस्वरूप पांचवां स्टैक खाली है।





पॉप (3) 10 रिटर्न देता है और 2 वें शीर्ष को कॉपी करता है: हमें छठा स्टैक मिलता है।





जाहिर है, एक अनुरोध O (1) के लिए काम करता है और कुल मिलाकर O (n) मेमोरी की आवश्यकता होती है, जो आनन्दित नहीं कर सकता है।



आवेदन। जहां तक ​​मुझे याद है, मुझे कई समस्याओं का सामना करना पड़ा, जो लगातार स्टैक का उपयोग करके हल किया जा सकता है। यह स्पष्ट है कि कुछ प्रधानता के कारण, इन संरचनाओं की कल्पना भी मुश्किल नहीं हो सकती है, लेकिन फिर भी वे मौजूद हैं। उदाहरण के लिए:



N बच्चे स्नोमैन बनाते हैं। पहले बच्चे ने त्रिज्या R1 की एक गेंद से एक स्नोमैन बनाया। प्रत्येक बाद के बच्चे ने एक स्नोमैन को पिछले एक के समान बनाया, लेकिन थोड़ा सोचने के बाद, उसने या तो त्रिज्या री की एक गेंद को जोड़ा या ऊपरी मौजूदा गेंद को नष्ट कर दिया। यह गारंटी है कि सभी स्नोमैन में गेंदों की एक सकारात्मक संख्या होती है। इनपुट एन है, बच्चों में से प्रत्येक के बारे में जानकारी है कि क्या उसने आखिरी गेंद को नष्ट कर दिया है या अपना खुद का जोड़ा (फिर उसका त्रिज्या भी दिया गया है)। निम्नलिखित 1 से लेकर N तक के K नंबरों का एक सेट है, प्रत्येक के लिए इस संख्या के साथ एक स्नोमैन में गेंदों के अनुक्रम को प्राप्त करना आवश्यक है। एन और के पर सीमा एक मिलियन है।



लगातार स्टैक के कार्यान्वयन पर अनुभाग को पढ़ने के बाद, इस समस्या का समाधान स्पष्ट हो जाता है।



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