מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/תורים

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

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

כדאי לדעת: לפעמים קוראים למבנה זה FIFO, או "first in - first out". מחסניות עוסק בLIFO. בספר הקורס, הפרק "Elementary Data Structures" מכסה נושא זה.

מימוש C++ std::queue

[עריכה] ממשק

להלן ממשק אפשרי לתור:

# Pushes (inserts) a value (v) to a queue (q).
Enqueue(q, v)
 
# Pops (removes) from a queue (q) the oldest value Enqueue()ed 
#     (that has not yet been Dequeue()ed).
Dequeue(q)
 
# Returns the oldest value Dequeue()ed to a queue (q) 
#     (that has not yet been Dequeue()ed).
Front(q)
 
# Returns the number of values inside a queue (q).
Size(q)

להלן דוגמה לשימוש בתור:

1  Enqueue(q, 1)
2      Enqueue(q, 3)
3      Enqueue(q, 2)
 
        # Prints 3
4      print Size(q)
 
        # Prints 1
5      Print Front(q)
 
6      Dequeue(q)
 
        # Prints 2
7      print Size(q)
 
        # Prints 3
8      Print Front(q)

שימו לב: למרבה הצער, אין ממשק מוסכם לתור. אנו השתמשנו בשמות הפעולות Enqueue,‏‏ Dequeue,‏ ‏ ‏ וFront;‏ יש המשתמשים בשמות הפעולות Push,‏ Pop,‏ וFirst; ‏ יש עוד ווריאציות. במהלך הקורס, אם תתקל בממשקים אחרים (לדוגמה במבחנים משנים קודמות), ייתכן שתיאלץ להפעיל מעט גמישות בהבנת הממשק.

[עריכה] מימושים

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

[עריכה] מימוש מערך

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

[עריכה] מימוש רשימה מקושרת

קל מאד (וכמעט מתבקש) לממש תור על ידי רשימה מקושרת. להלן מימוש על ידי רשימה מקושרת (דו-כוונית).

התור מכיל בתוכו שדה יחיד - רשימה מקושרת l.

Queue
        l # A list.

כעת יש שתי אפשרויות:

1. נכניס איברים לסוף הרשימה, ונשלוף אותם מראשה.
2. נכניס איברים לראש הרשימה ונשלוף אותם מסופה.

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

כדי לדחוף איבר לתור, נכניס אותו לראש הרשימה. להלן הפסוודו-קוד לפעולת Enqueue:

# Enqueues a value (v) in a queue (q)
Enqueue(q, v)
1      Insert-Front(q.l, v)

היות שבחרנו להכניס איברים לראש הרשימה, האיבר הראשון שנשלוף בכל פעם יהיה מסוף הרשימה:

# 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

נשים לב שבמימוש זה, ראש התור הוא למעשה סוף הרשימה:

# Returns the front (next to be dequeued) value from a (non-empty) queue (q).
Front(q)
1      return Back(q.l)

[עריכה] מימוש על ידי שתי מחסניות

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