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

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

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

הגדרה:

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

s1: [7, 6, 4, 3]

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

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

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]

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