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

أهلاً! سنتحدث اليوم عن شيء مهم جدًا لأي مبرمج: هياكل البيانات. تقول ويكيبيديا: " بنية البيانات هي تنظيم البيانات وإدارتها وتنسيق تخزينها الذي يتيح الوصول والتعديل الفعالين. وبشكل أكثر دقة، بنية البيانات هي مجموعة من قيم البيانات، والعلاقات فيما بينها، والوظائف أو العمليات التي يمكن يتم تطبيقها على البيانات." التعريف مربك بعض الشيء، لكن جوهره واضح. بنية البيانات هي نوع من المستودع حيث نقوم بتخزين البيانات لاستخدامها في المستقبل. في البرمجة، هناك مجموعة كبيرة ومتنوعة من هياكل البيانات. عند حل مشكلات معينة، غالبًا ما يكون الشيء الأكثر أهمية هو اختيار بنية البيانات الأكثر ملاءمة للمشكلة. وأنت بالفعل على دراية بالعديد منهم! على سبيل المثال، أنت تعرف عن المصفوفات. وأنت أيضًا على دراية Map(قد يُشار إلى بنية البيانات هذه أيضًا باسم "القاموس" أو "المصفوفة النقابية"). من المهم جدًا أن نفهم أن هياكل البيانات ليست مرتبطة بأي لغة معينة. إنها ببساطة "مخططات" مجردة تستخدمها كل لغة برمجة لإنشاء فئاتها الخاصة أو تطبيقات بنية معينة. على سبيل المثال، إحدى هياكل البيانات الأكثر شهرة هي القائمة المرتبطة. يمكنك الذهاب إلى ويكيبيديا والقراءة عن كيفية عمله وما هي مميزاته وعيوبه. ربما يبدو تعريفها مألوفًا لك :) "القائمة المرتبطة هي مجموعة خطية من عناصر البيانات، التي لا يتم تحديد ترتيبها من خلال موضعها الفعلي في الذاكرة. وبدلاً من ذلك، يشير كل عنصر إلى العنصر التالي." هذا يصف حبيبنا LinkedList، أليس كذلك؟ نعم، وهذا هو الأمر :) في Java، يتم تنفيذ بنية بيانات "القائمة المرتبطة" بواسطة الفصل LinkedList. لكن اللغات الأخرى تنفذ أيضًا قوائم مرتبطة! في بايثون، تسمى بنية البيانات هذه " llist". في Scala يطلق عليه " LinkedList"، تمامًا كما هو الحال في Java. تعد القائمة المرتبطة إحدى هياكل البيانات الأساسية الشائعة، لذلك ستجد أنها يتم تنفيذها بأي لغة برمجة حديثة. وينطبق الشيء نفسه على المصفوفات الترابطية. إليك التعريف من ويكيبيديا: "المصفوفة النقابية أو الخريطة أو جدول الرموز أو القاموس هي نوع بيانات مجردة يتكون من مجموعة من أزواج (المفتاح، القيمة)، بحيث يظهر كل مفتاح محتمل مرة واحدة على الأكثر في المجموعة." هل يذكرك ذلك بأي شيء؟ :) نعم. بالنسبة لنا لمطوري Java، المصفوفة الترابطية هي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 {

   // 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، يتم تنفيذ بنية بيانات المكدس في الفصل java.util.Stack. تحتوي لعبة الورق الخاصة بنا على 3 طرق تصف تصرفات اللاعبين:

• خذ بطاقة من سطح السفينة ( getCardFromDeck()طريقة)
• تجاهل البطاقة ( discard()طريقة)
• انظر إلى البطاقة العلوية ( lookAtTopCard()الطريقة). لنفترض أن هذه مكافأة "ذكاء" تسمح للاعب بمعرفة البطاقة التي ستأتي بعد ذلك في اللعبة.

داخل أساليبنا، نسمي الطرق التالية لفئة Stack:

• 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" إلى المجموعة أخيرًا (كانت البطاقة الخامسة)، وكانت البطاقة التي سحبها اللاعب أولاً. كان "Millhouse" في المركز الثاني في المجموعة الأخيرة، وقام اللاعب برسمه في المركز الثاني. ذهب "سيلفاناس" إلى المجموعة الثالثة من الأعلى، وكانت البطاقة الثالثة التي سحبها اللاعب. بعد ذلك، يتجاهل اللاعب البطاقات. أولاً، تتخلص من إدوين، ثم ميلهاوس، ثم سيلفاناس. ثم نقوم بعرض البطاقات في كومة المهملات واحدة تلو الأخرى: إخراج وحدة التحكم:

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

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

قائمة الانتظار في جافا

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