מבני נתונים בג'אווה - מחסנית ותור

שלום! היום נדבר על דברים כל כך חשובים עבור כל מתכנת כמו מבני נתונים . ויקיפדיה אומרת: מבנה נתונים ( eng. data structure ) הוא יחידת תוכנה המאפשרת לך לאחסן ולעבד הרבה מאותו סוג ו/או נתונים הקשורים מבחינה לוגית במחשוב. ההגדרה קצת מבלבלת, אבל המהות שלה ברורה. מבנה נתונים הוא סוג של אחסון שבו אנו מאחסנים נתונים לשימוש נוסף. יש מגוון עצום של מבני נתונים בתכנות. לעתים קרובות מאוד, כאשר פותרים בעיה ספציפית, הדבר החשוב ביותר הוא בחירת מבנה הנתונים המתאים ביותר למטרה זו. ואתם כבר מכירים רבים מהם! לדוגמה, עם מערכים . וגם עם Map(שמתורגם בדרך כלל כ"מילון", "מפה" או "מערך אסוציאטיבי"). חשוב מאוד להבין: מבני נתונים אינם קשורים לשפה ספציפית כלשהי . אלה פשוט "שרטוטים" מופשטים שלפיהם כל שפת תכנות יוצרת מחלקות משלה - יישומים של המבנה הזה. לדוגמה, אחד ממבני הנתונים המפורסמים ביותר הוא הרשימה המקושרת . אפשר להיכנס לויקיפדיה, לקרוא איך זה עובד, אילו יתרונות וחסרונות יש לזה. אולי תמצאו את ההגדרה שלו מוכרת :) "רשימה מקושרת היא מבנה נתונים דינמי בסיסי במדעי המחשב, המורכב מצמתים, שכל אחד מהם מכיל גם את הנתונים עצמם וגם קישור אחד או שניים ("קישורים") אל הבא ו/או רשימת הצמתים הקודמת" אז זה שלנו LinkedList! בדיוק, ככה זה :) מבנה הנתונים של הרשימה המקושרת מיושם בשפת Java בכיתה LinkedList. אבל שפות אחרות מיישמות גם רשימות מקושרות! בפייתון זה נקרא " llist", בסקאלה זה נקרא כמו בג'אווה - " LinkedList". רשימה מקושרת היא אחד ממבני הנתונים הנפוצים הבסיסיים, כך שתוכל למצוא את היישום שלה בכל שפת תכנות מודרנית. אותו דבר עם מערך אסוציאטיבי. הנה ההגדרה שלו מויקיפדיה: מערך אסוציאטיבי הוא סוג נתונים מופשט (ממשק למאגר נתונים) המאפשר אחסון זוגות בצורה "(מפתח, ערך)" ותומך בפעולות של הוספת זוג, כמו גם חיפוש ומחיקת זוג לפי מפתח. לא מזכיר לך כלום? :) בדיוק, עבורנו ג'אוויסטים, מערך אסוציאטיבי הוא ממשקMap. אבל מבנה הנתונים הזה מיושם גם בשפות אחרות! לדוגמה, מתכנתי C# מכירים את זה תחת השם "מילון". ובשפת רובי זה מיושם בכיתה שנקראת "Hash". באופן כללי, אתה מבין בערך מה המשמעות: מבנה נתונים הוא דבר משותף לכל התכנות, אשר מיושם באופן שונה בכל שפה ספציפית. היום נלמד שני מבנים כאלה ונראה איך הם מיושמים בג'אווה - מחסנית ותור.

מחסנית בג'אווה

מחסנית היא מבנה נתונים ידוע. זה מאוד פשוט ודי הרבה חפצים מחיי היומיום שלנו "מיושמים" כמחסנית. תארו לעצמכם מצב פשוט: אתם גרים בבית מלון, ובמהלך היום מקבלים מכתבים עסקיים. מכיוון שלא היית בחדר באותו זמן, עובד המלון פשוט הניח את המכתבים הנכנסים על שולחנך. תחילה הניח את האות הראשונה על השולחן. ואז הגיע השני והוא הניח אותו על הראשון. הוא הניח את האות השלישית שהגיעה על השנייה, ואת הרביעית על השלישית. עכשיו, ענה על שאלה פשוטה: איזה מכתב תקראו ראשון כשתבואו לחדר שלכם ותראו ערימה על השולחן? נכון, אתה תקרא את המכתב העליון . כלומר, זה שהגיע אחרון בזמן . כך בדיוק עובד מחסנית. עקרון הפעולה הזה נקרא 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. במשחק הקלפים שלנו יש 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='Сильвана Ветрокрылая'}

