מבנה נתונים מופשט

במדעי המחשב, מבנה נתונים מופשט (Abstract Data Type או ADT) הוא מודל מתמטי עבור קבוצה מסוימת של מבני נתונים בעלי התנהגות דומה, או עבור טיפוסי נתונים שונים בשפות תכנות להם סמנטיקה דומה, ומאפשר הפשטה שלהם. מבנה נתונים מופשט מוגדר על ידי הפעולות שניתן לבצע עליו ועל ידי מגבלות שחלות על תוצאות הפעולות האלה (או העלות שלהן מבחינת סיבוכיות זמן ומקום).

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

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

כמו כן מאפשרים מבני הנתונים המופשטים לסווג מבני נתונים, ולתאר באופן פורמלי את מערכות הטיפוסים של שפות תכנות. ניתן לממש מבני נתונים בעזרת טיפוסי נתונים או מבני נתונים שונים, בשפות תכנות שונות.

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