डौग लॉयड: ठीक है, आप कर रहे हैं इस बात से इतनी शायद बहुत परिचित सरणियों और लिंक सूचियों के साथ दो प्राथमिक जो है डाटा संरचनाओं हम है के सेट रखने के लिए के बारे में बात की थी इसी तरह के डेटा प्रकार के डेटा का आयोजन किया। अब हम बात करने जा रहे हैं बदलाव की एक जोड़ी के बारे में सरणियों और लिंक सूचियों पर। इस वीडियो में हम जा रहे हैं ढेर के बारे में बात करने के लिए। विशेष रूप से हम बात करने जा रहे हैं के बारे में डेटा संरचना एक ढेर बुलाया। पिछले चर्चाओं से याद संकेत और स्मृति के बारे में, ढेर भी है कि स्मृति का एक खंड के लिए नाम स्थिर रुप से घोषित जहां memory-- स्मृति कि आप आप का नाम है कि चर, नाम, एट वगैरह और समारोह तख्ते जो भी हम कॉल स्टैक फ्रेम मौजूद हैं। तो यह एक ढेर डेटा संरचना है स्मृति की नहीं एक ढेर खंड। ठीक। लेकिन एक ढेर में क्या है? तो यह सिर्फ एक बहुत सुंदर है संरचना के विशेष प्रकार कि एक संगठित तरीके से डेटा को बनाए रखता है। और दो बहुत ही वहाँ आम तरीकों को लागू करने के लिए दो डाटा संरचनाओं का उपयोग ढेर हम पहले से ही परिचित हैं कि, सरणियों और लिंक सूचियों। क्या एक ढेर खास है बनाता है हम जानकारी डाल दिया है जिसमें रास्ता ढेर, और जिस तरह से हम में ढेर से जानकारी निकालें। ढेर के साथ विशेष रूप से नियम केवल सबसे अधिक है हाल ही में जोड़ा तत्व हटाया जा सकता है। यह एक ढेर के रूप में अगर तो इसके बारे में सोचते हैं। हम सूचना जमा कर रहे हैं खुद के ऊपर, शीर्ष पर है और केवल एक चीज ढेर के हटाया जा सकता है। हम नीचे बात नहीं निकाल सकते बाकी सब होता है, क्योंकि पतन और अधिक गिरावट। इसलिए हम वास्तव में एक ढेर निर्माण कर रहे हैं कि हम तो टुकड़ा टुकड़ा करके हटा दिया है। इस वजह से हम सामान्यतः का उल्लेख एक LIFO संरचना के रूप में एक ढेर करने के लिए, अंतिम अंदर प्रथम बाहर। LIFO, पहले में बाहर पिछले। इसलिए क्योंकि इस प्रतिबंध पर की जानकारी के लिए जोड़ा जा सकता है कि कैसे और एक ढेर से हटा दिया है, वहाँ वास्तव में केवल दो बातें हम एक ढेर के साथ कर सकते हैं। हम है, जो धक्का कर सकते हैं हम जोड़ने के लिए उपयोग अवधि के शीर्ष करने के लिए एक नए तत्व ढेर, या अगर ढेर मौजूद नहीं है और हम इसे सिरे से बना रहे हैं पहली जगह में ढेर बनाने धक्का होगा। और उसके बाद पॉप, कि सीएस की तरह है अवधि हम सबसे हाल ही हटाने का उपयोग ढेर के ऊपर से तत्व जोड़े। इसलिए हम पर दोनों को देखने के लिए जा रहे हैं कार्यान्वयन, दोनों सरणी आधारित और लिंक सूची के आधार पर। और हम करने जा रहे हैं आधारित सरणी के साथ शुरू करते हैं। तो यहाँ के मूल विचार है क्या सरणी आधारित ढेर डेटा संरचना की तरह लग रही होगी। हम यहाँ एक टाइप परिभाषा है। अंदर की है कि हम दो सदस्य हैं संरचना का या खेतों। हम एक सरणी है। और फिर मैं उपयोग कर रहा हूँ मनमाने ढंग से डेटा प्रकार मूल्य। तो यह किसी भी डेटा प्रकार हो सकता है, पूर्णांक चार या कुछ अन्य डेटा आपने पहले बनाया टाइप करें। इसलिए हम आकार क्षमता की एक सरणी है। क्षमता एक पाउंड, निरंतर परिभाषित किया जा रहा शायद कहीं और हमारे फाइल में। इसलिए इस विशेष के साथ पहले से ही नोटिस हम bounding रहे हैं कार्यान्वयन खुद के रूप में आम तौर पर था सरणियों के साथ मामला है, हम गतिशील आकार नहीं कर सकते हैं, जो जहां एक निश्चित संख्या है तत्वों अधिकतम की है कि हम अपने ढेर में डाल सकते हैं। इस मामले में यह क्षमता तत्व है। हम यह भी का ट्रैक रखने ढेर के शीर्ष। सबसे क्या तत्व है हाल ही में ढेर करने के लिए कहा? और इसलिए हम उस पर नज़र रखने के एक चर बुलाया शीर्ष में। और यह सब एक साथ लिपटे हो जाता है एक ढेर नामक एक नए डेटा प्रकार में। और हम पैदा कर रहे हैं एक बार इस नए डेटा प्रकार हम यह कैसा व्यवहार कर सकते हैं किसी भी अन्य डेटा प्रकार। हम बस की तरह, ढेर एस घोषणा कर सकते हैं हम int एक्स, या चार Y कर सकता है। और हम ढेर जब कहते हैं एस, अच्छी तरह से क्या होता है हम का एक सेट हो जाता है स्मृति हमारे लिए अलग निर्धारित करें। इस मामले क्षमता में मैं जाहिरा तौर पर फैसला कर लिया है मैं एक मिल गया है, क्योंकि 10 प्रकार के ढेर के एकल चर जो दो क्षेत्रों को याद करते है। इस मामले में एक सरणी, जा रहा है पूर्णांक सरणी होने के लिए के रूप में मेरे उदाहरण के अधिकांश में मामला है। और एक अन्य पूर्णांक चर शीर्ष भंडारण की क्षमता, सबसे हाल ही में जोड़ा ढेर करने के लिए तत्व। का तो एक ही हो चुकी है कि हम क्या सिर्फ इस तरह लग रहा है परिभाषित किया। यह युक्त एक बॉक्स है 10 की एक सरणी क्या इस मामले में पूर्णांकों हो जाएगा और हरे रंग में वहाँ एक और पूर्णांक चर ढेर के शीर्ष से संकेत मिलता है। के शीर्ष सेट करने के लिए ढेर हम सिर्फ s.top कहते हैं। यही कारण है कि हम एक का उपयोग कैसे करना है एक संरचना रिकॉल के क्षेत्र। s.top प्रभावी ढंग से 0 के बराबर होती है हमारे ढेर करने के लिए इस करता है। तो फिर हम दो आपरेशन किया है हम अब प्रदर्शन कर सकते हैं। हम धक्का कर सकते हैं और हम पॉप कर सकते हैं। की धक्का के साथ शुरू करते हैं। फिर, एक नया जोड़ने का है धकेलने ढेर के शीर्ष करने के लिए तत्व। तो क्या हम में क्या करने की जरूरत है इस सरणी आधारित कार्यान्वयन? खैर सामान्य में धक्का समारोह जा रहा है एक को स्वीकार करने की जरूरत है ढेर करने के लिए सूचक। अब एक दूसरा ले और इसके बारे में सोचते हैं। हम क्यों स्वीकार करने के लिए चाहते हो जाएगा ढेर करने के लिए एक सूचक? पर पिछले वीडियो से याद चर गुंजाइश है और संकेत, हम सिर्फ भेजा तो क्या होगा ढेर, एक पैरामीटर के रूप में नहीं बल्कि क्या है? वहाँ वास्तव में क्या पारित किया जाएगा? हम एक प्रतिलिपि बना रहे हैं याद रखें हम एक समारोह के लिए इसे पारित जब जब तक हम संकेत का उपयोग करें। और इसलिए इस समारोह जरूरतों को धक्का ढेर करने के लिए एक सूचक को स्वीकार करने के लिए हम वास्तव में बदल रहे हैं इतना है कि ढेर हम बदलना चाहते हैं। दूसरी बात यह धक्का शायद करना चाहता है स्वीकार प्रकार मूल्य के एक डेटा तत्व है। इस मामले में, फिर, एक पूर्णांक कि हम ढेर के शीर्ष में जोड़ने के लिए जा रहे हैं। इसलिए हम अपने दो मापदंडों मिल गया है। हम क्या करने जा रहे हैं अब धक्का के अंदर करते हैं? खैर, बस, हम सिर्फ जोड़ने के लिए जा रहे हैं ढेर के शीर्ष करने के लिए उस तत्व और उसके बाद से जहां शीर्ष बदल ढेर कि शीर्ष मूल्य डॉट है, है। तो यह क्या एक समारोह है धक्का के लिए घोषणा एक में की तरह लग सकता है सरणी आधारित कार्यान्वयन। फिर यह एक कठोर नियम नहीं है आप इस बदल सकते हैं और हो सकता है कि यह अलग अलग तरीकों में भिन्नता है। शायद यह विश्व स्तर पर घोषित किया जाता है। और इसलिए तुम भी जरूरत नहीं है यह एक पैरामीटर के रूप में है पारित करने के लिए। यह फिर से सिर्फ एक है धक्का के लिए सामान्य स्थिति। और अलग देखते हैं तरीके से इसे लागू करने के लिए। लेकिन इस मामले में हमारे धक्का ले जा रहा है दो तर्क, एक ढेर के लिए एक सूचक और प्रकार मान, पूर्णांक के एक डेटा तत्व इस मामले में। तो हम, एस घोषित s.top 0 के बराबर होती कहा। अब देखते हैं कि धक्का ढेर पर 28 नंबर। अच्छा है कि क्या मतलब है? खैर वर्तमान में ढेर के शीर्ष 0 है। और तो क्या मूल रूप से है क्या होने जा रहा है हम नंबर छड़ी करने के लिए जा रहे हैं सरणी स्थान 0 में 28। बहुत सीधा है, है ना, कि शीर्ष था और अब हम जाने के लिए अच्छा कर रहे हैं। और फिर हम क्या बदलने की जरूरत है ढेर के ऊपर होगा। अगली बार तो यह है कि हम में एक तत्व को धक्का, हम में यह स्टोर करने के लिए जा रहे हैं सरणी स्थान, शायद नहीं 0। हम ऊपर लिख नहीं करना चाहते हैं हम सिर्फ वहाँ क्या रखा। और इसलिए हम सिर्फ शीर्ष 1 के लिए कदम होगा। यही कारण है कि शायद समझ में आता है। अब हम एक और तत्व डाल करना चाहते हैं ढेर पर, हम 33 पुश करने के लिए कहना चाहते हैं खैर अब हम सिर्फ 33 लेने के लिए जा रहे हैं और सरणी स्थान नंबर पर डाल 1, और उसके बाद के शीर्ष परिवर्तन हमारे सरणी स्थान नंबर दो होने की हो चुकी है। तो अगली बार अगर हम करना चाहते हैं ढेर पर एक तत्व को धक्का, यह सरणी स्थान 2 में डाल दिया जाएगा। और है कि एक बार और करते हैं। हम ढेर के बंद 19 धक्का होगा। हम सरणी स्थान 2 में 19 डाल देता हूँ और हमारे ढेर के शीर्ष बदल सरणी स्थान 3 होने की तो अगली बार जब हम यदि हम जाने के लिए अच्छा कर रहे हैं एक धक्का बनाने की जरूरत है। ठीक है, तो वह संक्षेप में धक्का है। क्या popping के बारे में? तो पॉपिंग की तरह है आगे बढ़ाने के लिए समकक्ष। यह हम ढेर से डेटा को हटाने का तरीका बताया। और सामान्य पॉप जरूरतों में निम्न करने के लिए। यह करने के लिए एक सूचक को स्वीकार करने की जरूरत है सामान्य मामले में फिर से हो चुकी है। कुछ अन्य मामले में आप कर सकते हैं विश्व स्तर पर हो चुकी है की घोषणा की है, जो मामले में आप इसे पारित करने की जरूरत नहीं क्योंकि यह पहले से ही यह करने के लिए उपयोग किया है एक वैश्विक चर के रूप में। लेकिन बाकी तो हम क्या करने की जरूरत है? खैर, हम incrementing थे धक्का में ढेर के ऊपर, तो हम शायद चाहते करने के लिए जा रहे हैं ढेर के शीर्ष घटती को पॉप में, है ना? और फिर बेशक हम भी चाहते करने के लिए जा रहे हैं हम दूर कि मूल्य लौटने के लिए। हम तत्वों को जोड़ने रहे हैं, हम चाहते हैं पर बाद में तत्वों को बाहर निकलने के लिए, शायद वास्तव में हम उन्हें तो हम संग्रहीत करना चाहते हैं बस से उन्हें नष्ट नहीं है ढेर और फिर उनके साथ कुछ भी नहीं है। आम तौर पर हम कर रहे हैं धक्का और यहां popping हम इस संग्रहीत करना चाहते हैं एक सार्थक तरीके में जानकारी और इसलिए यह नहीं कर सकता भावना सिर्फ यह त्यागने के लिए। इसलिए इस कार्य करना चाहिए शायद हमारे पास एक मूल्य वापसी। तो यह पॉप के लिए क्या एक घोषणा है ऊपर छोड़ दिया पर वहाँ की तरह लग सकता है। इस समारोह में रिटर्न प्रकार मूल्य के डेटा। फिर हम प्रयोग किया गया है पूर्णांकों भर। और यह एक ढेर के रूप में करने के लिए एक सूचक को स्वीकार करता है इसका एकमात्र तर्क या एकमात्र पैरामीटर। तो क्या पॉप करने जा रहा है? हम अब तक कहना चाहते हैं एस के बंद एक तत्व पॉप। तो मैं ढेर पिछले रहे हैं ने कहा कि याद पहली बार बाहर, LIFO डेटा संरचनाओं में। कौन सा तत्व जा रहा है ढेर से हटा दिया जा सकता है? आप 19 लगता था? तुम सही होगा क्योंकि। 19 हम करने के लिए जोड़ा पिछले तत्व था हम पर तत्वों जोर दे रहे थे जब ढेर, और इसलिए यह पहली बार होने जा रहा है हटा दिया जाता है कि तत्व। यह हम 28 ने कहा कि अगर के रूप में है, और फिर हम यह की चोटी पर 33 डाल और हम उस के शीर्ष पर 19 डाल दिया। हम से दूर ले जा सकते हैं केवल तत्व 19 है। अब यहाँ चित्र में मैंने क्या किया है तरह की सरणी से 19 हटाया जाता है। यही कारण है कि वास्तव में नहीं है हम क्या करने जा रहे हैं। हम बस की तरह करने के लिए जा रहे हैं की यह वहाँ नहीं है नाटक। यह अभी भी वहाँ है कि स्मृति स्थान, लेकिन हम सिर्फ इसे नजरअंदाज करने के लिए जा रहे हैं हमारे ढेर के शीर्ष बदलकर 3-2 से किया जा रहा। अगर हम थे तो अब धक्का ढेर पर एक और तत्व, इस पर 19 लिखना होगा। लेकिन हमें यह नहीं मुसीबत के माध्यम से चलते हैं ढेर से 19 को हटाने की। हम सिर्फ यह नहीं है वहाँ नाटक कर सकते हैं। ढेर के प्रयोजनों के लिए अगर यह चला गया है हम 2 की बजाय 3 होने की शीर्ष बदल जाते हैं। ठीक है, कि यह बहुत ज्यादा था इसलिए। यही कारण है कि हम सब करने की ज़रूरत है एक तत्व बंद पॉप करने के लिए। चलो इसे फिर से करते हैं। तो मैं करने के लिए यहाँ लाल रंग में यह प्रकाश डाला है हम एक और फोन कर रहे हैं संकेत मिलता है। हम एक ही बात करने के लिए जा रहे हैं। तो क्या होने जा रहा है? खैर, हम स्टोर करने के लिए जा रहे हैं एक्स में 33 और हम जा रहे हैं 1 करने के लिए ढेर के शीर्ष बदलने के लिए। हम एक पुश करने के लिए अब थे तो यह है कि हम कर रहे हैं जो ढेर में तत्व अभी क्या जा रहा है, क्या होने जा रहा है हम अधिलेखित जा रहे है सरणी स्थान नंबर 1। एक तरह से छोड़ दिया गया था कि 33 तो यह है कि उस के पीछे हम सिर्फ नाटक वहाँ नहीं है, हम बस जा रहे हैं यह पीटना और वहाँ के बजाय 40 डाल दिया। और फिर बेशक, हम एक धक्का दिया के बाद से, हम वेतन वृद्धि के लिए जा रहे हैं 1-2 ढेर के शीर्ष इसलिए हम अब जोड़ते हैं कि एक और तत्व यह हूँ सरणी स्थान नंबर दो में चलते हैं। अब लिंक सूचियों एक और कर रहे हैं ढेर को लागू करने का तरीका है। और पर इस परिभाषा यदि स्क्रीन, यहाँ आप परिचित लग रहा है यह लगभग लग रहा है, क्योंकि यह है बिल्कुल वैसा ही है, वास्तव में, यह बहुत ज्यादा ठीक है एक अकेले लिंक सूची के रूप में ही, आप की हमारी चर्चा से याद करते हैं अकेले एक अन्य वीडियो में सूचियों से जुड़े। यहां केवल प्रतिबंध , प्रोग्रामर के रूप में हमारे लिए है हम करने के लिए अनुमति नहीं कर रहे डालने या बेतरतीब ढंग से हटाना अकेले लिंक सूची से हम पहले से कर सकता है। हम केवल अब डालने और से हटा सकते हैं सामने या जुड़े के शीर्ष सूची। यही कारण है कि सच में ही है फर्क है। यह तो एक अकेले लिंक सूची है। यह केवल प्रतिबंध है खुद पर की जगह प्रोग्रामर के रूप में है कि एक ढेर में बदल जाता है। यहां नियम हमेशा एक बनाए रखने के लिए है एक लिंक सूची के सिर करने के लिए सूचक। यह निश्चित रूप से एक आम तौर पर है पहली महत्वपूर्ण नियम। अकेले आप सूची वैसे भी जुड़ा हुआ है के लिए केवल सिर के लिए एक संकेत की जरूरत है कि के क्रम में श्रृंखला का उल्लेख करने में सक्षम हो हर दूसरे तत्व को लिंक सूची में। लेकिन यह विशेष रूप से है एक ढेर के साथ महत्वपूर्ण है। और तो आम तौर पर आप कर रहे हैं वास्तव में चाहते करने जा इस सूचक एक वैश्विक चर हो। यह शायद करने के लिए जा रहा है और भी आसान है कि जिस तरह से किया। तो धक्का और पॉप की एनालॉगों क्या कर रहे हैं? ठीक है। तो फिर आगे बढ़ाने के जोड़ने का है ढेर करने के लिए एक नए तत्व। एक लिंक की गई सूची में उस हमारे पास करने के लिए जा रहे हैं इसका मतलब हम कर रहे हैं कि एक नया नोड बनाने के लिए लिंक सूची में जोड़ने के लिए जा रहा है, और फिर सावधान चरणों का पालन करें हम पहले से रेखांकित किया है कि अकेले लिंक सूचियों में इसे जोड़ने के लिए चेन तोड़ने के बिना श्रृंखला और खोने या किसी orphaning लिंक सूची के तत्वों। और कहा कि मूल रूप से क्या है पाठ की छोटी सी बूँद वहाँ सार। और चलो एक नजर डालते हैं एक चित्र के रूप में इसे। तो यहाँ हमारे लिंक सूची है। यह समवर्ती चार तत्व शामिल हैं। और अधिक पूरी तरह से हमारे यहाँ है चार तत्वों से युक्त हो चुकी है। और चलो अब हम कहना चाहते हैं इस ढेर पर एक नया आइटम धक्का। और हम एक नया धक्का चाहते हैं जिसका डेटा मान मद 12 है। वैसे तो हम क्या करने जा रहे हैं? अच्छी तरह से पहले हम करने जा रहे हैं गतिशील malloc अंतरिक्ष, एक नए नोड के लिए जगह आवंटित। और निश्चित रूप से तुरंत बाद हम हमेशा हम malloc के लिए एक फोन करना , अशक्त के लिए जाँच करने के लिए सुनिश्चित करें हम वापस अशक्त मिला क्योंकि अगर समस्या का किसी प्रकार का था। हम जानते हैं कि अशक्त भिन्नता नहीं करना चाहते हैं सूचक या आप एक SEG गलती भुगतना होगा। यह अच्छा नहीं है। इसलिए हम नोड के malloced गए हैं। हम यहाँ सफलता मिली है मान लेंगे। हम में से 12 डाल करने के लिए जा रहे हैं उस नोड के डेटा क्षेत्र। अब क्या आपको याद है कि हमारे संकेत के जो इसलिए हम श्रृंखला तोड़ नहीं है अगली चाल? हम यहाँ विकल्पों में से एक जोड़ी है लेकिन सुरक्षित होने जा रहा है कि केवल एक ही सूचक अगले करने के लिए खबर स्थापित करने के लिए है सूची के पुराने सिर इंगित या जल्दी ही हो जाएगा क्या सूची के पुराने सिर। और अब के सभी कि हमारे तत्व एक साथ जंजीर हैं, हम सिर्फ बात करने के लिए सूची स्थानांतरित कर सकते हैं नई करता है कि एक ही जगह पर। और अब हम प्रभावी रूप से धक्का दिया है एक ढेर के सामने पर नए तत्व। हम पॉप करने के लिए अभी करना चाहते हैं कि पहला तत्व हटा दें। और तो मूल रूप से क्या हम यहाँ क्या करना है अच्छी तरह से हम दूसरे तत्व खोजने के लिए है। अंततः है कि नए बन जाएगा हम पहले से एक को हटाने के बाद सिर। तो हम बस से शुरू करने की जरूरत शुरुआत में, एक आगे बढ़ना है। हम एक पर एक पकड़ मिल गया है एक बार जहां हम के आगे वर्तमान में हम सुरक्षित रूप से पहले से एक को नष्ट कर सकते हैं और फिर हम सिर्फ सिर स्थानांतरित कर सकते हैं क्या था को इंगित करने के लिए अब तो दूसरे कार्यकाल और उस के बाद सबसे पहले है नोड हटा दिया गया है। तो फिर, एक नज़र लेने इस पर एक चित्र के रूप में हम अब एक पॉप करने के लिए करना चाहते हैं इस ढेर के बंद तत्व। तो हम क्या करें? वैसे तो हम पहले पैदा करने के लिए जा रहे हैं जा रहा है कि एक नया सूचक प्रमुख के रूप में एक ही जगह पर बात करने के लिए। हम इसे एक की स्थिति को स्थानांतरित करने के लिए जा रहे हैं आगे Trav बराबरी कह कर उदाहरण के लिए अगले TRAV जो Trav सूचक एक अग्रिम होगा आगे की स्थिति। अब हमें मिल गया है कि एक पहला तत्व पर पकड़ सूचक कहा जाता सूची, और के माध्यम से कहा जाता है एक सूचक के माध्यम से दूसरे तत्व Trav, हम सुरक्षित रूप से है कि नष्ट कर सकते हैं ढेर से पहला तत्व बाकी को खोने के बिना चेन की वजह से हम उल्लेख करने के लिए एक रास्ता है दूसरा तत्व को के रास्ते से आगे सूचक Trav बुलाया। तो अब हम उस नोड मुक्त कर सकते हैं। हम सूची मुक्त कर सकते हैं। और फिर हम अब सब करने की ज़रूरत है एक ही जगह पर बात करने के लिए सूची को स्थानांतरित कि सफर करता है, और हम की पीठ तरह कर रहे हैं हम 12 से धक्का दे दिया इससे पहले कि हम शुरू कर दिया है, जहां पहले स्थान पर, सही है। हम कहाँ थे यह ठीक है। हम इस चार तत्व ढेर था। हम एक पांचवें गयी। हम एक पांचवें धक्का दिया तत्व पर, और फिर हम popped कि सबसे हाल ही में पीछे से तत्व जोड़े। यही कारण है कि बहुत ज्यादा सच है सभी ढेर करने के लिए नहीं है। आप सरणियों के रूप में उन्हें लागू कर सकते हैं। आप लिंक सूचियों के रूप में उन्हें लागू कर सकते हैं। अन्य, ज़ाहिर है, कर रहे हैं तरीके के रूप में उन्हें अच्छी तरह से लागू करने के लिए। हम प्रयोग करेंगे असल कारण ढेर को इस तरह से डेटा को बनाए रखने के लिए है सबसे हाल ही में कहा कि तत्व हम कर रहे हैं पहली बात यह है वापस पाने के लिए चाहते हो जा। मैं डौग लॉयड हूँ, इस CS50 है।