स्वतः रांग: आपला स्वतःचा रांगेचा वर्ग कसा लिहावा

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

रूपकांपासून दूर जाताच, रांग जास्त मर्यादित क्षमतेसह अ‍ॅरेसारखे कार्य करते. ही फर्स्ट-इन-फर्स्ट-आउट डेटा स्ट्रक्चर आहे आणि सामान्यत: त्यास चार पद्धती असतील:

एंक्यू: रांगेच्या शेवटी मूल्य जोडते

dequeue: रांगेतील पहिले मूल्य काढून टाकते

डोकावून पहा: रांगेतील पहिले मूल्य काय आहे ते न हटविता ते पाहण्याची आपल्याला अनुमती देते

is_empty?: रांगेत काही मूल्ये आहेत का ते तपासू

चला कोडिंग करू. प्रथम आपल्याला क्लास बनवायचा आहे. आम्ही नवीन अ‍ॅरे बनवून प्रारंभ करू, ज्याला आपण रांगेत कॉल करू आणि त्याच्या लांबीचा मागोवा ठेवू. सध्याचा आमचा वर्ग असे दिसतेः

थोडे कंटाळवाणे, परंतु प्रारंभ करण्यासाठी चांगली जागा. चला एन्क्यू तयार करू:

एंक्यू साठी आम्हाला सध्याच्या रांगेच्या शेवटी घटकात समाविष्ट करण्यास सक्षम व्हायचे आहे. लांबी वापरुन ते कोठे आहे ते शोधू शकतो. उदाहरणार्थ, जर आमची रांग रिकामी असेल तर लांबी 0 च्या बरोबरीने असेल, तर आम्ही पहिल्या अनुक्रमणिकेत मूल्य प्रविष्ट करू. आमच्या रांगेमध्ये पाच आयटम असल्यास, लांबी पाच आहे, परंतु त्या वस्तू निर्देशांक 0-4 मध्ये आहेत, म्हणून निर्देशांक 5 मध्ये आपले पुढील मूल्य जोडणे आम्हाला हवे आहे तेच आहे. छान!

चला तिरस्करणाकडे जाऊया. आम्ही आयटम हटवण्याची खरोखरच तसदी घेत नसल्यास त्याऐवजी आम्ही एखाद्या ऑफसेटचा मागोवा ठेवतो आणि जेव्हा एखादी वस्तू शोधतो तेव्हा ती अद्यतनित करते? याचा अर्थ असा आहे की आम्हाला मागोवा ठेवण्यासाठी नवीन चल आवश्यक आहे. हे आमच्या कन्स्ट्रक्टर मध्ये जोडून सुरू करूया.

आता याला डेको्यू पद्धतीत प्लग करू.

चला हे खाली करू. असे म्हणा की त्यामध्ये तीन आयटम असलेले अ‍ॅरे आहेतः

वर, मी प्रत्येक मूल्य असलेल्या निर्देशांकाचे लेबल लावले आहे आणि तळाशी मी ऑफसेट लेबल केले आहे. सुरुवातीला ते एक आणि एकसारखेच आहेत. तथापि, आम्हाला अ‍ॅरेमधून एखादी वस्तू काढायची असल्यास ती प्रत्यक्षात काढायची गरज नाही. आपण ज्या गोष्टी पहात आहोत त्या आपण समायोजित करणे आवश्यक आहे. जर आपण एखाद्या वस्तूच्या अनुक्रमणिकेऐवजी एखादे ऑफसेट वापरत असाल तर आम्ही ऑफसेटमध्ये एक जोडून आम्ही कुठे सुधारित आहोत हे सहजपणे समायोजित करू शकतो. खाली दिलेल्या प्रतिमेत मी setरे मधील पहिले मूल्य काढून टाकले आहे, अशा प्रकारे आम्ही ज्या अ‍ॅरेचा शोध घेत आहोत त्याचा भाग बदलून हे बदलून:

त्याच वेळी, आम्हाला लांबी कमी करण्याची आवश्यकता आहे, आणि आम्ही नुकतीच काढलेली मूल्य देखील परत करायची आहे. रुबीच्या अंतर्भूत परताव्याबद्दल धन्यवाद, आम्ही स्पष्टपणे रिटर्न न बोलता पद्धतीच्या शेवटच्या विधानात आपल्या दृष्टीकोनातून हलवलेली मूल्य परत देऊ शकतो, परंतु बर्‍याच अन्य भाषांमध्ये आम्ही त्याबद्दल स्पष्ट होऊ इच्छितो.

हे सर्व छान आहे, परंतु आता आपल्यास सामोरे जाण्यासाठी नवीन समस्या आली आहे. आमचे एन्क्यू यापुढे कार्य करत नाही, म्हणून आम्हाला ते अद्यतनित करण्याची आवश्यकता आहे. रांगेच्या शेवटी आयटम जोडण्याऐवजी जसे सोडल्यास, आम्ही त्यात चुकून आधीपासूनच त्या आयटम अधिलिखित करू. चला एन्को आणि परत अद्यतनित करूया:

रांग लांबी आणि ऑफसेट या दोन्ही गोष्टींचा विचार करून आम्ही रांगेत जिथे काहीतरी जोडतो ते अद्ययावत करीत आहोत. तर, जर आपल्याला वर काढलेल्या रांगेत काहीतरी जोडायचे असेल तर आमची ऑफसेट 1 असेल आणि आपली लांबी 2 असेल. त्या पाठोपाठ 1 + 2 = 3, जिथे आपल्याला नवीन आयटम जोडायचा आहे तो निर्देशांक आहे.

Is_empty वर जात आहे ?:

आम्ही आधीच आतीलरित्या लांबीचा मागोवा घेत आहोत, is_empty? रांगेत कमीतकमी एखादी वस्तू आहे की नाही हे तपासण्याची सोपी बाब आहे. नसल्यास, आम्ही सत्य परत करू शकतो (रांग रिकामी आहे), आणि अन्यथा आम्ही खोटे परत करतो (रांग रिकामी नाही).

शेवटी, आपल्याकडे लिहिण्यासाठी पहाण्याची पद्धत आहे. डोकावून, आम्हाला रांगेत न घेता पुढील मूल्य काय आहे हे तपासून पहायचे आहे. आमच्यासाठी भाग्यवान, ऑफसेट आधीच रांगेत असलेल्या पहिल्या आयटमच्या स्थानाचा मागोवा ठेवत आहे:

आम्ही आधी काढलेल्या रांगांचा संदर्भ देऊन हे तपासू:

या प्रकरणात, आमची ऑफसेट 0 आहे, म्हणून जेव्हा आपण रांगेत डोकावतो तेव्हा आपल्याला रांगेतला पहिला आयटम 'ए' दिसेल.

येथे, आम्ही आधीच रांगेतून एक आयटम काढला आहे. आमचे ऑफसेट सध्या 1 आहे, जे रांगेत असलेल्या पहिल्या आयटमची अनुक्रमणिका आहे आणि आम्ही ज्यासाठी शोधत आहोत.

छान! आपल्याकडे आता एक सोपा परंतु कार्यात्मक रांगेचा वर्ग आहे जो आपण आपल्या अंतःकरणाच्या इच्छेसाठी वापरू शकतो.