תרגיל בjava שנתקעתי איתו

[Eddy652]

תרגיל בjava שנתקעתי איתו

אהלן,
קיבלתי תרגיל שבו אני צריך למצוא מבנה נתונים שיממש שיטות מסוימות (מצורף).
חשבתי על מחסנית שתמומש על ידי רשימה מקושרת דו-כיוונית ממויינת, כשבראש שלה יופיע האיבר המינימלי ובזנב האיבר המקסימלי.
הבעיה היא שאני לא מצליח להתמודד עם המספרים המיוחדים- בעיקר עם זה שמספר מיוחד יכול להופיע כמספר גדול ביותר/קטן ביותר.
אשמח לעזרתכם (ברמת הפסאדו קוד או סתם תאור כללי איך לגשת לזה מספיק טוב כמובן)

 

[Eddy652]

רואה שהתמונה לא הועלתה כמו שצריך, פשוט ארשום פה:

הציעו מבנה נתונים המאפשר את הפעולות הבאות על קבוצה S של n מספרים שונים, מתוכם יש m מספרים "מיוחדים" (m < n). לכל פעולה מצורף החסם עליון המותר לזמן ריצת הפעולה.
&nbsp
1. בהינתן מספר k (שידוע אם הוא מיוחד) הוסף אותו לקבוצה S. זמן מירבי מותר- (o(n
2. הוצא את האיבר הקטן ביותר בקבוצה S. זמן מירבי מותר- (o(1
3. הוצא את האיבר הגדול ביותר בקבוצה S. זמן מירבי מותר- (o(1
4. החזר את האיבר המיוחד הכי "ותיק" (לפי סדר ההכנסה). זמן מירבי מותר- (o(1

 

[BravoMan]

התשובה לשאלה שלך נמצאת בשורה שמתחת לטאבלה:

שים לב כמה זיכרון מותר לך לנצל למבנה הזה.

 

[Eddy652]

אוקיי, אבל עדיין לא הצלחתי להסיק מזה

מה הפתרון.
&nbsp
חשבתי על דרך שבה פרט לרשימה שתיארתי, אני אבנה רשימה דו-כיוונית נוספת, שתכיל רק את האיברים המיוחדים- והאיבר בראשה יהיה הכי ותיק.
&nbsp
בנוסף, אכניס שדה נוסף בכל חוליה ברשימה הראשונה (של המספרים הרגילים והמיוחדים) שיציין מה המיקום של האיבר ברשימה של המיוחדים (אם זה איבר רגיל- השדה הזה יצביע לnull).
&nbsp
אבל גם זה לא מסתדר לי...
מה דעתכם?
&nbsp
&nbsp
&nbsp

 

[BravoMan]

אתה בכיוון, אבל שים לב:

מבקשים ממך תמיד את המספר המיוחד האחרון, לפי סדר ההכנסה.
&nbsp
זה די מזכיר מבנה שנקרא "מחסנית".

 

[Eddy652]

כן, התכוונתי שהרשימה השנייה תמומש בצורת LIFO

כלומר האיבר שבזנב הרשימה השנייה הוא האיבר המיוחד האחרון שהוכנס.
ניסיתי לצייר דוגמה למה שאני מתכוון. ציינתי שם מי נחשבים למספרים מיוחדים.

אשמח אם תגידו לי את דעתכם גם על התיאור הכללי שלי לשיטות:

ברשימה הדו-כיוונית הראשונה הוספתי שדה שאני אקרא לו special. הוא מצביע לNull אם האיבר הספציפי לא איבר מיוחד, ואם הוא כן מיוחד- אז הוא מצביע למיקום שלו ברשימה השנייה (שהיא כאמור, מייצגת את סדר ההכנסה).

הכנסה- נבדוק אם המספר מיוחד או לא. אם לא- נבנה לו חוליה שתייצג אותו ונכניסה לרשימה הראשונה במיקום המתאים (כך שהרשימה תשאר ממויינת).
אם כן- נבנה לו גם כן חוליה ונכניסה לרשימה הראשונה במיקום המתאים, ובנוסף נבנה לו עוד חולייה שתכנס לראש הרשימה השנייה. כמו כן, נעדכן את מצביע הspecial של החוליה הראשונה שהכנסנו לרשימה לראשונה- להצביע למיקום החוליה השנייה של המספר ברשימה השנייה (ראש הרשימה).

הוצאה והחזרת מקסימום- נוציא את האיבר שבסוף הרשימה הראשונה. אם זה מספר רגיל- פשוט נעדכן בהתאם את מצביעי הרשימה ונסיים. אם מספר מיוחד- גם כן נעדכן בהתאם, אך נדאג להסיר את האיבר הזה גם מהרשימה השנייה על ידי עדכון המצביעים שלפניו ואחריו- את זה נעשה בעזרת מצביע הspecial.

החזרת איבר מיוחד ותיק ביותר- נחזיר את הdata של האיבר בזנב הרשימה.

 

[BravoMan]

על פניו נראה שהפתרון נכון.

אני לפחות לא מוצא בעיות איתו (אולי מישהו אחר בפורום ישים לב למשהו שפספסתי).