डेटा संरचना: स्टॅक आणि रांग

हाय! आज आपण कोणत्याही प्रोग्रामरसाठी अत्यंत महत्त्वाच्या असलेल्या गोष्टीबद्दल बोलू: डेटा स्ट्रक्चर्स. विकिपीडिया म्हणते: " डेटा स्ट्रक्चर म्हणजे डेटा ऑर्गनायझेशन, मॅनेजमेंट आणि स्टोरेज फॉरमॅट जे कार्यक्षम ऍक्सेस आणि फेरफार सक्षम करते. अधिक स्पष्टपणे, डेटा स्ट्रक्चर म्हणजे डेटा व्हॅल्यू, त्यांच्यामधील संबंध आणि कार्ये किंवा ऑपरेशन्स यांचा संग्रह. डेटावर लागू केले." व्याख्या थोडी गोंधळात टाकणारी आहे, परंतु त्याचा सारांश स्पष्ट आहे. डेटा स्ट्रक्चर हा एक प्रकारचा रेपॉजिटरी आहे जिथे आपण भविष्यातील वापरासाठी डेटा संग्रहित करतो. प्रोग्रामिंगमध्ये, डेटा स्ट्रक्चर्सची प्रचंड विविधता आहे. विशिष्ट समस्या सोडवताना, बर्याचदा सर्वात महत्वाची गोष्ट म्हणजे समस्येसाठी सर्वात योग्य डेटा संरचना निवडणे. आणि त्यापैकी अनेकांशी तुम्ही आधीच परिचित आहात! उदाहरणार्थ, तुम्हाला अॅरेबद्दल माहिती आहे. आणि आपण परिचित देखील आहातMap(या डेटा स्ट्रक्चरला "शब्दकोश" किंवा "सहयोगी अॅरे" म्हणून देखील संबोधले जाऊ शकते). हे समजून घेणे फार महत्वाचे आहे की डेटा स्ट्रक्चर्स कोणत्याही विशिष्ट भाषेशी जोडलेले नाहीत. ते फक्त अमूर्त "ब्लूप्रिंट" आहेत जे प्रत्येक प्रोग्रामिंग भाषा स्वतःचे वर्ग तयार करण्यासाठी किंवा विशिष्ट संरचनेची अंमलबजावणी करण्यासाठी वापरते. उदाहरणार्थ, सर्वात प्रसिद्ध डेटा संरचनांपैकी एक लिंक केलेली सूची आहे. तुम्ही विकिपीडियावर जाऊन ते कसे कार्य करते आणि त्याचे कोणते फायदे आणि तोटे आहेत याबद्दल वाचू शकता. कदाचित त्याची व्याख्या तुम्हाला परिचित वाटेल :) "लिंक केलेली सूची म्हणजे डेटा घटकांचा एक रेषीय संग्रह आहे, ज्याचा क्रम मेमरीमध्ये त्यांच्या भौतिक स्थानाद्वारे दिलेला नाही. त्याऐवजी, प्रत्येक घटक पुढीलकडे निर्देश करतो." हे आपल्या प्रिय व्यक्तीचे वर्णन करते LinkedList, नाही का? होय, आणि तेच आहे :) Java मध्ये, "लिंक्ड लिस्ट" डेटा स्ट्रक्चर क्लासद्वारे लागू केले जाते LinkedList. पण इतर भाषा देखील जोडलेल्या याद्या लागू करतात! Python मध्ये, या डेटा स्ट्रक्चरला " " म्हणतात llist. LinkedListजावा प्रमाणेच स्कालामध्ये त्याला " " म्हणतात . लिंक केलेली सूची ही मूलभूत सामान्य डेटा संरचनांपैकी एक आहे, त्यामुळे तुम्हाला आढळेल की ती कोणत्याही आधुनिक प्रोग्रामिंग भाषेत लागू केली जाते. हीच गोष्ट असोसिएटिव्ह अॅरेच्या बाबतीतही सत्य आहे. विकिपीडियाची ही व्याख्या आहे: "एक सहयोगी अॅरे, नकाशा, चिन्ह सारणी किंवा शब्दकोश हा एक अमूर्त डेटा प्रकार आहे जो (की, मूल्य) जोड्यांच्या संग्रहाने बनलेला असतो, जसे की प्रत्येक संभाव्य की संग्रहामध्ये जास्तीत जास्त एकदा दिसून येते." ते तुम्हाला कशाची आठवण करून देते का? :) होय. आमच्या जावा डेव्हलपर्ससाठी, एक सहयोगी अॅरे आहेMapइंटरफेस पण ही डेटा रचना इतर भाषांमध्येही लागू केली जाते! उदाहरणार्थ, C# प्रोग्रामर हे "शब्दकोश" नावाने ओळखतात. आणि रुबीमध्ये, हे "हॅश" नावाच्या वर्गात लागू केले जाते. बरं, तुम्हाला मुद्दा समजेल: डेटा स्ट्रक्चर्स प्रोग्रामिंगमधील सार्वभौमिक संकल्पना आहेत आणि प्रत्येक प्रोग्रामिंग भाषा त्यांना त्यांच्या स्वत: च्या मार्गाने लागू करते. आज आपण अशा दोन संरचनांचा अभ्यास करू - स्टॅक आणि क्यू — आणि ते Java मध्ये कसे लागू केले जातात ते पाहू.

