ברצוננו לממש תור \(Q\) באמצעות שתי מחסניות \(s_1\) ו-\(s_2\), כך שעבור \(n\) פעולות הכנסה ו-\(m\) פעולות מחיקה, בסדר אפשרי כלשהו (\(m \le n\)), על \(Q\) ריק מלכתחילה, זמן הריצה (כלומר כמות הפעולות הבסיסיות – PUSH ו-POP) יהיה \(O(n+m)\).

א. תארו את מבנה המימוש וכתבו בפסאודו-קוד את הפעולות ENQUEUE ו-DEQUEUE של \(Q\) בעזרת פעולות המחסניות PUSH ו-POP.

ב. מהו זמן הריצה של כל פעולה של \(Q\) במקרה הגרוע ובמקרה הטוב?

ג. הראו שזמן הריצה של \(n\) פעולות הכנסה ו-\(m\) פעולות מחיקה, בסדר אפשרי כלשהו (\(m \le n\)), על \(Q\) ריק מלכתחילה, הוא \(O(n+m)\).
הדרכה: ספרו כמה פעולות PUSH וכמה פעולות POP לכל היותר יכולות להתבצע במהלך כל \(n+m\) ההכנסות והמחיקות.