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

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

כדאי לדעת: #לפעמים קוראים למבנה זה 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)

הגדרה: לעתים יש מבני נתונים שנתן לממש אותם בדרכים שונות. כדאי להבדיל בין הדברים הבאים: ממשק (interface) - מה המבנה עושה מימוש (implementation) - איך המבנה עושה זאת אלה המושגים הנהוגים בהנדסת תכנה. בתחום מבני הנתונים והאלגוריתמים, לפעמים קוראים למבנה נתונים שרק הממשק שלו הוצג - ADT, או abstract data type.‏

שימו לב: למרבה הצער, אין ממשק מוסכם לתור. אנו השתמשנו בשמות הפעולות 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)

מימוש על ידי שתי מחסניות

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

הפרק הקודם: מחסניות

תורים תרגילים

הפרק הבא: עצי חיפוש בינריים