דו-תור
דו-תור (אנגלית: Double-Ended Queue), הוא מבנה נתונים מופשט הדומה לתור אך מאפשר הכנסה והוצאה של ערכים משני צידיו. ניתן להגדיר גרסה של דו-תור המאפשרת הכנסה משני צידי התור אך הוצאה רק מראשו, או דו-תור המאפשר הכנסה רק מהזנב והוצאה משני הצדדים.
בדומה לתור רגיל, ניתן לממש דו-תור באמצעות רשימה מקושרת דו-כיוונית או באמצעות מערך. הפעולות המוגדרות על מבנה הנתונים מתבצעות בסיבוכיות קבועה של .
ניתן להשתמש בדו-תור במקומות בהם נדרש מימוש של תור רגיל אך יש לאפשר הכנסה מיידית של נתונים כך שיופיעו בראש התור או כאשר יש צורך להוציא לעיתים נתונים שבזנב לפני העברתם ליעד.
| מבני נתונים | ||
|---|---|---|
| מבנים מופשטים | רשימה • מחסנית • קבוצה • מולטי קבוצה • תור • דו-תור • תור עדיפויות • מילון • מחרוזת • איחוד קבוצות זרות | |
| מימושים ליניאריים | מערך • מערך משונן • טבלת גיבוב • רשימה מקושרת • רשימת דילוגים • חוצץ | |
| גרפים ועצים | ערימה (בינארית • בינומית • פיבונאצ'י) • עץ חיפוש (עץ אדום שחור • עץ 2-3 • עץ 2-3-4) • עץ סיפות • עץ B • עץ +B • עץ AVL • עץ Splay • עץ BSP • עץ kd • עץ R • Trie • X-fast trie • טריי y מהיר• עץ WAVL | |
| הסתברותיים | מסנן בלום | |