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

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

תבנית:מבנה תבנית

ממשק

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

# 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)

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

מימוש מערך

הרעיון הכללי

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

תבנית:מבנה תבנית

פסוודו-קוד

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

# 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

ניתוח

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

מימוש רשימה מקושרת

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