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

سلام! اڄ اسان ڪنهن به پروگرامر لاءِ اهڙين اهم شين بابت ڳالهائينداسين جيئن ڊيٽا جي جوڙجڪ . Wikipedia چوي ٿو: Data structure ( eng. data structure ) هڪ سافٽ ويئر يونٽ آهي جيڪو توهان کي ڪمپيوٽنگ ۾ ساڳئي قسم ۽/يا منطقي طور تي لاڳاپيل ڊيٽا کي ذخيرو ۽ پروسيس ڪرڻ جي اجازت ڏئي ٿو. وصف ٿورو مونجهارو آهي، پر ان جو جوهر واضح آهي. ڊيٽا جي جوڙجڪ هڪ قسم جي اسٽوريج آهي جتي اسان ڊيٽا کي وڌيڪ استعمال لاء ذخيرو ڪندا آهيون. پروگرامنگ ۾ ڊيٽا جي جوڙجڪ جي هڪ وڏي قسم آهن. گهڻو ڪري، جڏهن هڪ خاص مسئلي کي حل ڪرڻ، سڀ کان اهم شيء هن مقصد لاء سڀ کان وڌيڪ مناسب ڊيٽا جي جوڙجڪ کي چونڊڻ آهي. ۽ توھان انھن مان گھڻن کان اڳ ۾ ئي واقف آھيو! مثال طور، arrays سان . ۽ ان سان گڏ Map(جنهن کي عام طور تي ترجمو ڪيو ويندو آهي "لغت"، "نقشو"، يا "ملڪي صف"). اهو سمجهڻ تمام ضروري آهي: ڊيٽا جي جوڙجڪ ڪنهن مخصوص ٻولي سان ڳنڍيل نه آهن . اهي صرف خلاصا آهن ”بليو پرنٽس“ جن جي مطابق هر پروگرامنگ ٻولي پنهنجو طبقو ٺاهي ٿي - هن ڍانچي تي عمل درآمد. مثال طور، سڀ کان وڌيڪ مشهور ڊيٽا جي جوڙجڪ مان هڪ آهي ڳنڍيل فهرست . توھان وڪيپيڊيا ڏانھن وڃو، پڙھو ته اھو ڪيئن ڪم ڪري ٿو، ان جا ڪهڙا فائدا ۽ نقصان آھن. توھان کي معلوم ٿي سگھي ٿو ته ان جي وصف واقف آھي :) “هڪ ڳنڍيل لسٽ ڪمپيوٽر سائنس ۾ ھڪ بنيادي متحرڪ ڊيٽا جو ڍانچو آھي، جنھن ۾ نوڊس شامل آھن، جن مان ھر ھڪ پاڻ ۾ ڊيٽا ۽ ھڪ يا ٻه لنڪ (“لنڪس”) ٻئي ۽/يا پوئين نوڊ لسٽ“ پوءِ هي اسان جو آهي LinkedList! بلڪل ائين ئي آهي :) جڙيل لسٽ ڊيٽا جي جوڙجڪ جاوا ٻوليءَ ۾ ڪلاس ۾ لاڳو ڪئي وئي آهي LinkedList. پر ٻيون ٻوليون پڻ ڳنڍيل لسٽون لاڳو ڪن ٿيون! پٿون ۾ ان کي سڏيو ويندو آهي " llist"، اسڪالا ۾ اهو ساڳيو سڏيو ويندو آهي جيئن جاوا ۾ - " LinkedList". هڪ ڳنڍيل فهرست بنيادي عام ڊيٽا جي جوڙجڪ مان هڪ آهي، تنهنڪري توهان ڪنهن به جديد پروگرامنگ ٻولي ۾ ان جي نفاذ کي ڳولي سگهو ٿا. ساڳي شيء هڪ ساٿي صف سان. هتي وڪيپيڊيا مان ان جي تعريف آهي: هڪ associative array هڪ خلاصي ڊيٽا جو قسم آهي (ڊيٽا اسٽور لاءِ هڪ انٽرفيس) جيڪو فارم جي جوڙن کي محفوظ ڪرڻ جي اجازت ڏئي ٿو “(key, value)” ۽ هڪ جوڙي کي شامل ڪرڻ جي عملن کي سپورٽ ڪري ٿو، انهي سان گڏ ڳولا ۽ چاٻي ذريعي هڪ جوڙي کي حذف ڪرڻ. ڇا توهان کي ڪجهه به ياد نه ٿو اچي؟ :) بلڪل، اسان لاءِ جاواسٽ، هڪ ايسوسيئيٽو صف هڪ انٽرفيس آهي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 {

   //  колода
   private Stack<Card> deck;

   //  сброс
   private Stack<Card> graveyard;

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

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

   public Card lookTopCard() {

       return deck.peek();
   }

   //  ..геттеры, сеттеры и т.д.
}

جيئن اسان اڳ ۾ چيو آهي، اسان وٽ ٻه اسٽيڪ آهن: ڊيڪ ۽ رد ڪريو. اسٽيڪ ڊيٽا جي جوڙجڪ جاوا ۾ java.util.Stack. اسان جي ڪارڊ جي راند ۾ 3 طريقا آھن جيڪي رانديگرن جي عملن کي بيان ڪن ٿا:

