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

public static boolean isBottomStack(Stack<Integer> s1, Stack<Integer> s2)

מחסנית s1 נקראת "מחסנית תחתית" של מחסנית s2 אם כל האיברים של s1 נמצאים בתחתית s2 באותו הסדר. לדוגמה: המחסנית s1 היא מחסנית תחתית של s2. כתבו פעולה המקבלת שתי מחסניות של מספרים שלמים s1 ו-s2. הפעולה תבדוק אם s1 היא מחסנית תחתית של s2. אם כן – הפעולה תחזיר ערך true, ולא – הפעולה תחזיר ערך false.

definitionLabel: הגדרה:

exampleFigure: s2: [4, 6, 3, 1, 7, 6, 4, 3]

s1: [7, 6, 4, 3]

note: values listed top-of-stack-first, label under each box is the stack name; s1 matches s2's bottom 4 elements, consistent with the definition.

confidence: MEDIUM — hand-drawn stack boxes with pointer-arrow decorations, re-verify visually before use as solve-oracle input.

public static Stack<Integer> commonBottom(Stack<Integer> s1, Stack<Integer> s2)

מחסנית נקראת "תחתית משותפת" של s1 ו-s2 אם היא "מחסנית תחתית" גם ל-s1 וגם ל-s2. לדוגמה: המחסניות s3, s4, s5 הן תחתית משותפת של המחסניות s1 ו-s2. כתבו פעולה המקבלת שתי מחסניות של מספרים שלמים s1 ו-s2. הפעולה תחזיר מחסנית חדשה שהיא "תחתית משותפת הארוכה ביותר" של s1 ו-s2.

exampleFigure: s2: [4, 6, 3, 1, 7, 6, 2, 1]

s1: [5, 6, 7, 2, 1]

s3: [6, 2, 1]

s4: [2, 1]

s5: [7, 6, 2, 1]

confidence: MEDIUM-LOW — this multi-stack example did not fully self-verify against the definition when re-derived by hand (s4=[2,1] checks out as the longest common bottom of s1/s2 by this transcription's values, but s3/s5 did not cleanly reconcile) — flagged explicitly as needing visual re-verification of exact box values before use as a solve-oracle input; do not trust this figure's numbers at face value.

מהן הסיבוכיות של הפעולות שכתבתם בסעיפים א'-ב'? הסבירו את תשובתכם.