תור (מבנה נתונים)
מתוך ויקיפדיה, האנציקלופדיה החופשית
במדעי המחשב, תור (queue) הוא מבנה נתונים המוגדר על ידי הפעולות הבאות:
- הכנסה (enqueue) בסיבוכיות קבועה (במונחי סיבוכיות אסימפטוטית:
) - הוצאה (dequeue) בסיבוכיות קבועה ()
- בדיקה אם התור ריק בסיבוכיות קבועה ()
- בדיקת ערך בראש התור (הצצה) בסיבוכיות קבועה ().
פעולות ההכנסה וההוצאה בתור מבוססות על העקרון נכנס ראשון - יוצא ראשון FIFO, זאת בניגוד למחסנית שמממשת את אותן הפעולות, אבל לפי עקרון הנכנס ראשון- יוצא אחרון - LIFO).
[עריכה] מימוש תורים
תורים ממומשים בדרך כלל בעזרת מערך לשמירת הנתונים, ומשתני עזר לשמירת מיקומו של ראש התור וזנבו בתוך המערך. למימוש כזה קוראים גם לעתים חוצץ מעגלי (cyclic buffer).
[עריכה] מימוש תורים בשפות תכנות
בשפות תכנות בדרך כלל אין טיפוס מובנה לתורים, אם כי בחלק מהשפות הספריות הסטנדרטיות מכילות מימושים עבור המבנה. למשל ב-++C יש את מחלקות ה-queue ו-dequeue המממשות סוגים שונים של תורים.
[עריכה] יישומי התור
תורים משמשים באלגוריתמים הדורשים שמירה על סדר במהלך העברת הנתונים (למשל העברת הודעות בין תהליכונים (Threads) של תוכנית כלשהי ממומשת לרוב בעזרת תורים), ובמבני נתונים מורכבים יותר כמו למשל תור עדיפויות, שמשמשים לטיפול בריבוי משימות במערכות הפעלה המודרניות, טיפול בבקשות הנכנסות בשרתי אינטרנט, וכדומה.
