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

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

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


כדאי לדעת:

#לפעמים קוראים למבנה זה FIFO, או "first in - first out".
  1. מחסניות עוסק בLIFO.
  2. בספר הקורס, הפרק "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)

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

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


הפרק הקודם:
מחסניות
תורים
תרגילים
הפרק הבא:
עצי חיפוש בינריים