שאלת deque

[weinnir]

שאלת deque

אני שב אל הפורום המשובח הזה עם שאלה חדשה בכיסי: משום מה קיבלתי את הרושם שע"מ ליצור deque - double eded queue בעזרת linked list עלי ליישם את זה עם double linked list האם כך הדבר? (כמובן שעלות הכנסה או הוצאה מכל צד צריכה להיות בגודל 1). בנוסף - האם עלי להשתמש ב- dummy node ? ואחרון חביב - האם צריך לפיכך לשמור פוינטר אל סוף הדק כמו גם אל תחילתו? אלפי תודות מראש (גם אם לא תענו)

 

[אינגולמו]

תשובה פשוטה

1. כן, אפשר ברשימה מקושרת דו-כיוונית. זה הכי הגיוני. 2. DUMMY לא חובה. אפשר פשוט לראות מתי מתרוקנת הרשימה, אפשר לשמור COUNT, וכו'. 3. אם השתמשת ברשימה דו-כיוונית, זה כבר משתמע, לא?

 

[משועמם14]

אפשר גם עם חד כיוונית.

ניתן ליישם תור גם עם רשימה מקושרת חד כיוונית בצורה הבאה: שומרים שני מצביעים, אחד לסוף הרשימה (TAIL) ואחד לתחילת הרשימה ( HEAD), כשמוציאים איבר, לוקחים אותו מתחילת הרשימה, ומקדמים את ה- HEAD אחד קדימה, וכשמכניסים לרשימה, מכניסים ב- TAIL.NEXT ומקדמים את TAIL להיות TAIL.NEXT...

 

[DNile]

לא מדובר בסתם תור,

מדובר בתור דו-צדדי(double ended queue), שאפשר לצרף איבר לסוף, לצרף איבר להתחלה, לקחת איבר מהסוף, ולקחת איבר מהתחלה(push_front, push_back, pop_front, pop_back)