هياكل البيانات في جافا - المكدس وقائمة الانتظار

مرحبًا! سنتحدث اليوم عن أشياء مهمة لأي مبرمج مثل هياكل البيانات . تقول ويكيبيديا: بنية البيانات ( eng. بنية البيانات ) هي وحدة برمجية تسمح لك بتخزين ومعالجة الكثير من نفس النوع و/أو البيانات المرتبطة منطقيًا في الحوسبة. التعريف مربك بعض الشيء، ولكن جوهره واضح. بنية البيانات هي نوع من التخزين حيث نقوم بتخزين البيانات لاستخدامها مرة أخرى. هناك مجموعة كبيرة ومتنوعة من هياكل البيانات في البرمجة. في كثير من الأحيان، عند حل مشكلة معينة، فإن الشيء الأكثر أهمية هو اختيار بنية البيانات الأكثر ملاءمة لهذا الغرض. وأنت بالفعل على دراية بالعديد منهم! على سبيل المثال، مع المصفوفات . وأيضًا مع Map(والتي تُترجم عادةً باسم "القاموس" أو "الخريطة" أو "المصفوفة النقابية"). من المهم جدًا أن نفهم: هياكل البيانات ليست مرتبطة بأي لغة محددة . هذه مجرد "مخططات" مجردة تقوم بموجبها كل لغة برمجة بإنشاء فئاتها الخاصة - تطبيقات هذه البنية. على سبيل المثال، إحدى هياكل البيانات الأكثر شهرة هي القائمة المرتبطة . يمكنك الذهاب إلى ويكيبيديا والقراءة عن كيفية عملها وما هي مزاياها وعيوبها. قد تجد تعريفها مألوفًا :) "القائمة المرتبطة هي بنية بيانات ديناميكية أساسية في علوم الكمبيوتر، وتتكون من عقد، تحتوي كل منها على البيانات نفسها ورابط واحد أو رابطين ("روابط") إلى التالي و/أو قائمة العقد السابقة" إذن هذه هي قائمتنا LinkedList! بالضبط، هذا هو الحال :) يتم تنفيذ بنية بيانات القائمة المرتبطة بلغة Java في الفصل LinkedList. لكن اللغات الأخرى تنفذ أيضًا قوائم مرتبطة! في بايثون يطلق عليه " llist"، في سكالا يطلق عليه نفس الشيء كما في جافا - " LinkedList". تعد القائمة المرتبطة إحدى هياكل البيانات الأساسية الشائعة، لذا يمكنك العثور على تنفيذها في أي لغة برمجة حديثة. نفس الشيء مع مجموعة النقابي. هنا تعريفها من ويكيبيديا: المصفوفة النقابية هي نوع بيانات مجردة (واجهة لمخزن البيانات) تسمح بتخزين أزواج من النموذج "(مفتاح، قيمة)" وتدعم عمليات إضافة زوج، وكذلك البحث وحذف الزوج بالمفتاح. لا يذكرك بأي شيء؟ :) بالضبط، بالنسبة لنا نحن الجاويين، المصفوفة الترابطية هي واجهةMap. ولكن يتم تنفيذ بنية البيانات هذه بلغات أخرى أيضًا! على سبيل المثال، يعرفه مبرمجو C# تحت اسم "القاموس". وفي لغة روبي يتم تنفيذه في فئة تسمى "Hash". بشكل عام، أنت تفهم تقريبًا ما هو المعنى: بنية البيانات هي شيء مشترك بين جميع البرمجة، ويتم تنفيذها بشكل مختلف في كل لغة محددة. سندرس اليوم هيكلين من هذا القبيل ونرى كيف يتم تنفيذهما في Java - المكدس وقائمة الانتظار.

كومة في جافا

المكدس عبارة عن بنية بيانات معروفة. إنه أمر بسيط للغاية ويتم "تنفيذ" الكثير من الأشياء من حياتنا اليومية كمجموعة. تخيل موقفًا بسيطًا: أنت تعيش في فندق، وخلال النهار تتلقى رسائل عمل. نظرًا لأنك لم تكن في الغرفة في ذلك الوقت، قام موظف الفندق ببساطة بوضع الرسائل الواردة على طاولتك. أولا وضع الحرف الأول على الطاولة. ثم جاء الثاني فوضعه فوق الأول. فوضع الحرف الثالث الذي وصل فوق الثاني، والرابع فوق الثالث. الآن، أجب عن سؤال بسيط: ما هو الحرف الذي ستقرأه أولاً عندما تأتي إلى غرفتك وترى كومة على الطاولة؟ هذا صحيح، سوف تقرأ الحرف العلوي . وهذا هو، الذي جاء في الوقت المناسب . هذا هو بالضبط كيف يعمل المكدس. يُطلق على مبدأ التشغيل هذا اسم LIFO - "آخر ما يدخل - يخرج أولاً" ("آخر ما يدخل يخرج أولاً"). ما الذي يمكن أن يكون مفيدًا للمكدس؟ على سبيل المثال، أنت تقوم بإنشاء نوع من ألعاب الورق في Java. توجد مجموعة من البطاقات على الطاولة. يتم التخلص من البطاقات التي تم لعبها. يمكنك تنفيذ كلا من المجموعة والتخلص باستخدام مكدسين. يقوم اللاعبون بسحب البطاقات من أعلى المجموعة - وهو نفس المبدأ المتبع مع الحروف. عندما يتخلص اللاعبون من البطاقات، يتم وضع بطاقات جديدة فوق البطاقات القديمة. إليك ما ستبدو عليه المسودة الأولى للعبتنا، والتي تم تنفيذها باستخدام المكدس:

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 في ملف java.util.Stack. توجد في لعبة الورق الخاصة بنا ثلاث طرق تصف تصرفات اللاعبين:

