תור (מבנה נתונים)

במדעי המחשב, תור (queue) הוא מבנה נתונים מופשט המוגדר על ידי הפעולות הבאות:

הכנסה (enqueue) - הוספת אובייקט אחד חדש בסופו של התור
הוצאה (dequeue) - הוצאתו של האובייקט הנמצא בראש התור
בדיקה אם התור ריק (isEmpty)
בדיקת ערך בראש התור (peek)

כל הפעולות מתבצעות בסיבוכיות $\ O(1)$ , כלומר במספר פעולות שאיננו תלוי בגודל הקלט.

פעולות ההכנסה וההוצאה בתור מבוססות על העיקרון נכנס ראשון - יוצא ראשון FIFO, זאת בניגוד למחסנית שמממשת את אותן הפעולות, אבל לפי עקרון הנכנס אחרון - יוצא ראשון - LIFO (או: נכנס ראשון-יוצא אחרון - FILO).

מימוש תורים

ישנם שני מימושים נפוצים לתור:

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

יישומי התור

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