שאלת מבחן בתכנות מונחה עצמים - אוניברסיטת בר-אילן 2022 - מבני נתונים

שאלה משפר 4. (25 נק׳) רשימה מקושרת היא מבנה נתונים הניתן להצגה ממנה ניתונים אשר איזבו אחד מכמו מידע על מי היאיבו הבא זך הלאה. כתבו ב Java קוד אשר מטמיע רשימה מקושרת של Node אשר ייצור איזבו אחד ממשי יטול אשר ביאופון יטיפול האיברים של הרישמה המקושרת, ויהמיהן רשימה מקושרת ביטוח כוללתן חיקויים להותם מכול מכניים יתכניים מכול לתיומים של הרישמה, המחלקה כוללת הרישלות שלם היא עדי ב\ setteres 1 getters 1, ואי, היצגנו ממשנו יעוול עבור מחלקנית אשר יכוללה לאיחור איזביום מכול טיפוסים (כמו מציצי), למשנו, למשנו של סטודנטים בעיזורת בחקירה. יש לכלול בממשי קונספרקטור דיפולטיבי וכן את ממנויות peek,pop,push. כתבנו main המחזיקים שממוש בממחלקנית ובפעולויות שהגדרתו עבור טיפוסים שוניים שתברחרון. למעוו הדיר ספק, עליכם ללמנש את החוק בעצמכם ולא יתתן להשתמש בדוגמים מובנים בדברים כמו Stack של Java. תשובה:

רמז: כדי לממש מחסנית באמצעות רשימה מקושרת, הגדירו את ראש הרשימה (head) כראש המחסנית. פעולות `push` ו-`pop` יתבצעו תמיד על האיבר הראשון ברשימה, ובכך יבטיחו סיבוכיות זמן קבוע.

פתרון: השאלה דורשת לממש מבנה נתונים דמוי **מחסנית** (Stack) באמצעות **רשימה מקושרת** ב-Java, תוך שימוש ב**גנריות** כדי לאפשר אחסון של אובייקטים מכל טיפוס. המחסנית תתמוך בפעולות `push`, `pop`, ו-`peek`. ראשית, נגדיר את מבנה החוליה (Node) של הרשימה המקושרת. מכיוון שהמימוש של החוליה קשור באופן הדוק לרשימה עצמה ואין בו צורך מחוץ לה, נהוג להגדיר אותה כ**מחלקה פנימית סטטית** (static nested class). המחלקה `Node` תהיה גם היא **גנרית**. ```java private static class Node<E> { E data; Node<E> next; public Node(E data) { this.data = data; this.next = null; } } ``` כעת, נגדיר את המחלקה העיקרית, `LinkedListStack<E>`, שתנהל את הרשימה. היא תחזיק רפרנס בלבד לחוליה הראשונה ברשימה, אותה נכנה `head`. כאשר הרשימה (המחסנית) ריקה, `head` יהיה `null`. **קונסטרוקטור דיפולטיבי**: הקונסטרוקטור ייצור מחסנית ריקה על ידי איפוס המצביע `head`. **מימוש הפעולות:** 1. **`push(E data)`**: פעולה זו מוסיפה איבר חדש לראש המחסנית. כדי לעשות זאת, ניצור חוליה `Node` חדשה עם הנתונים. המצביע `next` של החוליה החדשה יוגדר להצביע על ה-`head` הנוכחי, ולאחר מכן, ה-`head` של הרשימה יעודכן להצביע על החוליה החדשה. פעולה זו מתבצעת בסיבוכיות זמן של $O(1)$. 2. **`pop()`**: פעולה זו מסירה את האיבר מראש המחסנית ומחזירה אותו. ראשית, נבדוק אם המחסנית ריקה (`head == null`). אם כן, נזרוק **חריגה** (למשל, `NoSuchElementException`). אחרת, נשמור את הנתונים מה-`head` הנוכחי, נעדכן את `head` להצביע על האיבר הבא (`head.next`), ונחזיר את הנתונים ששמרנו. גם פעולה זו מתבצעת בסיבוכיות זמן של $O(1)$. 3. **`peek()`**: פעולה זו "מציצה" ומחזירה את האיבר שבראש המחסנית מבלי להסיר אותו. בדומה ל-`pop`, נבדוק אם המחסנית ריקה. אם לא, פשוט נחזיר את הנתונים מה-`head`. להלן הקוד המלא, כולל מחלקת `main` המדגימה את השימוש עבור טיפוסים שונים (Integer, String, ואובייקט מותאם אישית `Student`). ```java import java.util.NoSuchElementException; // מחלקה גנרית המממשת מחסנית באמצעות רשימה מקושרת public class LinkedListStack<E> { // מחלקה פנימית סטטית המייצגת חוליה (Node) ברשימה private static class Node<E> { E data; // הנתון בחוליה Node<E> next; // מצביע לחוליה הבאה public Node(E data) { this.data = data; this.next = null; } } private Node<E> head; // מצביע לראש המחסנית (האיבר הראשון ברשימה) // קונסטרוקטור דיפולטיבי public LinkedListStack() { this.head = null; } // מוסיף איבר לראש המחסנית public void push(E data) { Node<E> newNode = new Node<>(data); newNode.next = this.head; this.head = newNode; System.out.println(data.toString() + " pushed to stack"); } // מסיר ומחזיר את האיבר מראש המחסנית public E pop() { if (isEmpty()) { throw new NoSuchElementException("Stack is empty, cannot pop."); } E data = this.head.data; this.head = this.head.next; return data; } // מחזיר את האיבר בראש המחסנית מבלי להסיר אותו public E peek() { if (isEmpty()) { throw new NoSuchElementException("Stack is empty, cannot peek."); } return this.head.data; } // בודק אם המחסנית ריקה public boolean isEmpty() { return this.head == null; } // מחלקת עזר להדגמה עם אובייקט מותאם אישית private static class Student { String name; int id; public Student(String name, int id) { this.name = name; this.id = id; } @Override public String toString() { return "Student{name='" + name + "', id=" + id + '}' ; } } public static void main(String[] args) { System.out.println("--- Demonstrating Stack with Integers ---"); LinkedListStack<Integer> intStack = new LinkedListStack<>(); intStack.push(10); intStack.push(20); intStack.push(30); System.out.println("Top element is (peek): " + intStack.peek()); System.out.println(intStack.pop() + " popped from stack"); System.out.println("Top element is now (peek): " + intStack.peek()); System.out.println(intStack.pop() + " popped from stack"); System.out.println("Is stack empty? " + intStack.isEmpty()); System.out.println(intStack.pop() + " popped from stack"); System.out.println("Is stack empty? " + intStack.isEmpty()); System.out.println("\n--- Demonstrating Stack with Strings ---"); LinkedListStack<String> stringStack = new LinkedListStack<>(); stringStack.push("Hello"); stringStack.push("World"); System.out.println("Top element is: " + stringStack.peek()); System.out.println(stringStack.pop() + " popped from stack"); System.out.println("\n--- Demonstrating Stack with Custom Objects (Student) ---"); LinkedListStack<Student> studentStack = new LinkedListStack<>(); studentStack.push(new Student("Alice", 123)); studentStack.push(new Student("Bob", 456)); Student topStudent = studentStack.peek(); System.out.println("Top student is: " + topStudent); Student poppedStudent = studentStack.pop(); System.out.println(poppedStudent + " popped from stack"); } } ```