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

ברצוננו לממש תור $Q$ באמצעות שתי מחסניות $S_1$ ו-$S_2$, כך שעבור $n$ פעולות הכנסה ו-$m$ פעולות מחיקה, בסדר אפשרי כלשהו ($m \leq n$), על $Q$ ריק מלכתחילה, זמן הריצה (כלומר כמות הפעולות הבסיסיות – push ו-pop) יהיה $O(n + m)$. תארו את מבנה המימוש וכתבו בפסאודו-קוד את הפעולות ENQUEUE ו-DEQUEUE של $Q$ בעזרת פעולות המחסניות PUSH ו-POP.

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

פתרון: **מבנה המימוש:** נשתמש בשתי מחסניות: - $S_1$ – מחסנית להכנסות - $S_2$ – מחסנית למחיקות **פסאודו-קוד:** ``` ENQUEUE(Q, x): PUSH(S1, x) ``` ``` DEQUEUE(Q): if S2 is empty: while S1 is not empty: PUSH(S2, POP(S1)) return POP(S2) ``` **הסבר:** כאשר מכניסים איבר, דוחפים אותו ל-$S_1$. כאשר רוצים להוציא, אם $S_2$ אינה ריקה, שולפים ממנה (האיבר העליון ב-$S_2$ הוא הראשון שנכנס). אם $S_2$ ריקה, מעבירים את כל $S_1$ ל-$S_2$ (ההיפוך הופך את הסדר כך שהאיבר הראשון שנכנס יהיה בראש $S_2$), ואז שולפים.