תור (Queue)

תור (באנגלית: Queue) הוא הוא מבנה נתונים מופשט אך מזכיר תור (תור רגיל של בני אדם), המדיניות שעל פיה מנוהל התור היא FIFO (ראשי תיבות: First In First Out), שגורמת לו לפעול בדומה לתור בקופת חולים (או כל תור דומה אחר). לתור יש ראש (head) וזנב (tail).

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

 

אחת הדרכים למימוש תור היא באמצעות מערך. לתור שני מאפיינים: [head[Q שהוא אינדקס ראש התור או מצביע אליו (תלוי מימוש), ו [tail[Q שהוא אינדקס המקום שבו יוצב האיבר הבא שיוכנס לתור. (בתנאי ששם התור הוא Q כמובן).

שימו לב כי מקום מס’ 1 תמיד בא אחרי מקום מס’ n, דהיינו, האיברים מוצבים במערך בסדר מעגלי. וכאשר [head[Q] = tail[Q התור ריק. בנוסף, יש לשים לב שכאשר התוק ריק, ניסיון למחוק ממנו איבר יגרום לחמיקה. וכאשר 1 + [head[Q] = tail[Q התור מלא, וניסיון להוסיף לו איבר יגרום לגלישה.

 

המתודות (פרוצדורות) שאציג להלן כן מטפלות במצבי השגיאות האלו (חמיקה וגלישה).
להלן המתודות בפסאודו קוד:

דחיפה - הכנסת איבר חדש (לסוף) התור. קוד:

ENQUEUE(Q, x)
if tail[Q] = length[Q] and head[Q] = 1 or tail[Q] +1 = head[Q]
    then error "overflow"
Q[tail[Q]] <- x
if tail[Q] = length[Q]
    then tail[Q] <- 1
else
    tail[Q] <- tail[Q] + 1
  • Q הוא שם התור.
  • x הוא האיבר החדש שאותו אנו מכניסים לתור.
  • לפני שנכניס את האיבר, נבדוק מצב של גלישה, לכן נבדוק אם הזנב שווה לגודל המערך, ובנוסף שהמצביע לראש התור שווה ל-1 או שהמצביע לזנב ועוד אחד שווה למצביע לראש התור. שני המצבים האלו (המצב הראשון והמצב השני, או המצב הראשון והמצב השלישי) יביאו למצב של גלישה, ולכן נדפיס הודעת שגיאה.
  • במידה ויש לנו מקום, נכניס את האיבר (x) לזנב התור.
  • לאחר ההכנסה של האיבר, נבדוק האם ישנו עוד מקום בתור, במידה והזנב שווה לגודל המערך, נזיז את הזנב ל-(1-) (ז”א לראש התור), שזה בעצם מסמן מצב שאין לנו עוד מקום בתור.
  • אחרת (ז”א שיש עוד מקום בתור), נזיז את הזנב תא אחד קדימה.

 

שליפה - הוצאת האיבר (מראש) התור. קוד:

DEQUEUE(Q)
if head[Q] = tail[Q]
    then error "underflow"
x <- Q[head[Q]]
if head[Q] = length[Q]
    then head[Q] <- 1
else
    head[Q] <- head[Q] + 1
return x
  • Q הוא שם התור.
  • אם המצביע לראש התור שווה למצביע לזנב התור, אנו במצב של חמיקה. ז”א שהתור ריק ונדפיס הודעת שגיאה.
  • במידה ויש איברים בתור, נכניס את האיבר עליו מצביע הזנב למשתנה בשם x.
  • ונבדוק האם ראש המחסנית שווה לגודל המערך, במידה וכן (ז”א שניצלנו את כל גודל המערך) נזיז את ראש המערך ל-1 (זה מה שנותן לנו את התכונה המעגלית של התור).
  • אחרת נזיז את ראש התור תא אחד קדימה.
  • ולבסוף, נחזיר את x.

 

כעת, נדגים את פעולות השינוי Enqueue ו Dequeue:

Dequeue & Enqueue

מימוש התור מתבצע באמצעות מערך [Q[1..12. איברי התור מופיעים רק במשבצות הבהירות.

  1. (i) התור מכיל 5 איברים, במקומות [Q[7..11.
  2. בשלב הבא (ii) מוצג התור לאחר הקריאות (Enqueue(Q, 17, ו (Enqueue(Q, 3, ו (Enqueue(Q, 5.
  3. ובשלב האחרון (iii) מוצגת תוצאת התור לאחר שהקריאה (Deququq(Q החזירה את ערך המפתח 15 שהיה קודם בראש התור. עתה נמצא בראש התור האיבר בעל המפתח 6.

(כל אחת מהפעולות האלו מתבצעת בזמן ריצה (O(1).

 

לסיכום

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

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