שאלת מבחן במבני נתונים ומבוא לאלגוריתמים - האוניברסיטה הפתוחה 2025 - מחסניות

נגדיר "סופר מחסנית" $SS$ (Super Stack), כמבנה המכיל מספרים טבעיים, תומך בכל פעולות המחסנית, ובנוסף תומך בפעולה $SUPER\_POP(SS)$: - $CREATE(SS)$: אתחול מבנה $SS$ ריק, בזמן $O(1)$. - $STACK\text{-}EMPTY(SS)$: מחזיר $TRUE$ אם המבנה $SS$ ריק, בזמן $O(1)$. - $PUSH(SS, x)$: הכנסת המספר $x$ למבנה $SS$, בזמן $O(1)$. - $POP(SS)$: הוצאת המספר שהוכנס אחרון למבנה $SS$ והחזרתו, בזמן $O(1)$. - $SUPER\_POP(SS)$: הוצאת כל המספרים שבמבנה $SS$ והחזרתם, החל מהאיבר שהוכנס אחרון ועד לאיבר שהוכנס ראשון (מבין האיברים הנמצאים במבנה), בזמן $O(n)$. הציעו מימוש למבנה "סופר מחסנית", שבו זמן הריצה הכולל של כל סדרה של $n$ פעולות תהיה $O(n)$. נמקו את חישוב זמן הריצה. נתון שכל סדרה של $n$ פעולות מתחילה עם מבנה ריק, ושהמפתחות ייחודיים (אין חזרות). יש לכתוב רק את שגרת $SUPER\_POP(SS)$.

רמז: השתמשו במחסנית רגילה $S$. הפעולה $SUPER\_POP$ פשוט מוציאה את כל האיברים בלולאה. חישבו את העלות הכוללת של $n$ פעולות באמצעות ניתוח מופחת (amortized analysis).

פתרון: **רעיון:** נחזיק מחסנית רגילה $S$. הפעולות זהות לפעולות על המחסנית, מלבד הפעולה $SUPER\_POP$. **$SUPER\_POP(SS)$:** ``` כל עוד S.Empty() == FALSE בצע: S.Pop() ``` **ניתוח זמן ריצה:** עבור פעולה בודדת, $SUPER\_POP$ במקרה הגרוע תהיה ליניארית. עבור $n$ פעולות: כיוון שמתחילים ממבנה ריק, עבור $n$ פעולות יהיו ב-$S$ לכל היותר $n$ איברים סה"כ (כי $PUSH$ מכניסה איבר אחד בכל פעם). לכן כלל פעולות $SUPER\_POP$ יבצעו $S.Pop()$ לכל היותר $n$ פעמים (כי כל איבר שהוכנס יוצא לכל היותר פעם אחת). סה"כ: כל $n$ הפעולות ($PUSH$, $POP$, $SUPER\_POP$, וכו') עולות $O(n)$.