डेटा संरचनाएं: ढेर और कतार

नमस्ते! आज हम उस बारे में बात करेंगे जो किसी भी प्रोग्रामर के लिए अति महत्वपूर्ण है: डेटा संरचनाएं। विकिपीडिया कहता है: "एक डेटा संरचना एक डेटा संगठन, प्रबंधन और भंडारण प्रारूप है जो कुशल पहुंच और संशोधन को सक्षम बनाता है। अधिक सटीक रूप से, एक डेटा संरचना डेटा मूल्यों का एक संग्रह है, उनके बीच संबंध और कार्य या संचालन जो हो सकते हैं डेटा पर लागू होता है।" परिभाषा थोड़ी भ्रमित करने वाली है, लेकिन इसका सार स्पष्ट है। डेटा संरचना एक प्रकार का रिपॉजिटरी है जहां हम भविष्य में उपयोग के लिए डेटा स्टोर करते हैं। प्रोग्रामिंग में, डेटा संरचनाओं की एक विशाल विविधता होती है। विशिष्ट समस्याओं को हल करते समय, समस्या के लिए सबसे उपयुक्त डेटा संरचना का चयन करना अक्सर सबसे महत्वपूर्ण बात होती है। और आप उनमें से बहुत से पहले से ही परिचित हैं! उदाहरण के लिए, आप सरणियों के बारे में जानते हैं। और आप भी परिचित हैंMap(इस डेटा संरचना को "शब्दकोश" या "सहयोगी सरणी" के रूप में भी संदर्भित किया जा सकता है)। यह समझना बहुत महत्वपूर्ण है कि डेटा संरचनाएं किसी विशेष भाषा से बंधी नहीं हैं। वे बस अमूर्त "ब्लूप्रिंट" हैं जो प्रत्येक प्रोग्रामिंग भाषा अपनी कक्षाएं बनाने या किसी विशेष संरचना के कार्यान्वयन के लिए उपयोग करती है। उदाहरण के लिए, सबसे प्रसिद्ध डेटा संरचनाओं में से एक लिंक की गई सूची है। आप विकिपीडिया पर जा सकते हैं और पढ़ सकते हैं कि यह कैसे काम करता है और इसके क्या फायदे और नुकसान हैं। शायद इसकी परिभाषा आपको परिचित लगेगी :) "एक लिंक की गई सूची डेटा तत्वों का एक रैखिक संग्रह है, जिसका क्रम मेमोरी में उनके भौतिक प्लेसमेंट द्वारा नहीं दिया जाता है। इसके बजाय, प्रत्येक तत्व अगले की ओर इशारा करता है।" यह हमारे प्यारे का वर्णन करता है LinkedList, है ना? हां, और बस यही है :) जावा में, "लिंक की गई सूची" डेटा संरचना LinkedListवर्ग द्वारा कार्यान्वित की जाती है। लेकिन अन्य भाषाएँ भी लिंक्ड सूचियों को लागू करती हैं! पायथन में, इस डेटा संरचना को " llist" कहा जाता है। स्काला में इसे LinkedListजावा की तरह ही "" कहा जाता है। एक लिंक की गई सूची बुनियादी सामान्य डेटा संरचनाओं में से एक है, इसलिए आप पाएंगे कि यह किसी भी आधुनिक प्रोग्रामिंग भाषा में लागू है। साहचर्य सरणियों के बारे में भी यही सच है। यहाँ विकिपीडिया से परिभाषा दी गई है: "एक साहचर्य सरणी, मानचित्र, प्रतीक तालिका, या शब्दकोश एक सार डेटा प्रकार है जो (कुंजी, मान) जोड़े के संग्रह से बना है, जैसे कि संग्रह में प्रत्येक संभावित कुंजी अधिकतम एक बार दिखाई देती है।" क्या यह आपको कुछ याद दिलाता है? :) हां। हमारे लिए जावा डेवलपर्स, एक साहचर्य सरणी हैMapइंटरफेस। लेकिन यह डेटा संरचना अन्य भाषाओं में भी लागू होती है! उदाहरण के लिए, C# प्रोग्रामर इसे "शब्दकोश" के नाम से जानते हैं। और रूबी में, इसे "हैश" नामक वर्ग में कार्यान्वित किया जाता है। ठीक है, आप बिंदु प्राप्त करते हैं: डेटा संरचनाएं प्रोग्रामिंग में सार्वभौमिक अवधारणाएं हैं, और प्रत्येक प्रोग्रामिंग भाषा उन्हें अपने तरीके से लागू करती है। आज हम ऐसी दो संरचनाओं - ढेर और कतार - का अध्ययन करेंगे और देखेंगे कि उन्हें जावा में कैसे कार्यान्वित किया जाता है।

जावा में ढेर

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

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.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"}

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

जावा में कतार