• خذ بطاقة من سطح السفينة (الطريقة 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='Сильвана Ветрокрылая'}

انتبه إلى الترتيب الذي تم به إخراج البطاقات إلى وحدة التحكم. كانت بطاقة "Edwin Van Cleiff" هي آخر بطاقة وصلت إلى المجموعة (الخامسة على التوالي)، وكانت البطاقة التي حصل عليها اللاعب أولاً. ضرب "ميخلاوس" سطح السفينة من المركز الثاني إلى الأخير، وحصل لاعبه على المركز الثاني. ضرب "سيلفاناس" المجموعة الثالثة من النهاية وذهب إلى اللاعب الثالث. بعد ذلك، يتخلص اللاعب من أوراقه. أولاً يسقط إدوين، ثم ميلهاوس، ثم سيلفاناس. بعد ذلك نقوم بإخراج البطاقات الموجودة في وحدة التحكم واحدًا تلو الآخر: الإخراج إلى وحدة التحكم:

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

ومرة أخرى نرى كيف يعمل المكدس! يعتبر الرمي في لعبتنا أيضًا مكدسًا (تمامًا مثل المجموعة). كان "Edwin Van Clyffe" أول من تم إسقاطه. ثاني قطعة تم إسقاطها كانت "Millhouse Manastorm" - وتم وضعها فوق Edwin في سلة المهملات. بعد ذلك، تم التخلص من Sylvanas - ووضعت هذه البطاقة فوق Millhouse. كما ترون، لا يوجد شيء معقد حول كيفية عمل المكدس. ومع ذلك، من الضروري معرفة بنية البيانات هذه - غالبًا ما يتم السؤال عنها في المقابلات، وغالبًا ما يتم بناء هياكل بيانات أكثر تعقيدًا على أساسها.

طابور

قائمة الانتظار (أو، باللغة الإنجليزية، "قائمة الانتظار") هي بنية بيانات شائعة أخرى. تمامًا مثل المكدس، يتم تنفيذه في العديد من لغات البرمجة، بما في ذلك Java. ما هو الفرق بين قائمة الانتظار والمكدس؟ قائمة الانتظار الخاصة بها لا تعتمد على LIFO، ولكن على مبدأ آخر - FIFO ("أولاً يدخل - يخرج أولاً"، "أولاً يدخل - يخرج أولاً") . من السهل أن نفهم ذلك، إذا أخذنا كمثال... أو على الأقل قائمة انتظار عادية وحقيقية من الحياة الواقعية! على سبيل المثال، قائمة الانتظار إلى المتجر. إذا كان هناك خمسة أشخاص في الطابور، فإن أول شخص في الطابور سوف يدخل المتجر . إذا أراد شخص آخر (إلى جانب الخمسة في الطابور) شراء شيء ما واصطف في الطابور، فهو يدخل المتجر أخيرًا ، أي السادس. عند العمل مع قائمة الانتظار، تتم إضافة عناصر جديدة إلى النهاية، وإذا كنت ترغب في الحصول على عنصر، فسيتم أخذه من البداية. هذا هو المبدأ الأساسي لعمله، والذي يجب أن تتذكره، ومن السهل جدًا فهم مبدأ قائمة الانتظار بشكل حدسي، لأنه غالبًا ما يتم مواجهته في الحياة الواقعية. تجدر الإشارة بشكل منفصل إلى أنه في Java، لا يتم تمثيل قائمة الانتظار بواسطة فئة، ولكن بواسطة واجهة - Queue. ولكن في الوقت نفسه، تعد قائمة الانتظار في Java واجهة تحتوي على العديد من التطبيقات. إذا نظرنا إلى وثائق أوراكل، فسنرى أن 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- هذه قائمة انتظار ذات اتجاهين. يعمل على توسيع وظائف قائمة الانتظار العادية من خلال السماح لك بإضافة عناصر إلى كلا الطرفين (بداية ونهاية قائمة الانتظار) وأخذ العناصر من طرفي قائمة الانتظار. يستخدم 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 - "قائمة انتظار الأولوية". يعد هذا أحد أكثر تطبيقات Queue إثارة للاهتمام وإفادة. على سبيل المثال، إذا كان هناك 50 شخصًا في الطابور في متجرك، و7 منهم من عملاء VIP، PriorityQueueفسيسمح لك بخدمتهم أولاً! شيء مفيد للغاية، ألا توافقني على ذلك؟ :) ثانيا، لن يكون من غير الضروري أن نذكر مرة أخرى كتاب روبرت لافوريت "هياكل البيانات والخوارزميات في جافا" . أثناء قراءة الكتاب، لن تتعلم فقط العديد من هياكل البيانات (بما في ذلك المكدس وقائمة الانتظار)، ولكنك ستنفذ أيضًا العديد منها بنفسك! على سبيل المثال، تخيل لو أن Java لا تحتوي على فئة Stack. ماذا ستفعل إذا كنت بحاجة إلى بنية البيانات هذه لبرنامجك؟ وبطبيعة الحال، كان علي أن أكتب ذلك بنفسي. عند قراءة كتاب لافوريت، هذا ما ستفعله غالبًا. بفضل هذا، سيكون فهمك لهياكل البيانات أوسع بكثير من مجرد دراسة النظرية :) لقد انتهينا من النظرية اليوم، لكن النظرية بدون ممارسة لا شيء! المشاكل لن تحل نفسها، لذا حان الوقت لمعالجتها! :)