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

यह एक दौड़ की तरह होगा एक ही रास्ता है, तो नीचे करने के लिए आप पर टेलर से बात करने के लिए मिला बैंक लाइन में अंतिम व्यक्ति हो गया था। हर कोई हमेशा चाहेगा लाइन में अंतिम व्यक्ति हो सकता है, और पहले व्यक्ति जो वहाँ गया था कौन है, थोड़ी देर के लिए इंतजार कर रहा है घंटे के लिए हो सकता है, और घंटे, और घंटे वे वास्तव में करने के लिए एक मौका है इससे पहले बैंक में किसी भी पैसा वापस ले लें। और तो कतारों की तरह कर रहे हैं निष्पक्षता संरचना को लागू करने। लेकिन यह जरूरी है कि इसका मतलब यह नहीं ढेर सिर्फ एक बुरी बात कर रहे हैं कि कतारों ऐसा करने का एक और तरीका है कि। तो फिर एक कतार पहले में पहला है बाहर, में जो पिछले एक ढेर, बनाम पहले बाहर। एक ढेर के लिए इसी प्रकार, हम दो आपरेशन किया है हम कतारों पर प्रदर्शन कर सकते हैं। नाम जोड़ने के लिए है, जो एन्क्यू हैं कतार के अंत करने के लिए एक नए तत्व, जो है और विपंक्ति, सबसे पुराना दूर करने के लिए लाइन के सामने से तत्व। इसलिए हम तत्वों को जोड़ने के लिए जा रहे हैं कतार के अंत पर, और हम तत्वों को दूर करने के लिए जा रहे हैं लाइन के सामने से। फिर, ढेर के साथ, हम जोड़ रहे थे ढेर के शीर्ष करने के लिए तत्वों और तत्वों को हटाने ढेर के ऊपर से। एन्क्यू साथ तो, इसे जोड़ने है सामने से हटाने के अंत। वहाँ के सबसे पुराने बात तो हमेशा अगले बात है हम कोशिश करते हैं, तो बाहर आने के लिए और कुछ विपंक्ति। 

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

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

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

तो यहाँ हमारे कतार है। यह एक संरचना है। यह तीन सदस्यों या तीन में शामिल खेतों, आकार क्षमता की एक सरणी। इस मामले में, क्षमता 10 है। और इस सरणी है पूर्णांकों आयोजित करने जा रहा। हरे रंग में हमारी लाइन के सामने है, अगले तत्व हटा दिया, और लाल रंग में किया जाना है कतार के आकार का हो जाएगा, कितने तत्वों वर्तमान में कर रहे हैं कतार में मौजूदा। हम q.front बराबरी का कहना है कि यदि ऐसा है तो 0, और q.size आकार के बराबर होती है 0-- हम उन क्षेत्रों में 0s डाल रहे हैं। और इस बिंदु पर, हम बहुत ज्यादा कर रहे हैं हमारे कतार के साथ काम शुरू करने के लिए तैयार है। 

तो पहला ऑपरेशन हम कर सकते हैं प्रदर्शन कुछ enqueue करने के लिए है, करने के लिए एक नया तत्व जोड़ने के लिए कतार के अंत। खैर, हम करने के लिए क्या जरूरत है सामान्य मामले में क्या? वैसे इस समारोह की जरूरत है enqueue हमारे कतार के लिए एक सूचक को स्वीकार करने के लिए। फिर, हम घोषणा की थी कि अगर विश्व स्तर पर हमारी कतार, हम ऐसा करने की जरूरत नहीं होगी जरूरी है, लेकिन सामान्य तौर पर, हम संकेत स्वीकार करने की जरूरत डेटा संरचनाओं के लिए इस तरह, अन्यथा, क्योंकि हम हम कर रहे हैं value-- के पास से गुजर रहे हैं कतार की प्रतियों में से गुजर रहा है, और इसलिए हम वास्तव में नहीं बदल रहे हैं हम बदलने का इरादा है कि कतार। 

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

