מחסנית ותור מוסברים בפשטות - Stack ו-Queue

אלה שני מבני הנתונים הכי אינטואיטיביים שתלמדו, ואני מבטיח לכם שאתם כבר מכירים אותם מהחיים האמיתיים, גם אם מעולם לא קראתם לתופעה בשם הזה. פשוט תנו לי שתי דקות, ואתם תבינו אותם לגמרי.

מחסנית - Stack: ערימת הצלחות

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

זו בדיוק מחסנית. הכלל שלה נקרא LIFO - ראשי תיבות של Last In, First Out, כלומר "האחרון שנכנס, ראשון שיוצא". שתי הפעולות היחידות שחשובות הן:

• push - להוסיף איבר למעלה, לראש המחסנית.
• pop - להוציא את האיבר שבראש המחסנית.

איפה זה משמש בפועל? בכל מקום שבו הסדר ההפוך חשוב:

• כפתור ה-"בטל" - undo במעבד תמלילים. כל פעולה נכנסת למחסנית, ולחיצה על בטל מוציאה את האחרונה שנכנסה.
• ניהול הקריאות לפונקציות בתוכנית - כל פעם שפונקציה קוראת לפונקציה אחרת, המערכת "דוחפת" אותה למחסנית, וכשהיא מסיימת, היא "נשלפת" חזרה.
• כפתור החזרה אחורה בדפדפן.

תור - Queue: תור לקופה

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

זה נקרא FIFO - ראשי תיבות של First In, First Out, "הראשון שנכנס, ראשון שיוצא". שתי הפעולות המקבילות הן:

• enqueue - להצטרף לסוף התור.
• dequeue - לצאת מראש התור.

התור הוא בדיוק המבנה שבו משתמשים כשסדר ההגעה חשוב וצריך לשמור עליו:

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

למה זה לא סתם "עוד שני מבנים לשנן"

הדבר החשוב באמת פה הוא לא הפעולות push ו-pop בפני עצמן. זה שברגע שאתם מזהים שבעיה דורשת "אחרון נכנס ראשון יוצא" או "ראשון נכנס ראשון יוצא", אתם מיד יודעים איזה כלי לשלוף מהארגז. בלי המילים האלה בראש, אנשים כותבים קוד מסורבל שמנסה לדמות התנהגות כזו עם רשימות רגילות ותנאים מפותלים, כשבעצם היה פתרון מובנה מוכן וקצר.

בפייתון, אגב, אתם לא צריכים לבנות מחסנית ותור מאפס כדי להשתמש בהם. רשימה רגילה כבר מתפקדת כמחסנית מצוין עם הפעולות append ו-pop. לתור נכון יש כלי ייעודי בשם deque שנועד בדיוק בשביל זה ומהיר יותר מרשימה רגילה לצורך הזה.

איך לתרגל את זה נכון

הדרך הכי טובה להפנים את שני המבנים היא לא לקרוא עליהם, אלא לבנות אחד מכל סוג בעצמכם מאפס, בלי להשתמש בכלים המובנים. תבנו מחסנית עם מערך רגיל ופונקציות push ו-pop משלכם. אחר כך תפתרו איתה בעיה קלאסית, כמו לבדוק אם סוגריים בטקסט נסגרים כמו שצריך. תרגיל קטן כזה עושה יותר להבנה שלכם מאשר שעה של קריאה.

בקורס התכנות הבסיסי שלנו עוברים בדיוק על הבניה הזו, מהיסוד ועד לפתרון תרגילים אמיתיים איתם.

תתחילו את קורס התכנות הבסיסי כאן

לסיכום

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

יש לכם שאלה על תרגיל שאתם תקועים בו? קפצו לדיסקורד שלנו, יש שם אנשים שישמחו לעזור.

הצטרפו לקהילה בדיסקורד