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

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

כדאי לדעת: #לפעמים קוראים למבנה זה LIFO, או "last in - first out". תורים עוסק בFIFO. בספר הקורס, הפרק "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

ניתוח

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

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

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

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

הפרק הקודם: רשימות מקושרות

מחסניות

הפרק הבא: תורים