तो चलो शुरू हो जाओ। यहाँ, फिर से, सामान्य कि प्रपत्र समारोह घोषणा एन्क्यू की तरह लग सकता है के लिए। और अब हम चले। के नंबर enqueue चलो कतार में 28। तो हम क्या करने जा रहे हैं? खैर, हमारे लाइन के सामने है 0, और हमारे कतार के आकार पर 0 पर है, और इसलिए हम शायद डाल करना चाहते हैं सरणी तत्व संख्या में 28 नंबर 0, है ना? तो क्या अब हम वहाँ में है कि रखा है। तो अब क्या हमें बदलने की जरूरत है? हम बदल नहीं करना चाहते हैं कतार के सामने, हम क्या तत्व जानना चाहते हैं क्योंकि हम बाद में विपंक्ति करने की आवश्यकता हो सकती है। तो कारण है कि हम सामने देखते हैं क्या है की एक संकेत की तरह है सरणी में सबसे पुरानी बात है। खैर array-- में सबसे पुराना बात में तथ्य यह है, सरणी में केवल एक चीज सही now-- है, जो 28 है सरणी स्थान 0 पर। इसलिए हम नहीं करना चाहते हैं कि, हरी संख्या में परिवर्तन वजह यह है कि सबसे पुराने तत्व है। बल्कि, हम आकार बदलना चाहते हैं। तो इस मामले में, हम करेंगे 1 करने के लिए आकार में वृद्धि। 

जहां के विचार के बारे में अब एक सामान्य प्रकार अगले तत्व एक कतार में जाना जा रहा है उन दो संख्याओं को जोड़ने के लिए है एक साथ, आगे और आकार, और कहा कि जहां अगले तुम्हें बताता हूँ कतार में तत्व जाना जा रहा है। तो अब दूसरे नंबर enqueue करते हैं। 33 enqueue करते हैं। तो 33 में जाना जा रहा है सरणी स्थान 0 प्लस 1। इस मामले में तो, यह जा रहा है सरणी स्थान 1 में जाने के लिए, और अब हमारे कतार के आकार 2 है। 

फिर, हम नहीं बदल रहे हैं हमारी लाइन के सामने, 28 अब भी है क्योंकि सबसे पुराने तत्व है, और हम हम अंत में मिलता है जब चाहते है-- तत्वों को हटाने, dequeuing को इस कतार से, हम जानना चाहते हैं जहां सबसे पुराने तत्व है। और इसलिए हम हमेशा बनाए रखने की जरूरत वह यह है कि जहां से कुछ के सूचक। तो यह है कि 0 के लिए वहाँ क्या है। यही कारण है कि सामने के लिए वहाँ क्या है। 

एन्क्यू में की एक और तत्व, 19 दें। मैं आप अनुमान लगा सकते हैं यकीन जहां 19 जाना जा रहा है। इस बारे में जाना जा रहा है सरणी स्थान नंबर 2। यही कारण है कि 0 से अधिक 2 है। और अब हमारे कतार के आकार 3 है। हम इसे में 3 तत्व है। तो हम करने के लिए थे, और हम नहीं जा रहे हैं अब ठीक करने के लिए, एक और तत्व enqueue यह सरणी स्थान में जाना होगा नंबर 3, और हमारे कतार के आकार 4 होगा। तो क्या अब हम कई तत्वों कतारबद्ध गए हैं। अब हम उन्हें दूर करने के लिए शुरू करते हैं। की कतार से उन्हें विपंक्ति करते हैं। 

तरह है, जो पॉप के समान ढेर के लिए इस के अनुरूप की, विपंक्ति एक को स्वीकार करने की जरूरत है फिर queue-- करने के लिए सूचक, जब तक यह विश्व स्तर पर घोषित की है। अब हम स्थान बदलना चाहते हैं कतार के सामने की। यह एक तरह से आता है जहां यह है खेलने में, कि सामने चर, हम हटाने क्योंकि एक बार एक तत्व है, हम चाहते हैं अगले सबसे पुराने तत्व को स्थानांतरित करने के लिए। 

तो फिर हम में कमी करना चाहते हैं कतार के आकार, और फिर हम मूल्य वापसी करना चाहते हैं कि कतार से हटा दिया गया था। फिर, हम सिर्फ यह त्यागने के लिए नहीं करना चाहती। हम संभवतः निकालने रहे हैं हम कर रहे हैं queue-- से हम इसके बारे में परवाह है क्योंकि यह dequeuing। इसलिए हम इस समारोह में वापसी करना चाहते हैं प्रकार मूल्य के एक डेटा तत्व। फिर, इस मामले में, मूल्य पूर्णांक है। 

तो अब कुछ विपंक्ति करते हैं। की कतार से एक तत्व को दूर करते हैं। अगर हम कहते हैं पूर्णांक एक्स के बराबर होती है और क्यू, एम्परसेंड q-- फिर कि इस क्यू डेटा के लिए एक संकेत है structure-- क्या तत्व dequeued होने जा रहा है? इस मामले में, यह पहली बार है, क्योंकि में पहली डेटा संरचना, फीफो बाहर, हम इस में डाल पहली बात कतार में 28 था, और इसलिए इस मामले में, हम में से 28 लेने के लिए जा रहे हैं जो है, जो कतार, नहीं, 19 इस एक ढेर था कि अगर हम किया होता। हम कतार में से 28 लेने के लिए जा रहे हैं। 