• ڊيڪ مان هڪ ڪارڊ وٺو (طريقو getCardFromDeck())؛
• ڪارڊ رد ڪريو (طريقو discard())؛
• مٿين ڪارڊ کي ڏسو (طريقو lookTopCard()). اچو ته چئو ته هي بونس ميڪيڪل "انٽيليجنس" هوندو، جيڪو پليئر کي اهو معلوم ڪرڻ جي اجازت ڏيندو ته ڪهڙو ڪارڊ اڳتي هلي راند ۾ ايندو.

اسان جي طريقن جي اندر، طبقاتي طريقن کي سڏيو ويندو آهي Stack:

• push()- اسٽيڪ جي چوٽي تي ھڪڙو عنصر شامل ڪري ٿو. جڏهن اسان هڪ ڪارڊ رد ڪريون ٿا، اهو اڳئين رد ٿيل ڪارڊ جي مٿان وڃي ٿو.
• pop()- اسٽيڪ مان مٿين عنصر کي هٽائي ٿو ۽ ان کي واپس ڪري ٿو. اهو طريقو مثالي آهي لاڳو ڪرڻ لاءِ ”پليئر ڪارڊ ٺاهي ٿو“ ميڪنڪ.
• peek()- اسٽيڪ جي مٿين عنصر کي واپس ڏئي ٿو، پر ان کي اسٽيڪ مان نه هٽايو

اچو ته ڏسون ته اسان جي راند ڪيئن ڪم ڪندي:

import java.util.Stack;

public class Main3 {

   public static void main(String[] args) {

       //  создаем колоду и добавляем в нее карты
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Рагнарос"));
       deck.push(new Card("Пират Глазастик"));
       deck.push(new Card("Сильвана Ветрокрылая"));
       deck.push(new Card("Миллхаус Манашторм"));
       deck.push(new Card("Эдвин ван Клифф"));

       //  создаем сброс
       Stack<Card> graveyard = new Stack<>();

       //  начинаем игру
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setGraveyard(graveyard);

       //  первый игрок берет 3 карты из колоды
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Какие карты достались первому игроку?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       //  первый игрок отправляет в сброс 3 своих карты
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("Какие карты находятся в сбросе?");
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
   }
}

تنهنڪري اسان پنهنجي ڊيڪ تي پنج ڪارڊ شامل ڪيا آهن. پهرين رانديگر انهن مان 3 ورتو. هن کي ڪهڙا ڪارڊ مليا؟ ڪنسول آئوٽ:

Card{name='Эдвин ван Клифф'}
Card{name='Миллхаус Манашторм'}
Card{name='Сильвана Ветрокрылая'}

آرڊر تي ڌيان ڏيو جنهن ۾ ڪارڊ ڪنسول ڏانهن ٻاھر نڪتا. "ايڊون وان ڪليف" ڪارڊ ڊيڪ کي مارڻ لاءِ آخري هو (پنجون قطار ۾)، ۽ اهو ڪارڊ هو جيڪو پليئر پهريون ڀيرو ورتو. "Michhlaus" مارو ڊيڪ سيڪنڊ کي آخري، ۽ ان جي پليئر ان کي سيڪنڊ ورتو. "Sylvanas" آخر کان ٽيون ڊيڪ ماريو، ۽ ٽئين پليئر ڏانهن ويو. اڳيون، پليئر سندس ڪارڊ رد ڪري ٿو. پهرين هو ايڊون کي ڇڏي ٿو، پوءِ مل هائوس، پوءِ سلواناس. جنهن کان پوءِ اسان هڪ هڪ ڪري ڪنسول ڏانهن آئوٽ ڪريون ٿا اهي ڪارڊ جيڪي اسان جي رد ۾ آهن: ڪنسول ڏانهن آئوٽ:

Card{name='Сильвана Ветрокрылая'}
Card{name='Миллхаус Манашторм'}
Card{name='Эдвин ван Клифф'}

۽ ٻيهر اسان ڏسون ٿا ته اسٽيڪ ڪيئن ڪم ڪري ٿو! اسان جي راند ۾ رد پڻ هڪ اسٽيڪ آهي (جيئن ڊيڪ وانگر). "ايڊون وان ڪليف" پهريون ڀيرو ڪڍيو ويو. ٻيو جنهن کي ڇڏيو ويو هو ”مِل هاؤس مينسٽارم“ هو - ۽ ردي ۾ ايڊون جي چوٽي تي ليٽيو ويو. اڳتي هلي، سلواناس کي رد ڪيو ويو - ۽ اهو ڪارڊ مل هائوس جي چوٽي تي رکيل هو. جئين توهان ڏسي سگهو ٿا، ڪجھ به پيچيده ناهي ته اسٽيڪ ڪيئن ڪم ڪري ٿو. بهرحال، اهو ضروري آهي ته هن ڊيٽا جي جوڙجڪ کي ڄاڻڻ ضروري آهي - اهو اڪثر انٽرويو ۾ پڇيو ويندو آهي، ۽ وڌيڪ پيچيده ڊيٽا جي جوڙجڪ اڪثر ڪري ان جي بنياد تي ٺهيل آهن.

قطار

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

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

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