ڈیٹا ڈھانچے: اسٹیک اور قطار

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

اس ترتیب پر توجہ دیں جس میں کارڈز کنسول پر دکھائے جاتے ہیں۔ "Edwin VanCleef" کارڈ آخری بار ڈیک میں گیا (یہ پانچواں کارڈ تھا)، اور یہ وہ کارڈ تھا جسے کھلاڑی نے پہلے ڈرا کیا۔ "مل ہاؤس" ڈیک میں آخری نمبر پر تھا، اور کھلاڑی نے اسے دوسرے نمبر پر کھینچ لیا۔ "Sylvanas" اوپر سے تیسرے نمبر پر چلا گیا، اور یہ تیسرا کارڈ تھا جو کھلاڑی نے ڈرا کیا۔ اگلا، کھلاڑی کارڈز کو ضائع کر دیتا ہے۔ سب سے پہلے، وہ ایڈون، پھر مل ہاؤس، پھر سلواناس کو مسترد کرتی ہے۔ پھر ہم کارڈز کو اپنے ڈسکارڈ پائل میں ایک ایک کرکے ڈسپلے کرتے ہیں: کنسول آؤٹ پٹ:

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

ایک بار پھر، ہم دیکھتے ہیں کہ اسٹیک کیسے کام کرتا ہے! ہمارے کھیل میں، ڈسکارڈ پائل بھی ایک اسٹیک ہے (بالکل ڈرا ڈیک کی طرح)۔ "ایڈون وین کلیف" کو پہلے رد کر دیا گیا تھا۔ دوسرا کارڈ ڈسکارڈ مل ہاؤس مینسٹورم تھا، اور اسے ردی کے ڈھیر میں ایڈون کے اوپر رکھا گیا تھا۔ پھر سلوینس کو ضائع کر دیا گیا، اور یہ کارڈ مل ہاؤس کے اوپر رکھا گیا۔ جیسا کہ آپ دیکھ سکتے ہیں، اسٹیک کے بارے میں کچھ بھی پیچیدہ نہیں ہے۔ پھر بھی، آپ کو اس ڈیٹا ڈھانچے کو جاننے کی ضرورت ہے — اس کے بارے میں اکثر ملازمت کے انٹرویو کے دوران پوچھا جاتا ہے، اور یہ اکثر ڈیٹا کے زیادہ پیچیدہ ڈھانچے کی تعمیر کی بنیاد ہوتا ہے۔

جاوا میں قطار

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