מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/מחסניות

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי


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


כדאי לדעת:

#לפעמים קוראים למבנה זה LIFO, או "last in - first out".
  1. תורים עוסק בFIFO.
  2. בספר הקורס, הפרק "Elementary Data Structures" מכסה נושא זה.


מימוש C++

std::stack


ממשק[עריכה]

מחסנית צריכה לתמוך בממשק הבא:

# Pushes (inserts) a value (v) to a stack (stk).
Push(stk, v)	

# Pops (removes) from a stack (stk) the newest value Push()ed 
#	(that has not yet been Pop()ed).
Pop(stk)

# Returns the newest value Push()ed to a stack (stk) 
# 	(that has not yet been Pop()ed).
Top(stk)

# Returns the number of values inside a stack (stk).
Size(stk)

להלן דוגמה לשימוש במחסנית:

1	Push(stk, 1)
2	Push(stk, 3)
3	Push(stk, 2)

	# Prints 3
4	print Size(stk)

	# Prints 2
5	Print Top(stk)

6	Pop(stk)

	# Prints 2
7	print Size(stk)

	# Prints 3
8	Print Top(stk)


הגדרה:

לעתים יש מבני נתונים שנתן לממש אותם בדרכים שונות. כדאי להבדיל בין הדברים הבאים:

  • ממשק (interface) - מה המבנה עושה
  • מימוש (implementation) - איך המבנה עושה זאת

אלה המושגים הנהוגים בהנדסת תכנה. בתחום מבני הנתונים והאלגוריתמים, לפעמים קוראים למבנה נתונים שרק הממשק שלו הוצג - ADT, או abstract data type.‏


שימו לב:

למרבה הצער, אין ממשק מוסכם למחסנית. אנו השתמשנו בשמות הפעולות Push,‏ Pop,‏ ‏ וTop;‏ יש המשתמשים בממשק הבא:
# Pushes (inserts) a value (v) to a stack (stk).
Push(stk, v)	

# Pops (removes) from a stack (stk) the newest value Push()ed 
#	(that has not yet been Pop()ed).
Pop(stk)

# Returns the newest value Push()ed to a stack (stk) 
# 	(that has not yet been Pop()ed).
Top(stk)

# Returns whether the size of the stack is 0.
Empty(stk)

כלומר הפעולה Size איננה, אך במקומה מופיעה הפעולה Empty; קל לראות שאין זה הבדל משמעותי.

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

מימוש מערך[עריכה]

הרעיון הכללי[עריכה]

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


עכשיו תורכם:

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




דוגמה:

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

הכנסת איברים למחסנית ממומשת ע"י מערך.
הכנסת איברים למחסנית ממומשת ע"י מערך.




דוגמה:

התרשים הבא מתאר פעולת Delete:

הוצאת איברים ממחסנית ממומשת ע"י מערך.
הוצאת איברים ממחסנית ממומשת ע"י מערך.


פסוודו-קוד[עריכה]

להלן הפסוודו-קוד של מימוש זה. (המימוש מניח שישנו משתנה גלובלי max-size, המתאר את גודל המקסימום של המחסנית.):

# An array-based stack.
Stack
	# An array storing the values.
1	Values
	# The current used size.
2	size


# Creates a stack.
Make-Stack()
1	stk = Stack()

# Note we're using the global variable max-size.
2	stk.Values = Make-Array(max-size)
3	stk.size = 0

4	return stk


# Pushes (inserts) a value (v) to a stack (stk).
Push(stk, v)	
1	stk.Values[++stk.size] = v


# Pops (removes) from a stack (stk) the newest value Push()ed 
#	(that has not yet been Pop()ed).
Pop(stk)
1	return stk.Values[stk.size--]


# Returns the newest value Push()ed to a stack (stk) 
# 	(that has not yet been Pop()ed).
Top(stk)
1	return stk.Values[stk.size]


# Returns the number of values inside a stack (stk).
Size(stk)
1	return stk.size

ניתוח[עריכה]

קל מאד להוכיח את נכונות המימוש, וכן קל להראות שסיבוכיות כל פעולה היא .

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

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


כדאי לדעת:

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


הפרק הקודם:
רשימות מקושרות
מחסניות הפרק הבא:
תורים