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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

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

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

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

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

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

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


P Computer-science.png ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.