ڊيٽا جي جوڙجڪ: اسٽيڪ ۽ قطار

سلام اڄ اسان ڪنهن به شيءِ بابت ڳالهائينداسين جيڪا ڪنهن به پروگرامر لاءِ انتهائي اهم آهي: ڊيٽا جي جوڙجڪ. Wikipedia چوي ٿو: "هڪ ڊيٽا جو ڍانچو هڪ ڊيٽا آرگنائيزيشن، انتظام، ۽ اسٽوريج فارميٽ آهي جيڪو موثر رسائي ۽ ترميم کي قابل بڻائي ٿو. وڌيڪ واضح طور تي، ڊيٽا جي جوڙجڪ ڊيٽا جي قدرن جو هڪ مجموعو آهي، انهن جي وچ ۾ لاڳاپا، ۽ افعال يا عمل جيڪي ٿي سگهن ٿيون. ڊيٽا تي لاڳو ڪيو ويو آهي." وصف ٿورڙي مونجهارو آهي، پر ان جو خلاصو واضح آهي. ڊيٽا جي جوڙجڪ هڪ قسم جو مخزن آهي جتي اسان مستقبل جي استعمال لاءِ ڊيٽا محفوظ ڪندا آهيون. پروگرامنگ ۾، ڊيٽا جي جوڙجڪ جي هڪ وڏي قسم آهن. جڏهن مخصوص مسئلن کي حل ڪرڻ، اڪثر ڪري سڀ کان اهم شيء اهو آهي ته مسئلي لاء سڀ کان وڌيڪ مناسب ڊيٽا جي جوڙجڪ کي چونڊيو وڃي. ۽ توھان انھن مان گھڻن کان اڳ ۾ ئي واقف آھيو! مثال طور، توهان arrays بابت ڄاڻو ٿا. ۽ توهان ان سان پڻ واقف آهيو Map(هن ڊيٽا جي جوڙجڪ کي "لغت" يا "ملڪي صف" جي طور تي حوالو پڻ ڏئي سگهجي ٿو). اهو سمجهڻ تمام ضروري آهي ته ڊيٽا جي جوڙجڪ ڪنهن خاص ٻولي سان ڳنڍيل نه آهن. اهي صرف خلاصا آهن "بليو پرنٽ" جيڪي هر پروگرامنگ ٻولي پنهنجي طبقن ٺاهڻ يا هڪ خاص ڍانچي تي عمل ڪرڻ لاء استعمال ڪندا آهن. مثال طور، سڀ کان وڌيڪ مشهور ڊيٽا جي جوڙجڪ مان هڪ ڳنڍيل فهرست آهي. توهان وڪيپيڊيا تي وڃي سگهو ٿا ۽ پڙهي سگهو ٿا ته اهو ڪيئن ڪم ڪري ٿو ۽ ان جا ڪهڙا فائدا ۽ نقصان آهن. ٿي سگهي ٿو ته ان جي وصف توهان کي واقف هجي :) "هڪ ڳنڍيل فهرست ڊيٽا عناصر جو هڪ لڪير مجموعو آهي، جنهن جي ترتيب ياداشت ۾ انهن جي جسماني جاء تي ترتيب نه ڏني وئي آهي. ان جي بدران، هر عنصر ايندڙ ڏانهن اشارو ڪري ٿو." اهو اسان جي محبوب کي بيان ڪري ٿو LinkedList، ڇا اهو ناهي؟ ها، ۽ اهو صرف اهو ئي آهي :) جاوا ۾، "ڳنڍيل فهرست" ڊيٽا جي جوڙجڪ طبقي طرفان لاڳو ڪئي وئي آهي LinkedList. پر ٻيون ٻوليون پڻ ڳنڍيل لسٽون لاڳو ڪن ٿيون! پٿون ۾، هن ڊيٽا جي جوڙجڪ کي " llist" سڏيو ويندو آهي. اسڪالا ۾ ان کي " LinkedList" سڏيو ويندو آهي، جهڙوڪ جاوا ۾. هڪ ڳنڍيل فهرست بنيادي عام ڊيٽا جي جوڙجڪ مان هڪ آهي، تنهنڪري توهان کي اهو معلوم ٿيندو ته اهو ڪنهن به جديد پروگرامنگ ٻولي ۾ لاڳو ٿئي ٿو. ساڳي شيءِ associative arrays جي به صحيح آهي. هتي وڪيپيڊيا جي وصف آهي: "هڪ ايسوسيئيٽو صف، نقشو، علامت ٽيبل، يا ڊڪشنري هڪ خلاصي ڊيٽا جو قسم آهي، جيڪو (ڪي، قدر) جوڑوں جي مجموعن تي مشتمل هوندو آهي، جيئن ته هر ممڪن ڪيئي مجموعي ۾ هڪ ڀيرو ئي ظاهر ٿئي." ڇا اهو توهان کي ڪجهه ياد ڏياريندو آهي؟ :) جي. اسان لاءِ جاوا ڊولپرز، هڪ ايسوسيئيٽو صف آهيMapانٽرفيس. پر هي ڊيٽا ڍانچي ٻين ٻولين ۾ پڻ لاڳو ڪيو ويو آهي! مثال طور، سي # پروگرامر ان کي "ڊڪشنري" جي نالي سان ڄاڻن ٿا. ۽ روبي ۾، اهو "هيش" نالي هڪ طبقي ۾ لاڳو ٿئي ٿو. خير، توهان نقطي حاصل ڪريو: ڊيٽا جي جوڙجڪ پروگرامنگ ۾ عالمگير تصورات آهن، ۽ هر پروگرامنگ ٻولي انهن کي پنهنجي طريقي سان لاڳو ڪري ٿي. اڄ اسان ٻه اهڙيون اڏاوتون پڙهنداسين - اسٽيڪ ۽ قطار - ۽ ڏسو ته اهي جاوا ۾ ڪيئن لاڳو ٿين ٿيون.