हम साथ क्या किया था के लिए इसी प्रकार एक ढेर, हम वास्तव में नहीं कर रहे हैं 28 को नष्ट करने के लिए जा रहा कतार से ही, हम बस की तरह करने के लिए जा रहे हैं की यह वहाँ नहीं है नाटक। तो यह वहाँ रहने के लिए जा रहा है स्मृति में है, लेकिन हम सिर्फ रहे हैं एक तरह से ले जाकर इसे नजरअंदाज करने के लिए जा रहा हमारे क्यू डेटा के अन्य दो क्षेत्रों संरचना। हम सामने बदलने जा रहे हैं। Q.front अब करने जा रहा है कि अब है, क्योंकि 1 हो हम में है सबसे पुरानी तत्व हमारे कतार, हम पहले से ही 28 को हटा दिया है, क्योंकि जो पूर्व के सबसे पुराने तत्व था। 

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

तो क्या अब हम dequeued किया है हमारी कतार से पहले तत्व। चलो इसे फिर से करते हैं। चलो एक और दूर करते हैं कतार से तत्व। सबसे पुराने मामले में, वर्तमान तत्व सरणी स्थान 1 है। यही कारण है कि q.front हमें बताता है। यही कारण है कि हरे बॉक्स हमें बताता है कि कि सबसे पुराना तत्व है। और हां, x 33 हो जाएगा। हम बस की तरह भूल जाओगे 33 सरणी में मौजूद है, और अब हम कहेंगे कि कतार में नए सबसे पुराने तत्व सरणी स्थान 2, और आकार में है तत्वों की कतार की, संख्या हम कतार में, 1 है। अब चलो कुछ enqueue है, और मैं एक तरह से, एक दूसरे महीने में यह दूर दे दी लेकिन हम में से 40 डाल करना चाहते हैं कतार, जहां 40 से जाना जा रहा है? खैर हम इसे टाल दिया गया है q.front प्लस कतार आकार में, और तो यह समझ में आता है वास्तव में यहां 40 डाल दिया। अब कम से सूचना है कि कुछ बिंदु, हम जा रहे हैं का अंत करने के लिए क्यू के अंदर हमारे सरणी, लेकिन लगता है कि 28 और बाहर फीका 33-- वे तकनीकी रूप से, वास्तव में कर रहे खुली जगह, है ना? और हां, तो हम अंततः सकता है उनका कहना है की है कि शासन उन दो together-- हम अंत में कर सकते हैं क्षमता के आकार के द्वारा आधुनिक करने की जरूरत है इसलिए हम चारों ओर लपेट कर सकते हैं। 

हम तत्व करने के लिए मिलता है तो है, हम कर रहे हैं तो 10 नंबर तत्व नंबर 10 में यह जगह, हम चाहते हैं वास्तव में सरणी स्थान 0 में डाल दिया। और हम करने के लिए जा रहे थे सरणी मुझे माफ location--, हम उन्हें एक साथ जोड़ा है, तो और हम नंबर के लिए मिला हम डाल दिया जाएगा, जहां 11 होगा यह, जो इस array-- में मौजूद नहीं है यह सीमा से बाहर जा रहा होगा। हम 10 से रक्षा मंत्रालय और डाल सकता है यह सरणी स्थान 1 में। तो यह है कि कतारों काम कैसे करना है। वे हमेशा बाएं से जाने जा रहे हैं सही करने के लिए और संभवतः आसपास लपेटो। और अगर आप वे कर रहे हैं कि पता है पूर्ण यदि आकार, लाल बॉक्स कि, क्षमता के बराबर हो जाता है। और हम करने के लिए 40 जोड़ दिया है, ताकि बाद कतार, अच्छी तरह से हम क्या करने की जरूरत है? खैर, सबसे पुराना तत्व कतार में, अभी भी 19 है इसलिए हम बदल नहीं करना चाहते हैं कतार के सामने, लेकिन अब हम दो हैं कतार में तत्वों, और इसलिए हम बढ़ाना चाहते हैं 1-2 हमारे आकार। 

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