जावा मध्ये स्टॅक

स्टॅक एक सुप्रसिद्ध डेटा संरचना आहे. हे खूप सोपे आहे. आपल्या दैनंदिन जीवनातील बर्‍याच गोष्टी स्टॅक म्हणून "अंमलबजावणी" केल्या जातात. या साध्या परिस्थितीची कल्पना करा: तुम्ही हॉटेलमध्ये रहात आहात आणि दिवसभरात तुम्हाला काही व्यावसायिक पत्रे मिळाली. त्यावेळी तुम्ही तुमच्या खोलीत नव्हते, त्यामुळे हॉटेलच्या क्लार्कने येणारी पत्रे तुमच्या डेस्कवर ठेवली. प्रथम, त्याने पहिले पत्र डेस्कवर ठेवले. मग दुसरे पत्र आले आणि त्याने ते पहिल्याच्या वर ठेवले. त्याने तिसरे अक्षर दुसऱ्याच्या वर ठेवले आणि चौथे अक्षर तिसऱ्याच्या वर ठेवले. आणि आता, एका साध्या प्रश्नाचे उत्तर द्या: जेव्हा तुम्ही तुमच्या खोलीत परत याल आणि टेबलवर स्टॅक पहाल तेव्हा तुम्ही प्रथम कोणते पत्र वाचाल ? बरोबर, तुम्ही सर्वात वरचे वाचालपत्र म्हणजे, अगदी अलीकडे आलेला . स्टॅक नेमके कसे कार्य करते. या तत्त्वाला "लास्ट इन फर्स्ट आउट" (LIFO) म्हणतात . स्टॅक कशासाठी चांगले आहेत? बरं, समजा तुम्ही Java मध्ये काही प्रकारचे कार्ड गेम तयार करत आहात. टेबलावर कार्ड्सचा डेक पडला आहे. खेळलेली पत्ते टाकून दिली जातात. ड्रॉ डेक आणि डिस्कार्ड पाइल दोन्ही अंमलात आणण्यासाठी तुम्ही दोन स्टॅक वापरू शकता. तुमच्या व्यवसायाच्या पत्रांप्रमाणेच त्याच तत्त्वाचे पालन करून खेळाडू डेकच्या शीर्षस्थानी त्यांची कार्डे घेतात. जेव्हा खेळाडू टाकलेल्या ढिगात कार्डे ठेवतात, तेव्हा नवीन टाकून दिलेली कार्डे जुन्याच्या वर ठेवली जातात. स्टॅकच्या आधारे अंमलात आणलेला गेममधील आमचा पहिला प्रयत्न येथे आहे:

public class Card {

   public Card(String name) {
       this.name = name;
   }

   private String name;

   public String getName() {
       return name;
   }

   public void setName(String name) {
       this.name = name;
   }

   @Override
   public String toString() {
       return "Card{" +
               "name='" + name + '\'' +
               '}';
   }
}

import java.util.Stack;

public class SimpleCardGame {

   // Draw deck
   private Stack<Card> deck;
  
   // Discard pile
   private Stack<Card> discardPile;

   public Card getCardFromDeck() {
       return deck.pop();
   }

   public void discard(Card card) {
       discardPile.push(card);
   }

