[Powered by Google Translate] [कतार]
[क्रिस Gerber, हार्वर्ड विश्वविद्यालय]
इस CS50 है, CS50.TV]
तत्वों के एक आदेश संग्रह के भंडारण के लिए उपयोगी डेटा संरचना एक कतार है.
यह प्रयोग किया जाता है जब तत्वों को हटा दिया जाना चाहिए
के रूप में वे एक ही क्रम में जोड़ा गया था.
इस अवधारणा फीफो, जो में, 1 बाहर पहली बार के लिए एक परिचित करा रहा है के रूप में जाना जाता है.
यह कल्पना करने में मदद करने के लिए, यह तस्वीर के लिए उपयोगी हो सकता है
एक दुकान पर एक Checkout लाइन.
के रूप में लोगों को आने, वे लाइन के पीछे प्रतीक्षा.
खजांची बदल जाता है तो मोर्चे पर ग्राहकों की सेवा लेता है,
जो तब एक समय में एक लाइन से बाहर निकलें.
कंप्यूटर विज्ञान में, हम लाइन के सामने करने के लिए सिर के रूप में देखें
और पूंछ के रूप में वापस.
जब हम एक आवेदन में इस का उपयोग कर सकते हैं का एक उदाहरण
कक्षा में नामांकन के लिए एक waitlist है.
सीटें कक्षा में उपलब्ध हो जाते हैं,
प्रतीक्षा सूची के सिर पर व्यक्ति कक्षा में भर्ती करने का अवसर प्रदान किया जाता है.
>> एक कतार किसी भी संग्रह का उपयोग कर निर्माण किया जा सकता है
कि एक सरणी या एक लिंक सूची के रूप में इस तरह के आदेश में डेटा संग्रहीत करता है.
संग्रह के साथ कतार में वस्तुओं की दुकान,
हम भी कतार के अंत में आइटम जोड़ने के लिए एक विधि की जरूरत है,
जो enqueuing कहा जाता है,
और एक अन्य कतार के सिर से एक आइटम हटाने के लिए,
जो dequeuing कहा जाता है.
यह उपयोगी होता है के लिए एक और विधि शामिल करने के लिए कतार की वर्तमान लंबाई वापस
के रूप में अच्छी तरह से जाँच करने के लिए अगर कतार खाली है के लिए एक विधि के रूप में.
चलो हम सी में integers की एक कतार कैसे लागू हो सकता है पर देखो,
तत्वों के संग्रह के लिए एक सरणी का उपयोग.
सबसे पहले, हम एक संरचना बुलाया कतार हमारे चर पकड़ बनाने के लिए.
हम integers के एक निश्चित आकार 0 सूचकांक सरणी का उपयोग होगा
तत्वों की दुकान.
हम भी एक चर बुलाया सिर शामिल होंगे
कि तत्व है कि कतार के सिर पर वर्तमान में है के सूचकांक में संग्रहीत करता है.
एक तीसरा चर, लंबाई बुलाया इस्तेमाल किया जा
सरणी में तत्वों की संख्या का ट्रैक रखने के लिए.
एक विकल्प के रूप में, आप एक चर बुलाया पूंछ का उपयोग करने पर विचार कर सकता है
सरणी में पिछले क्षेत्र तत्व को इंगित करने के लिए.
इससे पहले कि हम किसी भी अधिक कोड लिखने के लिए,
चलो बाहर हमारे डिजाइन की कोशिश.
चलो 0 लंबाई के एक खाली सरणी के साथ शुरू करते हैं,
साथ सिर 0 पर सेट.
अब चलो enqueue 4 मूल्यों - 6, 2, 3, और 1.
लंबाई अब 4 हो जाएगा,
और सिर 0 में रहना होगा.
>> क्या होता है अगर हम एक मूल्य विपंक्ति?
हम 3 लंबाई कम हो जाएगा,
1 के लिए सिर सेट,
और 6 मूल्य वापसी.
यही कोड इस तरह लग सकता है.
यहाँ हम विपंक्ति समारोह,
क्ष - जो कतार में एक सूचक लेता है और तत्व के लिए एक सूचक है,
जो एक प्रकार int है.
पहले हम कतार की लंबाई यकीन है कि यह 0 से अधिक है करने के लिए जाँच
सुनिश्चित करें कि वहाँ एक तत्व के लिए dequeued है.
तो फिर हम तत्वों सरणी में स्थिति सिर पर, देखो,
और तत्व का मूल्य निर्धारित करने के लिए उस स्थिति में मूल्य.
तो फिर हम सिर बदलने के लिए अगले सूचकांक
क्षमता%.
हम तो 1 से कतार की लंबाई कम है.
अंत में, हम यह इंगित करने के लिए कि विपंक्ति सफल रहा था सच वापसी.
अगर हम फिर विपंक्ति, लंबाई 2 बन जाएगा,
सिर भी 2 बन जाएगा,
और वापसी मान 2 हो जाएगा.
>> क्या होता है अगर हम एक 7 के रूप में एक और मूल्य enqueue?
जैसा कि हम कतार के अंत में थे,
हम चारों ओर लपेट और सरणी के तत्व 0 में मूल्य की दुकान की आवश्यकता होगी.
गणितीय, इस लंबाई जोड़कर प्रतिनिधित्व किया जा सकता है
सिर के सूचकांक
और एक कतार क्षमता का उपयोग कर मापांक प्रदर्शन.
यहाँ है कि 2 2, जो 4 4% है,
जो 0 है.
इस विचार अनुवाद हम इस समारोह कोड.
यहाँ हम enqueue समारोह देखने के लिए,
क्ष - जो कतार में एक सूचक लेता है -
और तत्व कतारबद्ध करने के लिए लेता है, जो एक पूर्णांक है.
हम अगले जांच सुनिश्चित करने के लिए कि कतार की क्षमता
अभी भी कतार की वर्तमान लंबाई से अधिक है.
अगला, हम तत्वों सरणी में तत्व की दुकान
सूचकांक में जो सिर + लंबाई% कतार की क्षमता से निर्धारित होता है.
हम फिर 1 से कतार लंबाई बढ़ाने के लिए,
और फिर सच लौटने के लिए संकेत मिलता है कि enqueue समारोह सफल रहा था.
>> दो कार्यों हम उल्लेख किया है के अलावा,
वहाँ दो अतिरिक्त कार्य कर रहे हैं.
पहले isempty समारोह है,
जो कतार में एक सूचक लेता है
पुष्टि और कि लंबाई 0 है.
2 लंबाई समारोह है,
जो भी कतार में एक सूचक लेता है
और struct से मौजूदा लंबाई देता है.
इस संक्षिप्त सिंहावलोकन एक कतार के एक संभव कार्यान्वयन का प्रदर्शन किया है.
सीमाओं के इस कार्यान्वयन के लिए एक
यह है कि कतार एक निश्चित अधिकतम आकार है.
यदि हम अधिक तत्वों से कतार पकड़ कर सकते हैं जोड़ने की कोशिश
हम अनुरोध उपेक्षा और तत्व ड्रॉप की आवश्यकता हो सकती है,
या हम त्रुटि के कुछ प्रकार लौटना पसंद कर सकते हैं.
एक सरणी के बजाय एक लिंक सूची का उपयोग
यह गतिशील आकार कतार को आसान बनाना होगा.
हालांकि, के बाद से हम एक लिंक सूची के तत्वों के लिए सीधी पहुँच नहीं है,
अगर हम पूंछ का ट्रैक नहीं रहते हो,
हम पूरे लिंक की गई सूची को स्कैन करने के लिए समाप्त करने के लिए हर बार प्राप्त करना होगा.
हम भी अन्य डेटा प्रकार की एक सरणी का उपयोग करने पर विचार कर सकते हैं,
structs के रूप में इस तरह के और अधिक जटिल तत्व की कतार बनाने.
एक वर्ग waitlist के हमारे उदाहरण के लिए वापस सोच,
इन संरचनाओं व्यक्तिगत छात्रों का प्रतिनिधित्व कर सकता है.
>> मेरा नाम क्रिस Gerber है, और इस CS50 है.
[CS50.TV]
और रिटर्न - >> एक बार.
और संकेत मिलता है कि वापसी सच - कतार सफल रहा था.
% कतार की क्षमता -
यह संपादित करने में मज़ा आने वाला है. [हँसी]