שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2026 - מחסניות

שאלה 3: נתונה מערכת בעיות הקשורות למחסניות ותורים (מבוסס על הגדרות תומכות במדע המחשוב). נא לבדוק את הקשרים בין המבנים ואת סדר הביצוע של הפעולות השונות.

רמז: ממשו תור באמצעות שתי מחסניות. השתמשו במחסנית אחת להכנסת איברים ובמחסנית השנייה להוצאתם. העבירו איברים בין המחסניות רק כאשר מחסנית ההוצאה ריקה.

פתרון: השאלה אינה מוגדרת במלואה, ולכן נפתור בעיה קלאסית המדגימה את הקשר בין מחסניות ותורים: מימוש **תור (Queue)** באמצעות שתי **מחסניות (Stacks)**, וניתוח הסיבוכיות של הפעולות. **הרעיון המרכזי:** נשתמש בשתי מחסניות, נקרא להן `in_stack` ו-`out_stack`. - `in_stack`: משמשת לקליטת איברים חדשים לפעולת ה-`enqueue`. - `out_stack`: משמשת להוצאת איברים בפעולת ה-`dequeue`. התנהגות **FIFO (First-In, First-Out)** של תור מושגת על ידי כך שאיברים המוצאים מהתור הם אלו שהוכנסו ראשונים. מחסנית פועלת בשיטת **LIFO (Last-In, First-Out)**. על ידי העברת האיברים ממחסנית אחת לשנייה, אנו הופכים את סדר האיברים ובכך מדמים את פעולת התור. **מימוש הפעולות:** 1. **`enqueue(x)`:** כדי להוסיף איבר `x` לתור, אנו פשוט דוחפים (push) אותו ל-`in_stack`. `in_stack.push(x)` פעולה זו היא פעולת `push` בודדת, ולכן **סיבוכיות הזמן** שלה היא $O(1)$. 2. **`dequeue()`:** כדי להוציא איבר מהתור, ראשית נבדוק אם `out_stack` ריקה. * **מקרה א': `out_stack` אינה ריקה.** האיבר שבראש `out_stack` הוא האיבר הוותיק ביותר בתור. לכן, אנו שולפים (pop) אותו ומחזירים אותו. `return out_stack.pop()` פעולה זו היא פעולת `pop` בודדת, וסיבוכיות הזמן שלה היא $O(1)$. * **מקרה ב': `out_stack` ריקה.** אם `out_stack` ריקה, עלינו להעביר את כל האיברים מ-`in_stack` אל `out_stack`. אנו עושים זאת בלולאה, כל עוד `in_stack` אינה ריקה: `while (not in_stack.is_empty()):` ` out_stack.push(in_stack.pop())` תהליך זה הופך את סדר האיברים. האיבר שהיה בתחתית `in_stack` (הראשון שנכנס) נמצא כעת בראש `out_stack`. לאחר סיום ההעברה, אנו מבצעים `pop` מ-`out_stack` כבמקרה א'. במקרה הגרוע ביותר, אם יש $n$ איברים ב-`in_stack`, נבצע $n$ פעולות `pop` מ-`in_stack` ו-$n$ פעולות `push` ל-`out_stack`. לכן, **סיבוכיות הזמן במקרה הגרוע** היא $O(n)$. **ניתוח סיבוכיות מופחת (Amortized Analysis):** הסיבוכיות של `dequeue` היא $O(n)$ במקרה הגרוע, אך מקרה זה אינו מתרחש בכל קריאה. נשתמש ב**שיטת הצבירה (Aggregate Method)** לניתוח מופחת. נבחן סדרה של $m$ פעולות (`enqueue` ו-`dequeue`) על המבנה, החל ממצב ריק. נשים לב שכל איבר `x` במהלך חייו במבנה יכול לעבור את הפעולות הבאות לכל היותר פעם אחת: 1. `push` ל-`in_stack` (במהלך `enqueue(x)`). 2. `pop` מ-`in_stack` (במהלך העברה ל-`out_stack`). 3. `push` ל-`out_stack` (במהלך אותה העברה). 4. `pop` מ-`out_stack` (במהלך `dequeue()`). כל איבר תורם מספר קבוע של פעולות (לכל היותר 4 פעולות מחסנית, שכל אחת מהן $O(1)$) למשך כל שהותו במבנה. לכן, העלות הכוללת של סדרת $m$ פעולות על $n$ איברים ($n \\\le m$) היא פרופורציונלית ל-$m$. העלות הכוללת היא $O(m)$. ה**עלות המופחתת** לפעולה היא העלות הכוללת חלקי מספר הפעולות: $\frac{O(m)}{m} = O(1)$ לכן, הסיבוכיות המופחתת של כל פעולה, `enqueue` ו-`dequeue`, היא $O(1)$. $\blacksquare$