מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/תורים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 72:
===מימוש רשימה מקושרת===
קל מאד (וכמעט מתבקש) לממש תור על ידי רשימה מקושרת. להלן מימוש על ידי [[מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/רשימות מקושרות|רשימה מקושרת (דו-כוונית)]].
התור מכיל בתוכו שדה יחיד - רשימה מקושרת {{קוד בשורה|l}}.
<source lang = "python">
Queue
l # A list.
</source>
כעת יש שתי אפשרויות:
#נכניס איברים לסוף הרשימה, ונשלוף אותם מראשה.
#נכניס איברים לראש הרשימה ונשלוף אותם מסופה.
אין הבדל משמעותי בין המימושים. כדי להדגיש את הסימטריות של רשימה מקושרת דו-כוונית, נראה את האפשרות השניה.
כדי לדחוף איבר לתור, נכניס אותו לראש הרשימה. להלן הפסוודו-קוד לפעולת Enqueue:
<source lang = "python">
# Enqueues a value (v) in a queue (q)
Enqueue(q, v)
1 Insert-Front(q.l, v)
</source>
היות שבחרנו להכניס איברים לראש הרשימה, האיבר הראשון שנשלוף בכל פעם יהיה מסוף הרשימה:
<source lang = "python">
# Dequeues a value from a (non-empty) queue (q), and returns this value.
Dequeue(q)
1 v = Back(q.l)
2 Delete-Back(q.l)
3 return v
</source>
נשים לב שבמימוש זה, ראש התור הוא למעשה סוף הרשימה:
<source lang = "python">
# Returns the front (next to be dequeued) value from a (non-empty) queue (q).
Front(q)
1 return Back(q.l)
</source>
===מימוש על ידי שתי מחסניות===
| |||