   public Card lookAtTopCard() {

       return deck.peek();
   }
  
   // ...getters, setters, etc.
}

आम्ही आधी म्हटल्याप्रमाणे, आमच्याकडे दोन स्टॅक आहेत: ड्रॉ डेक आणि टाकून दिलेला ढीग. Java मध्ये, स्टॅक डेटा स्ट्रक्चर क्लासमध्ये लागू केले जाते java.util.Stack. आमच्या कार्ड गेममध्ये 3 पद्धती आहेत ज्या खेळाडूंच्या क्रियांचे वर्णन करतात:

• डेकमधून कार्ड घ्या ( getCardFromDeck()पद्धत)
• कार्ड टाकून द्या ( discard()पद्धत)
• lookAtTopCard()शीर्ष कार्ड ( पद्धत) पहा . समजा हा एक "बुद्धीमत्ता" बोनस आहे जो खेळाडूला गेममध्ये पुढे कोणते कार्ड येईल हे शोधण्याची परवानगी देतो.

आमच्या पद्धतींमध्ये, आम्ही स्टॅक क्लासच्या खालील पद्धतींना कॉल करतो:

• push()— स्टॅकच्या शीर्षस्थानी एक आयटम जोडते. आम्ही टाकलेल्या ढिगाऱ्यावर कार्ड पाठवतो तेव्हा ते ढिगाऱ्याच्या वर जाते
• pop()— स्टॅकमधून वरचा घटक काढून टाकतो आणि परत करतो. ही पद्धत अशा क्रियांच्या अंमलबजावणीसाठी योग्य आहे ज्यामध्ये खेळाडू कार्ड काढतो.
• peek()— स्टॅकचा वरचा घटक परत करतो, परंतु स्टॅकमधून काढून टाकत नाही

आमचा गेम कसा कार्य करेल ते पाहूया:

import java.util.Stack;

public class Main3 {

   public static void main(String[] args) {

       // Create a deck and add cards to it
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Ragnaros"));
       deck.push(new Card("Patches the Pirate"));
       deck.push(new Card("Sylvanas Windrunner"));
       deck.push(new Card("Millhouse Manastorm"));
       deck.push (new Card ("Edwin VanCleef"));

       // Create the discard pile
       Stack<Card> discardPile = new Stack<>();

       // Start the game
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setDiscardPile(discardPile);

       // The first player draws 3 cards from the deck
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Which cards went to the first player?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       // The first player discards 3 of his cards
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("What cards are in the discard pile?");
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
   }
}

आम्ही आमच्या डेकमध्ये पाच कार्डे जोडली. पहिल्या खेळाडूने त्यापैकी 3 घेतले. तिला कोणते कार्ड मिळाले? कन्सोल आउटपुट:

Card{name='Edwin VanCleef"}
Card{name='Millhouse Manastorm'}
Card{name='Sylvanas Windrunner'}

कन्सोलवर कार्ड कोणत्या क्रमाने प्रदर्शित केले जातात त्याकडे लक्ष द्या. "एडविन व्हॅनक्लीफ" कार्ड शेवटच्या डेकमध्ये गेले (ते पाचवे कार्ड होते), आणि ते कार्ड खेळाडूने प्रथम काढले. "मिलहाऊस" डेकमध्ये शेवटचा दुसरा क्रमांक होता आणि खेळाडूने तो दुसरा काढला. "सिल्वेनास" वरच्या बाजूने तिसऱ्या क्रमांकावर गेला आणि खेळाडूने काढलेले ते तिसरे कार्ड होते. पुढे, खेळाडू कार्डे टाकून देतो. प्रथम, ती एडविन, नंतर मिलहाऊस, नंतर सिल्व्हानास टाकून देते. मग आम्ही आमच्या टाकलेल्या ढिगाऱ्यात एक एक करून कार्ड प्रदर्शित करतो: कन्सोल आउटपुट:

Card{name='Sylvanas Windrunner'}
Card{name='Millhouse Manastorm'}
Card{name='Edwin VanCleef"}

पुन्हा एकदा, स्टॅक कसे कार्य करते ते आम्ही पाहतो! आमच्या गेममध्ये, टाकून दिलेला ढीग देखील एक स्टॅक आहे (जसे ड्रॉ डेक प्रमाणे). "एडविन व्हॅनक्लीफ" प्रथम टाकून देण्यात आला. दुसरे कार्ड टाकून दिलेले मिलहाऊस मॅनस्टॉर्म होते आणि ते टाकून दिलेल्या ढिगाऱ्यात एडविनच्या वर ठेवले होते. मग सिल्व्हानास टाकून देण्यात आले आणि हे कार्ड मिलहाऊसच्या वर ठेवण्यात आले. जसे आपण पाहू शकता, स्टॅकमध्ये काहीही क्लिष्ट नाही. तरीही, तुम्हाला ही डेटा संरचना माहित असणे आवश्यक आहे — नोकरीच्या मुलाखती दरम्यान याबद्दल विचारले जाते आणि बहुतेकदा अधिक जटिल डेटा संरचना तयार करण्यासाठी हा आधार असतो.

जावा मध्ये रांग

रांग ही दुसरी सामान्य डेटा संरचना आहे. स्टॅक व्यतिरिक्त, Java सह अनेक प्रोग्रामिंग भाषा, रांग डेटा संरचना देखील लागू करतात. रांग आणि स्टॅकमध्ये काय फरक आहे? रांग LIFO तत्त्वावर आधारित नसून FIFO तत्त्वावर ("फर्स्ट इन, फर्स्ट आउट") आधारित असते. वास्तविक जीवनात, उदाहरणार्थ, एक सामान्य ओळ किंवा रांग लक्षात घेऊन हे तत्त्व समजणे सोपे आहे! उदाहरणार्थ, किराणा दुकानातील एक ओळ. जर ओळीत पाच लोक असतील, तर ज्याने प्रथम ओळीत प्रवेश केला तोच पहिला सर्व्ह केला जाईल . जर दुसर्‍या व्यक्तीला (आधीपासून रांगेत असलेल्या पाच व्यतिरिक्त) काहीतरी खरेदी करायचे असेल आणि तो रांगेत आला तर त्याला शेवटची सेवा दिली जाते, म्हणजे, सहावा. रांगेत काम करताना, शेपटीत (मागे) नवीन घटक जोडले जातात आणि जर तुम्हाला एखादे घटक मिळवायचे असतील तर ते डोक्यावरून (समोर) घेतले जातील. रांग कशी कार्य करते या संदर्भात हे मुख्य तत्व लक्षात ठेवणे आवश्यक आहे. रांगेचे ऑपरेशन खूप अंतर्ज्ञानी आहे, कारण आपल्याला वास्तविक जीवनात अनेकदा रांगा आढळतात. हे स्वतंत्रपणे लक्षात घेण्यासारखे आहे की जावामध्ये रांग वर्गाद्वारे नव्हे तर इंटरफेसद्वारे दर्शविली जाते: रांग. इतकेच काय, Java मध्ये या क्यू इंटरफेसची बरीच अंमलबजावणी आहेत. ओरॅकल डॉक्युमेंटेशन पाहिल्यास, आम्हाला दिसेल की 4 भिन्न इंटरफेस, तसेच वर्गांची एक अत्यंत प्रभावी यादी, रांग इंटरफेसचा वारसा घेतात:

All known subinterfaces

BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>

All known implementing classes

AbstractQueue, ArrayBlockingQueue, ArrayDeque

ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

PriorityBlockingQueue, PriorityQueue, SynchronousQueue

किती मोठी यादी! परंतु, अर्थातच, तुम्हाला हे सर्व वर्ग आणि इंटरफेस आत्ता लक्षात ठेवण्याची गरज नाही — तुमचे डोके फुटू शकते :) आम्ही फक्त काही महत्त्वाच्या आणि मनोरंजक मुद्द्यांचा विचार करू. प्रथम, रांगेच्या चार "सबइंटरफेस" पैकी एकाकडे लक्ष देऊ: Deque . काय ते इतके खास बनवते? A Dequeही दुहेरी टोक असलेली रांग आहे. हे नियमित रांगेची कार्यक्षमता वाढवते, ज्यामुळे तुम्हाला दोन्ही टोकांना (डोके आणि शेपटीला) घटक जोडता येतात आणि रांगेच्या दोन्ही टोकांपासून घटक घेता येतात. सॉफ्टवेअर डेव्हलपमेंटमध्ये डबल-एंडेड रांगा मोठ्या प्रमाणावर वापरल्या जातात. आम्ही वर प्रदान केलेल्या रांगेतील वर्गांच्या सूचीकडे लक्ष द्या. यादी बरीच मोठी आहे, पण त्यात काही परिचित आहे का?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

हा! हा आमचा जुना मित्र आहे LinkedList! तर, ते रांग इंटरफेस लागू करते? पण ती रांग कशी असू शकते? शेवटी, एक LinkedListलिंक केलेली यादी आहे! खरे आहे, परंतु ते रांग होण्यापासून थांबवत नाही :) ते लागू करत असलेल्या सर्व इंटरफेसची यादी येथे आहे:

All implemented interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>

जसे आपण पाहू शकता, इंटरफेस LinkedListलागू करते Deque(पुन्हा, याचा अर्थ डबल-एंडेड रांग). याची गरज का आहे? हे आम्हाला a च्या सुरुवातीपासून आणि शेवटपासून घटक मिळविण्यास अनुमती देते LinkedList. हे आम्हाला सुरुवातीस आणि शेवटी घटक जोडण्यास देखील अनुमती देते. LinkedListइंटरफेसमधून मिळणाऱ्या पद्धती येथे आहेत Deque:

• peekFirst()— पहिला घटक परत करतो (परंतु तो रांगेतून काढत नाही).
• peekLast()— शेवटचा घटक परत करतो (परंतु तो रांगेतून काढत नाही).
• pollFirst()— रांगेतील पहिला घटक परत करतो आणि काढून टाकतो.
• pollLast()— रांगेतील शेवटची वस्तू परत करते आणि काढून टाकते.
• addFirst()— रांगेच्या समोर एक नवीन आयटम जोडते.
• addLast()— रांगेच्या शेवटी एक आयटम जोडते.

तुम्ही बघू शकता, LinkedListडबल-एंडेड रांगेची कार्यक्षमता पूर्णपणे लागू करते! आणि तुम्हाला तुमच्या प्रोग्राममध्ये अशा कार्यक्षमतेची आवश्यकता आहे, ते कोठे शोधायचे ते तुम्हाला कळेल :) आजचा धडा संपत आहे. शेवटी, मी तुम्हाला अतिरिक्त वाचनासाठी काही दुवे देईन. प्रथम, PriorityQueue बद्दल या लेखाकडे लक्ष द्या . हे सर्वात मनोरंजक आणि उपयुक्त Queueअंमलबजावणींपैकी एक आहे. उदाहरणार्थ, समजा तुमच्या स्टोअरमध्ये ५० लोक रांगेत उभे आहेत आणि त्यापैकी ७ VIP ग्राहक आहेत. प्राधान्य रांग तुम्हाला प्रथम त्यांची सेवा करू देईल! खूप उपयुक्त सामग्री, बरोबर? :) दुसरे, रॉबर्ट लाफोर यांच्या "डेटा स्ट्रक्चर्स अँड अल्गोरिदम इन जावा" या पुस्तकाचा पुन्हा एकदा उल्लेख केल्याने त्रास होणार नाही.. हे पुस्तक वाचून, तुम्ही अनेक डेटा स्ट्रक्चर्स (स्टॅक आणि रांगेसह) शिकू शकाल, परंतु तुम्ही स्वतः त्यांपैकी अनेकांची अंमलबजावणी देखील कराल! उदाहरणार्थ, Java मध्ये स्टॅक क्लास नसेल तर? तुम्हाला तुमच्या प्रोग्रामसाठी अशा डेटा स्ट्रक्चरची आवश्यकता असल्यास तुम्ही काय कराल? तुम्हाला ते स्वतःच लिहावे लागेल, नक्कीच. जसे तुम्ही लाफोरचे पुस्तक वाचता , तुम्ही अनेकदा तेच कराल. परिणामी, डेटा स्ट्रक्चर्सची तुमची समज तुम्हाला सिद्धांताच्या साध्या अभ्यासातून मिळेल त्यापेक्षा खूप खोल असेल :) आम्ही आजसाठी सिद्धांत गुंडाळत आहोत, परंतु सरावशिवाय सिद्धांत काहीही नाही! कार्ये स्वतःच सोडवणार नाहीत, म्हणून त्यांना हाताळण्याची वेळ आली आहे! :)