तो चलो पर एक नज़र है क्या इस तरह लग सकता है। हम enquue-- चाहते हैं तो अब, फिर से हम कर रहे हैं एक लिंक्ड-सूची का उपयोग करने जा यहां मॉडल के आधार पर। हम enqueue चाहते हैं, हम चाहते हैं खैर, एक नया तत्व जोड़ने के लिए हमें क्या करना होगा? सब से पहले, ठीक है, क्योंकि हम अंत करने के लिए जोड़ रहे हैं और से हटाने शुरुआत में, हम शायद दोनों के लिए संकेत बनाए रखना चाहते हैं सिर और लिंक सूची की पूंछ? पूंछ के लिए एक और कार्यकाल के किया जा रहा है लिंक सूची के अंत में, लिंक सूची में पिछले तत्व। और ये, शायद होगा फिर, हमारे लिए फायदेमंद हो सकता है वे वैश्विक चर रहे हैं। लेकिन अब हम एक नया जोड़ना चाहते हैं तत्व हमें क्या करना है? क्या हम सिर्फ [? मलक?] या गतिशील खुद के लिए हमारे नए नोड का आवंटन। हम किसी भी जोड़ने और फिर, जब सिर्फ पसंद एक दोगुना लिंक सूची हम करने के लिए तत्व, सिर्फ of-- हल करना होगा यहां उन पिछले तीन चरणों बस सब जाने के बारे में कर रहे हैं सही तरीके से संकेत तो यह है कि तत्व में जोड़ा जाता है चेन तोड़ने के बिना श्रृंखला या गलती किसी प्रकार का कर रही है या दुर्घटना के किसी प्रकार का कर जिससे हम गलती से हो हमारे कतार के कुछ तत्वों को अनाथ। यहाँ इस तरह लग सकता है। हम तत्व जोड़ना चाहते हैं इस पंक्ति के अंत में 10। यहां के सबसे पुराने तत्व तो सिर का प्रतिनिधित्व करती है। यही कारण है कि हम डाल पहले की बात है यहाँ इस काल्पनिक कतार में। और पूंछ, 13, सबसे अधिक है हाल ही में तत्व जोड़े। और इसलिए हम में 10 enqueue करना चाहते हैं इस कतार में, हम 13 के बाद यह करना चाहते हैं। और इसलिए हम गतिशील करने के लिए जा रहे हैं एक नए नोड के लिए जगह आवंटित और यह सुनिश्चित करना बातिल के लिए जाँच हम एक स्मृति विफलता नहीं है। तो फिर हम करने जा रहे हैं उस नोड में 10 जगह, और अब हम सावधान रहने की जरूरत हम संकेत व्यवस्थित कैसे के बारे में इसलिए हम श्रृंखला तोड़ नहीं है। 

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

Dequeuing वास्तव में है popping के लिए बहुत समान है कि एक ढेर से एक लिंक सूची के रूप में लागू आप ढेर वीडियो देखा है। हम सब करने की जरूरत पर शुरू है शुरुआत, दूसरा तत्व मिल जाए, पहला तत्व मुक्त, और फिर सिर को स्थानांतरित दूसरा तत्व को इंगित करने के लिए। शायद बेहतर यह कल्पना करने के लिए अभी इसके बारे में अतिरिक्त स्पष्ट किया जाना है। तो यहाँ हमारे कतार फिर से है। 12 सबसे पुराने तत्व है हमारे कतार, सिर में। 10 नवीनतम तत्व है हमारे कतार, हमारी पूंछ में। 

और इसलिए हम चाहते हैं कि जब एक तत्व विपंक्ति करने के लिए, हम सबसे पुराने तत्व हटाना चाहते हैं। तो हम क्या करें? खैर, हम एक चंक्रमण सूचक सेट कि, सिर में शुरू होता है और हम तो यह है कि यह कदम है यह दूसरा तत्व के लिए अंक इस बात का सफर कह कर कुछ queue-- Trav अगले तीर के बराबर होती है, उदाहरण के लिए, को इंगित करने के लिए वहाँ Trav ले जाया जाएगा हम 12 विपंक्ति के बाद जो, 15,, हम 12 निकालने के बाद या होगा, तत्कालीन सबसे पुराने तत्व बन जाते हैं। 

अब हम पहले पर एक पकड़ मिल गया है सूचक सिर के माध्यम से तत्व और दूसरा तत्व सूचक Trav के माध्यम से। हम अब स्वतंत्र सिर कर सकते हैं, और फिर हम कर सकते हैं कुछ भी नहीं अब और 15 से पहले आता है। इसलिए हम 15 के पिछले बदल सकते हैं सूचक अशक्त करने के लिए बात करने के लिए, और हम सिर्फ सिर पर ले जाते हैं। और वहाँ हम चले। अब हम सफलतापूर्वक 12 dequeued, और अब हम 4 तत्वों का एक और कतार है। यही कारण है कि बहुत ज्यादा सब है , कतारों को देखते है दोनों सरणी आधारित और लिंक्ड-सूची के आधार पर। मैं डौग लॉयड हूँ। इस सीएस 50 है।