جاوا میں ڈیٹا سٹرکچرز - اسٹیک اور قطار

ہیلو! آج ہم کسی بھی پروگرامر کے لیے ڈیٹا سٹرکچر جیسی اہم چیزوں کے بارے میں بات کریں گے ۔ ویکیپیڈیا کہتا ہے: ڈیٹا ڈھانچہ ( eng. ڈیٹا ڈھانچہ ) ایک سافٹ ویئر یونٹ ہے جو آپ کو کمپیوٹنگ میں ایک ہی قسم کے اور/یا منطقی طور پر متعلقہ ڈیٹا کو ذخیرہ کرنے اور اس پر کارروائی کرنے کی اجازت دیتا ہے۔ تعریف تھوڑی مبہم ہے، لیکن اس کا جوہر واضح ہے۔ ڈیٹا کا ڈھانچہ ایک قسم کا ذخیرہ ہے جہاں ہم مزید استعمال کے لیے ڈیٹا ذخیرہ کرتے ہیں۔ پروگرامنگ میں ڈیٹا ڈھانچے کی ایک بہت بڑی قسم ہے۔ اکثر، کسی خاص مسئلے کو حل کرتے وقت، سب سے اہم چیز اس مقصد کے لیے موزوں ترین ڈیٹا ڈھانچہ کا انتخاب کرنا ہے۔ اور آپ ان میں سے بہت سے لوگوں سے پہلے ہی واقف ہیں! مثال کے طور پر، arrays کے ساتھ ۔ اور اس کے ساتھ بھی Map(جس کا ترجمہ عام طور پر "لغت"، "نقشہ"، یا "ایسوسی ایٹو سرنی" کے طور پر کیا جاتا ہے)۔ یہ سمجھنا بہت ضروری ہے: ڈیٹا ڈھانچے کسی مخصوص زبان سے منسلک نہیں ہیں ۔ یہ صرف خلاصہ "بلیو پرنٹس" ہیں جن کے مطابق ہر پروگرامنگ لینگویج اپنی کلاسز بناتی ہے - اس ڈھانچے کے نفاذ۔ مثال کے طور پر، سب سے مشہور ڈیٹا ڈھانچے میں سے ایک منسلک فہرست ہے ۔ آپ ویکیپیڈیا پر جا کر پڑھ سکتے ہیں کہ یہ کیسے کام کرتا ہے، اس کے کیا فوائد اور نقصانات ہیں۔ آپ کو اس کی تعریف مانوس لگ سکتی ہے :) "ایک منسلک فہرست کمپیوٹر سائنس میں ایک بنیادی متحرک ڈیٹا ڈھانچہ ہے، جو نوڈس پر مشتمل ہے، جن میں سے ہر ایک خود ڈیٹا اور ایک یا دو لنکس ("لنک") پر مشتمل ہوتا ہے اور/یا پچھلی نوڈ لسٹ" تو یہ ہماری ہے LinkedList! بالکل، ایسا ہی ہے :) لنکڈ لسٹ ڈیٹا ڈھانچہ کلاس میں جاوا زبان میں لاگو ہوتا ہے LinkedList۔ لیکن دوسری زبانیں بھی منسلک فہرستوں کو نافذ کرتی ہیں! Python میں اسے " 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 {

   //  колода
   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 ("first in - first out"، "first in - first out") ۔ اسے سمجھنا آسان ہے، مثال کے طور پر... یا کم از کم ایک عام، حقیقی زندگی سے حقیقی قطار! مثال کے طور پر، دکان کے لیے ایک قطار۔ اگر لائن میں پانچ لوگ ہیں تو لائن میں پہلا شخص اسٹور میں داخل ہوگا ۔ اگر ایک اور شخص (لائن میں لگے پانچوں کے علاوہ) کوئی چیز خریدنا چاہتا ہے اور لائن میں لگ جاتا ہے، تو وہ دکان میں آخری یعنی چھٹے نمبر پر آتا ہے۔ قطار کے ساتھ کام کرتے وقت، آخر میں نئے عناصر شامل کیے جاتے ہیں، اور اگر آپ عنصر حاصل کرنا چاہتے ہیں، تو اسے شروع سے لیا جائے گا۔ یہ اس کے آپریشن کا بنیادی اصول ہے، جسے آپ کو یاد رکھنا چاہیے ۔ یہ الگ سے غور کرنے کے قابل ہے کہ جاوا میں ایک قطار کی نمائندگی کلاس کے ذریعہ نہیں بلکہ ایک انٹرفیس کے ذریعہ کی جاتی ہے Queue۔ لیکن ایک ہی وقت میں، جاوا میں ایک قطار ایک انٹرفیس ہے جس میں بہت سے نفاذ ہیں. اگر ہم اوریکل دستاویزات کو دیکھیں تو ہم دیکھیں گے کہ 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تو یہ آپ کو پہلے ان کی خدمت کرنے کی اجازت دے گا! ایک بہت مفید چیز، کیا آپ متفق نہیں ہیں؟ :) دوسری بات یہ کہ ایک بار پھر رابرٹ لافورٹ کی کتاب "Data Structures and Algorithms in Java" کا ذکر کرنا ضرورت سے زیادہ نہیں ہوگا ۔ کتاب کو پڑھتے ہوئے، آپ نہ صرف بہت سے ڈیٹا ڈھانچے (بشمول اسٹیک اور قطار) سیکھیں گے، بلکہ آپ ان میں سے بہت سے خود بھی لاگو کریں گے! مثال کے طور پر، تصور کریں کہ کیا جاوا میں Stack کلاس نہیں ہے۔ اگر آپ کو اپنے پروگرام کے لیے اس طرح کے ڈیٹا ڈھانچے کی ضرورت ہو تو آپ کیا کریں گے؟ یقیناً مجھے خود ہی لکھنا پڑے گا۔ Laforet کی کتاب پڑھتے وقت ، یہ اکثر آپ کیا کریں گے. اس کی بدولت، ڈیٹا کے ڈھانچے کے بارے میں آپ کی سمجھ صرف تھیوری کا مطالعہ کرنے سے کہیں زیادہ وسیع ہو جائے گی :) ہم آج کے لیے تھیوری کے ساتھ کام کر چکے ہیں، لیکن پریکٹس کے بغیر تھیوری کچھ بھی نہیں ہے! مسائل خود حل نہیں ہوں گے، لہذا اب ان سے نمٹنے کا وقت ہے! :)