שימו לב לסדר היציאה של הכרטיסים לקונסולה. קלף "אדווין ואן קליף" היה האחרון שפגע בחפיסה (חמישי ברציפות), וזה היה הקלף שהשחקן לקח ראשון. "מיכלאוס" פגע בחפיסה שנייה אחרונה, והשחקן שלה לקח אותה שנייה. "סילוואנס" פגע בחפיסה שלישית מהסוף, והלך לשחקן השלישי. לאחר מכן, השחקן זורק את הקלפים שלו. קודם הוא מפיל את אדווין, אחר כך את מילהאוס, ואז את סילבנס. לאחר מכן אנו מוציאים אחד אחד לקונסולה את הקלפים שנמצאים במחיקה שלנו: פלט לקונסולה:

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

ושוב אנחנו רואים איך המחסנית עובדת! ההשלכה במשחק שלנו היא גם מחסנית (בדיוק כמו החפיסה). "אדווין ואן קליף" היה הראשון שירד. השני שהופל היה "Millhouse Manastorm" - ושכב על גבי אדווין בהשליך. לאחר מכן, סילבנס נזרק - והקלף הזה שכב על גבי מילהאוס. כפי שאתה יכול לראות, אין שום דבר מסובך באופן שבו הערימה עובדת. עם זאת, יש צורך להכיר את מבנה הנתונים הזה – לעתים קרובות שואלים אותו בראיונות, ולרוב נבנים על בסיסו מבני נתונים מורכבים יותר.

תוֹר

תור (או, באנגלית, "תור") הוא מבנה נתונים נפוץ נוסף. ממש כמו מחסנית, הוא מיושם בשפות תכנות רבות, כולל Java. מה ההבדל בין תור למחסנית? התור שלו אינו מבוסס על LIFO, אלא על עיקרון אחר - FIFO ("כניסה ראשונה - יוצאת ראשונה", "כניסה ראשונה - יוצאת ראשונה") . קל להבין, לקחת כדוגמה... או לפחות תור רגיל, אמיתי מהחיים האמיתיים! למשל, תור לחנות. אם יש חמישה אנשים בתור, האדם הראשון בתור ייכנס לחנות . אם עוד אדם אחד (מלבד החמישה בתור) רוצה לקנות משהו ומתייצב בתור, אז הוא נכנס אחרון לחנות , כלומר שישי. בעבודה עם תור מוסיפים אלמנטים חדשים לסוף, ואם רוצים לקבל אלמנט הוא יילקח מההתחלה. זהו העיקרון הבסיסי של פעולתו, אותו אתה צריך לזכור. עיקרון התור קל מאוד להבנה אינטואיטיבית, מכיוון שהוא נתקל לעתים קרובות בחיים האמיתיים. ראוי לציין בנפרד כי ב-Java תור מיוצג לא על ידי מחלקה, אלא על ידי ממשק - 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 - "תור עדיפות". זהו אחד המימושים המעניינים והשימושיים ביותר של Queue. לדוגמה, אם יש 50 אנשים בתור בחנות שלך, ו-7 מהם לקוחות VIP, PriorityQueueזה יאפשר לך לשרת אותם קודם! דבר מאוד שימושי, אתה לא מסכים? :) שנית, לא יהיה מיותר להזכיר שוב את ספרו של רוברט לפורט "מבני נתונים ואלגוריתמים בג'אווה" . במהלך קריאת הספר, לא רק תלמדו מבני נתונים רבים (כולל מחסנית ותור), אלא גם תטמיעו רבים מהם בעצמכם! לדוגמה, תארו לעצמכם אם ל-Java לא הייתה מחלקת Stack. מה הייתם עושים אם הייתם צריכים מבנה נתונים כזה עבור התוכנית שלכם? כמובן שאצטרך לכתוב את זה בעצמי. כשקוראים את ספרו של לפורה, זה מה שתעשה לעתים קרובות. הודות לכך, ההבנה שלך במבני נתונים תהיה הרבה יותר רחבה מלימוד תיאוריה בלבד :) סיימנו עם התיאוריה להיום, אבל תיאוריה ללא תרגול זה כלום! הבעיות לא יפתרו את עצמן, אז עכשיו זה הזמן לטפל בהן! :)