कतार एक अन्य सामान्य डेटा संरचना है। स्टैक के अलावा, जावा सहित कई प्रोग्रामिंग लैंग्वेज भी कतार डेटा संरचना को लागू करती हैं। क्यू और स्टैक में क्या अंतर है? एक कतार LIFO सिद्धांत पर आधारित नहीं है, बल्कि FIFO सिद्धांत ("पहले अंदर, पहले बाहर") पर आधारित है। इस सिद्धांत को वास्तविक जीवन में, उदाहरण के लिए, एक साधारण रेखा, या कतार पर विचार करके समझना आसान है! उदाहरण के लिए, किराने की दुकान पर एक लाइन। यदि लाइन में पांच लोग हैं, तो सबसे पहले उसे सर्व किया जाएगा, जिसने लाइन में सबसे पहले प्रवेश किया । यदि कोई अन्य व्यक्ति (पांच के अलावा पहले से ही लाइन में) कुछ खरीदना चाहता है और लाइन में लग जाता है, तो उसे अंतिम सेवा दी जाती है, यानी छठा। कतार के साथ काम करते समय, पूंछ (पीछे) में नए तत्व जोड़े जाते हैं, और यदि आप एक तत्व प्राप्त करना चाहते हैं, तो इसे सिर (सामने) से लिया जाएगा। कतार कैसे काम करती है, इसके बारे में आपको यह मुख्य सिद्धांत याद रखना चाहिए। एक कतार का संचालन बहुत सहज है, क्योंकि हम वास्तविक जीवन में अक्सर कतारें पाते हैं। यह अलग से ध्यान देने योग्य है कि जावा में एक कतार को एक वर्ग द्वारा नहीं, बल्कि एक इंटरफ़ेस द्वारा दर्शाया गया है: कतार। क्या अधिक है, जावा में इस कतार इंटरफ़ेस के बहुत सारे कार्यान्वयन हैं। यदि हम Oracle प्रलेखन को देखते हैं, तो हम देखेंगे कि 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एक डबल-एंडेड कतार है। यह एक नियमित कतार की कार्यक्षमता का विस्तार करता है, जिससे आप दोनों सिरों (सिर और पूंछ पर) में तत्व जोड़ सकते हैं और कतार के दोनों सिरों से तत्व ले सकते हैं। सॉफ्टवेयर विकास में डबल-एंडेड कतारों का व्यापक रूप से उपयोग किया जाता है। हमारे द्वारा ऊपर प्रदान की गई कतार कक्षाओं की सूची पर ध्यान दें। सूची काफी लंबी है, लेकिन क्या इसमें कुछ जाना-पहचाना है?

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डबल-एंडेड कतार की कार्यक्षमता को पूरी तरह से लागू करता है! और आपको अपने कार्यक्रम में ऐसी कार्यक्षमता की आवश्यकता है, आपको पता चल जाएगा कि इसे कहां खोजना है :) आज का पाठ समाप्त हो रहा है। अंत में, मैं आपको अतिरिक्त पढ़ने के लिए कुछ लिंक दूंगा। सबसे पहले, प्रायोरिटी क्यू के बारे में इस लेख पर ध्यान दें । यह सबसे दिलचस्प और उपयोगी Queueकार्यान्वयनों में से एक है। उदाहरण के लिए, मान लीजिए कि आपके स्टोर पर 50 लोग लाइन में इंतज़ार कर रहे हैं, और उनमें से 7 VIP ग्राहक हैं। एक प्रायोरिटी क्यू आपको पहले उनकी सेवा करने देगी! बहुत उपयोगी सामान, है ना? :) दूसरा, यह एक बार फिर से रॉबर्ट लाफोर की पुस्तक "डेटा स्ट्रक्चर्स एंड एल्गोरिदम इन जावा" का उल्लेख करने के लिए चोट नहीं पहुंचाएगा।. इस पुस्तक को पढ़कर, आप न केवल कई डेटा संरचनाएँ सीखेंगे (स्टैक और कतार सहित), बल्कि आप उनमें से कई को स्वयं लागू भी करेंगे! उदाहरण के लिए, क्या होगा यदि जावा में स्टैक क्लास नहीं है? यदि आपको अपने प्रोग्राम के लिए ऐसी डेटा संरचना की आवश्यकता हो तो आप क्या करेंगे? आपको इसे स्वयं लिखना होगा, निश्चित रूप से। जैसा कि आप लाफोर की किताब पढ़ते हैं , आप अक्सर ऐसा ही करेंगे। नतीजतन, डेटा संरचनाओं की आपकी समझ सिद्धांत के एक साधारण अध्ययन से आपको जो मिलेगी उससे कहीं अधिक गहरी होगी :) हम आज के लिए सिद्धांत को लपेट रहे हैं, लेकिन अभ्यास के बिना सिद्धांत कुछ भी नहीं है! कार्य अपने आप हल नहीं होंगे, इसलिए उनसे निपटने का समय आ गया है! :)