جاوا ۾ اسٽيڪ

هڪ اسٽيڪ هڪ معروف ڊيٽا جي جوڙجڪ آهي. اهو تمام سادو آهي. اسان جي روزاني زندگي ۾ ڪافي ڪجھ شيون "لاڳو" هڪ اسٽيڪ جي طور تي آهن. تصور ڪريو ھن سادي صورتحال: توھان ھڪڙي ھوٽل ۾ رھيا آھيو، ۽ ڏينھن جي دوران توھان کي ڪجھ ڪاروباري خط مليا. تون ان وقت پنهنجي ڪمري ۾ نه هئين، تنهن ڪري هوٽل جي ڪلارڪ رڳو توهان جي ڊيسڪ تي ايندڙ اکر رکيا. پهرين، هن پهريون خط ميز تي رکيو. پوءِ ٻيو خط آيو، ۽ ان کي پهرين جي چوٽيءَ تي رکيائين. هن ٽيون اکر ٻئي جي مٿي تي رکيو، ۽ چوٿين کي ٽئين جي مٿي تي. ۽ هاڻي، هڪ سادي سوال جو جواب ڏيو: جڏهن توهان پنهنجي ڪمري ۾ واپس اچو ۽ ٽيبل تي اسٽيڪ ڏسو ته توهان پهريون خط پڙهو ؟ صحيح، توهان مٿين خط کي پڙهي سگهندا . اهو آهي، جيڪو تازو آيو آهي . اهو بلڪل آهي ڪيئن هڪ اسٽيڪ ڪم ڪري ٿو. ان اصول کي ”لاسٽ ان فرسٽ آئوٽ“ (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 . ڇا ان کي ايترو خاص بڻائي ٿو؟ 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(ٻيهر، هن جو مطلب آهي ڊبل ختم ٿيل قطار). اها ضرورت ڇو آهي؟ هي اسان کي هڪ جي شروعات ۽ آخر کان عناصر حاصل ڪرڻ جي اجازت ڏئي ٿو LinkedList. اهو پڻ اسان کي عناصر شامل ڪرڻ جي اجازت ڏئي ٿو شروعات ۽ آخر ۾. هتي اهي طريقا آهن جيڪي انٽرفيس LinkedListمان حاصل ٿين ٿا Deque:

• peekFirst()- پهريون عنصر واپس آڻيندو (پر ان کي قطار مان نه هٽايو).
• peekLast()- آخري عنصر موٽائي ٿو (پر ان کي قطار مان نه هٽايو).
• pollFirst()- قطار مان پھريون عنصر موٽائي ٿو ۽ ان کي ختم ڪري ٿو.
• pollLast()- قطار مان آخري شيون واپس ڪري ٿو ۽ ان کي هٽائي ٿو.
• addFirst()- قطار جي سامهون هڪ نئين شيء شامل ڪري ٿو.
• addLast()- قطار جي آخر ۾ ھڪڙي شيء شامل ڪري ٿو.

جئين توهان ڏسي سگهو ٿا، LinkedListمڪمل طور تي ڊبل ختم ٿيل قطار جي ڪارڪردگي کي لاڳو ڪري ٿو! ۽ توهان کي پنهنجي پروگرام ۾ اهڙي فنڪشنلٽي جي ضرورت آهي، توهان کي خبر پوندي ته ان کي ڪٿي ملندو :) اڄ جو سبق ختم ٿي رهيو آهي. آخر ۾، مان توهان کي اضافي پڙهڻ لاءِ ڪجهه لنڪ ڏيندس. پهرين، هن مضمون ڏانهن ڌيان ڏيو PriorityQueue بابت . اهو سڀ کان وڌيڪ دلچسپ ۽ مفيد عملن مان هڪ آهي Queue. مثال طور، فرض ڪريو ته 50 ماڻهو توهان جي اسٽور تي قطار ۾ انتظار ڪري رهيا آهن، ۽ انهن مان 7 VIP گراهڪ آهن. هڪ ترجيحي قطار توهان کي انهن جي پهرين خدمت ڪرڻ جي اجازت ڏيندو! تمام مفيد شيون، صحيح؟ :) ٻيو، اهو هڪ ڀيرو ٻيهر رابرٽ لافور جي ڪتاب "جاوا ۾ ڊيٽا جي جوڙجڪ ۽ الگورتھم" جو ذڪر ڪرڻ ڏکيو نه ٿيندو . هن ڪتاب کي پڙهڻ سان، توهان نه صرف ڪيترن ئي ڊيٽا جي جوڙجڪ کي سکندا (جنهن ۾ اسٽيڪ ۽ قطار شامل آهن)، پر توهان انهن مان ڪيترن کي پاڻ به لاڳو ڪندا! مثال طور، ڇا جيڪڏهن جاوا وٽ اسٽيڪ ڪلاس نه هجي؟ جيڪڏهن توهان کي پنهنجي پروگرام لاءِ اهڙي ڊيٽا جي جوڙجڪ جي ضرورت هجي ته توهان ڇا ڪندا؟ توهان کي اهو ضرور لکڻو پوندو. جيئن توهان Lafore جو ڪتاب پڙهو ، توهان اڪثر ڪري ائين ڪندا. نتيجي طور، ڊيٽا جي جوڙجڪ بابت توهان جي سمجھڻ جي ڀيٽ ۾ تمام گهڻي گهڻي هوندي جيڪا توهان نظريي جي هڪ سادي مطالعي مان حاصل ڪندا :) اسان اڄ تائين نظريي کي ختم ڪري رهيا آهيون، پر عمل کان سواء نظريو ڪجهه به ناهي! ڪم پاڻ کي حل نه ڪندا، تنهنڪري اهو انهن کي منهن ڏيڻ جو وقت آهي! :)