מבני נתונים: מחסנית ותור

היי! היום נדבר על משהו שהוא סופר חשוב עבור כל מתכנת: מבני נתונים. ויקיפדיה אומרת: " מבנה נתונים הוא פורמט ארגון, ניהול ואחסון נתונים המאפשרים גישה ושינוי יעילים. ליתר דיוק, מבנה נתונים הוא אוסף של ערכי נתונים, היחסים ביניהם, והפונקציות או הפעולות שניתן לבצע. הוחל על הנתונים." ההגדרה קצת מבלבלת, אבל עיקרה ברור. מבנה נתונים הוא מעין מאגר שבו אנו מאחסנים נתונים לשימוש עתידי. בתכנות, יש מגוון עצום של מבני נתונים. כאשר פותרים בעיות ספציפיות, לרוב הדבר החשוב ביותר הוא לבחור את מבנה הנתונים המתאים ביותר לבעיה. ואתם כבר מכירים רבים מהם! לדוגמה, אתה יודע על מערכים. ואתה גם מכיר Map(ניתן להתייחס למבנה הנתונים הזה גם כ"מילון" או "מערך אסוציאטיבי"). חשוב מאוד להבין שמבני נתונים אינם קשורים לשפה מסוימת. הם פשוט "שרטוטים" מופשטים שכל שפת תכנות משתמשת בהם כדי ליצור מחלקות משלה או יישומים של מבנה מסוים. לדוגמה, אחד ממבני הנתונים המפורסמים ביותר הוא רשימה מקושרת. אפשר להיכנס לויקיפדיה ולקרוא איך זה עובד ומה היתרונות והחסרונות שיש לזה. אולי ההגדרה שלו תיראה לכם מוכרת :) "רשימה מקושרת היא אוסף ליניארי של רכיבי נתונים, שהסדר שלהם אינו נתון על ידי מיקומם הפיזי בזיכרון. במקום זאת, כל אלמנט מצביע על הבא." זה מתאר את האהוב שלנו LinkedList, לא? כן, וזה בדיוק מה שזה :) בג'אווה, מבנה הנתונים של "רשימה מקושרת" מיושם על ידי המחלקה LinkedList. אבל שפות אחרות מיישמות גם רשימות מקושרות! ב-Python, מבנה הנתונים הזה נקרא " llist". בסקאלה זה נקרא " LinkedList", בדיוק כמו בג'אווה. רשימה מקושרת היא אחד ממבני הנתונים הנפוצים הבסיסיים, כך שתגלו שהיא מיושמת בכל שפת תכנות מודרנית. אותו הדבר נכון לגבי מערכים אסוציאטיביים. הנה ההגדרה מויקיפדיה: "מערך אסוציאטיבי, מפה, טבלת סימנים או מילון הוא סוג נתונים מופשט המורכב מאוסף של (מפתח, ערך) זוגות, כך שכל מפתח אפשרי מופיע לכל היותר פעם אחת באוסף." זה מזכיר לך משהו? :) כן. עבורנו מפתחי Java, מערך אסוציאטיבי הואMapמִמְשָׁק. אבל מבנה הנתונים הזה מיושם גם בשפות אחרות! לדוגמה, מתכנתי C# מכירים את זה תחת השם "מילון". וב-Ruby, זה מיושם בכיתה בשם "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" נכנס אחרון לחפיסה (זה היה הקלף החמישי), וזה היה הקלף שהשחקן שלף ראשון. "מיליהאוס" היה השני אחרון לתוך החפיסה, והשחקן צייר אותו במקום השני. "סילוואנס" נכנס לחפיסה שלישית מלמעלה, וזה היה הקלף השלישי שהשחקן שלף. לאחר מכן, השחקן זורק קלפים. ראשית, היא זורקת את אדווין, אחר כך את מילהאוס, ואז את סילבנס. לאחר מכן אנו מציגים את הקלפים בערימת השלכה שלנו בזה אחר זה: פלט מסוף:

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

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

תור ב-Java

תור הוא מבנה נתונים נפוץ נוסף. בנוסף לערימות, שפות תכנות רבות, כולל Java, מיישמות גם את מבנה הנתונים בתור. מה ההבדל בין תור למחסנית? תור מבוסס לא על עיקרון LIFO, אלא על עיקרון FIFO ("first in, first out"). עיקרון זה קל להבנה על ידי בחינת, למשל, קו רגיל, או תור, בחיים האמיתיים! למשל, תור במכולת. אם יש חמישה אנשים בתור, הראשון שיוגש יהיה זה שנכנס ראשון לקו . אם אדם אחר (בנוסף לחמישה שכבר בתור) רוצה לקנות משהו ומתייצב בתור, אז הוא מקבל שירות אחרון , כלומר שישי. בעבודה עם תור מוסיפים אלמנטים חדשים לזנב (אחורי), ואם רוצים לקבל אלמנט הוא יילקח מהראש (הקדמי). זה העיקרון העיקרי שאתה צריך לזכור לגבי אופן הפעולה של תור. הפעולה של תור היא מאוד אינטואיטיבית, מכיוון שאנו מוצאים תורים לעתים קרובות בחיים האמיתיים. ראוי לציין בנפרד שב-Java תור מיוצג לא על ידי מחלקה, אלא על ידי ממשק: Queue. מה שכן, יש הרבה יישומים של ממשק התור הזה בג'אווה. אם נסתכל על התיעוד של אורקל, נראה ש-4 ממשקים שונים, כמו גם רשימה מרשימה ביותר של מחלקות, יורשים את ממשק ה-Queue:

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

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

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

הא! הנה החבר הוותיק שלנו LinkedList! אז, הוא מיישם את ממשק ה-Queue? אבל איך זה יכול להיות תור? אחרי הכל, a 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? מה הייתם עושים אם הייתם צריכים מבנה נתונים כזה עבור התוכנית שלכם? אתה תצטרך לכתוב את זה בעצמך, כמובן. כשאתה קורא את ספרו של לאפור , לעתים קרובות תעשה בדיוק את זה. כתוצאה מכך, ההבנה שלכם במבני נתונים תהיה הרבה יותר עמוקה ממה שהייתם מקבלים מלימוד פשוט של התיאוריה :) אנחנו מסיימים את התיאוריה להיום, אבל תיאוריה ללא תרגול היא כלום! המשימות לא יפתרו את עצמן, אז הגיע הזמן להתמודד איתן! :)