שאלה במבני נתונים

[מבולבלת23]

שאלה במבני נתונים

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

 

[HaifaMan]

את יכולה לצרף את התרגיל?

באילו פעילויות בדיוק צריך לתמוך? מחסנית רגילה + הכנסה לאמצע?

 

[HaifaMan]

יש לי רעיון

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

 

[מבולבלת23]

לא כל כך הבנתי אותך....

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

 

[HaifaMan]

כמו שאני הגעתי...

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

 

[corona22]

תשובה חלקית

את צריכה להכניס איברים ולשמור על איזון הרעיון הוא לשמור על האמצע, כאשר מחצית האיברים הראשונים יהיו במחסנית והמחצית השניה בתור בכל פעולת הכנסה תצטרכי להעביר מהתור למחסנית איבר, תמיד יהיה מספר שווה של איברים או בהפרש של איבר אחד, וכך את שומרת על האמצע ואת יכולה להוציא אותו בטטה של 1. נדמה לי שזה הרעיון הכללי... לא למדתי מבנה נתונים הרבה זמן=)