Loading AI tools
מבנה נתונים על פי שיטת LIFO מוויקיפדיה, האנציקלופדיה החופשית
מחסנית היא סוג של מבנה נתונים מופשט הפועל בצורה דומה לזו של מחסנית רובה: האיבר שנכנס ראשון למחסנית יוצא ממנה אחרון (תכונה זו מכונה נכנס אחרון יוצא ראשון - LIFO).
שלוש הפעולות הבסיסיות המגדירות מחסנית הן:
לעיתים, מוגדרות במחסנית גם פעולות נוספות:
את כל הפעולות האלה ניתן להגדיר פורמלית כפונקציות מתמטיות שאינן משנות את המחסנית, אלא מחזירות מחסנית חדשה. הפונקציות מקיימות את התנאים דלהלן:
כל הפעולות במחסנית מתבצעות בזמן קבוע, שאיננו תלוי במספר האיברים במחסנית.
את פעולת ההסרה ניתן להגדיר על מחסנית ריקה ככזאת שמחזירה את אותה המחסנית. לחלופין, ניתן להימנע מלהגדיר אותה, או להגדיר אותה כמחזירה ערך שגיאה מיוחד. באופן דומה, (()top(init (בדיקת ראש מחסנית ריקה) ניתן להגדיר כמחזירה שגיאה, או להימנע מהגדרתה.
חשוב לשים לב לכך שכל אוסף של פונקציות וערכים המקיים את התנאים האלה נחשב למחסנית. דוגמה לא-טריוויאלית לכך היא קבוצת המספרים הטבעיים, עבור הפעולות "החזר 0" (אתחול), "הוסף 1"(push), "הפחת 1"(pop), "האם_אפס"(isEmpty). בכיוון השני ניתן לומר שכל מחסנית עשויה להוות ייצוג למספרים הטבעיים.
מחסנית היא מבנה נתונים בסיסי במימוש שפות תכנות. במעבדים רבים קיים אוגר מיוחד המשמש כמצביע למחסנית, ובשפת המכונה של מעבדים אלו ממומשת הקריאה לתת-שיגרה על ידי הכנסת כתובת החזרה למחסנית. ברוב השפות העיליות נשמרים גם המשתנים המקומיים במבנה המחסנית הנתמך במעבד.
ישנו קשר הדוק בין מחסנית לעץ: מחסנית היא מבנה הנתונים הנפוץ ביותר לצורכי מעבר על עצים, על ידי אלגוריתם DFS, וכן ניתן להציג כל רצף פעולות על מחסנית בעזרת עץ מכוון. בכל רגע נתון, האיברים הנמצאים במחסנית הם המסלול משורש העץ אל הצומת שבו נמצאים. דוגמה לשימוש כזה אפשר למצוא בשפות פורמליות: לכל מילה הנגזרת בעזרת דקדוק חסר הקשר קיים עץ גזירה, ולכל דקדוק כזה קיים אוטומט מחסנית המקבל אותו.
ישנן מספר דרכים לממש מחסנית:
מימושים שונים עלולים לאפשר מצבים לא תקינים:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.