ערומות
עמוד זה דורש דפדפן עדכני (תומך ב-SharedArrayBuffer). אנא עדכן את Chrome, Edge, Firefox או Safari לגרסה העדכנית ביותר.
מהו ADT?
- סוג נתונים מופשט (ADT) הוא קבוצת נתונים יחד עם סט של פעולות עליו.
- אתה משתמש בפעולות ומתעלם מכך שהקוד מבונה בפנים.
- מאגר (stack), תור (queue) ו-רשימה מקשרת (linked list) הם כולם ADTs.
מאגר הוא LIFO
- מאגר הוא היכנס אחרון, יציאה ראשונה (LIFO).
- הפריט האחרון שנוסף הוא הראשון שנלקח החוצה.
- תחשוב על ערימת צלחות: לוקחים את הצלחת העליונה קודם.
push ו-pop עם רשימה
- ניתן לבנות מאגר ממטריצת Python.
- push =
stack.append(x)— הוספה בסוף (העליון). - pop =
stack.pop()- הסרה והחזרת הסוף (העליון).
English
stack = []
stack.append("a")
stack.append("b")
print(stack.pop())
print(stack)
peek ו-empty
- peek בעליון בלי להסיר אותו:
stack[-1]. - ערימה היא רוקה כאשר
len(stack) == 0. - ביצוע pop על מאגר ריק הוא טעות, ולכן יש לבדוק קודם.
English
stack = [10, 20, 30]
print(stack[-1]) # peek the top
print(len(stack) == 0) # is it empty?
בפסאודוקוד קמברידג'
- במבחן בונים מאגר ממטריצה יחד עם מצביע
top(אינדקס).
DECLARE stack : ARRAY[1:10] OF INTEGER
DECLARE top : INTEGER
top ← 0 // 0 means empty
// push value
top ← top + 1
stack[top] ← value
// pop into value
value ← stack[top]
top ← top - 1
טעויות נפוצות
- המאגר הוא היכנס אחרון, יציאה ראשונה: push לעליון, pop מעליון.
- בדוק שהוא לא ריק לפני ביצוע pop.
כעת תנסו בעצמכם
- השתמש ברשימה כמאגר שלך (
appendלהוספה,popלהסרה). - לחץ על בדוק תשובה כדי לבדוק את הקוד שלך.
חקור
ערומה היא LIFO
ערומה דוחפת ומוציאה באחד הצדדים — אחרון שנכנס, ראשון שיוצא.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
התחל עם ארגז ריק. הוסף 1, ואז 2, ואז 3. לאחר מכן הסר פעם אחת, ושמור את הערך שהוסר ב-top. (top אמור להיות 3 והארגז אמור להיות [1, 2].)
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
השתמשו בסטיר כדי להפוך את הרשימה items. הכניסו כל פריט לסטיר, ולאחר מכן הוציאו אותם כולם לresult. (result צריך להיות [3, 2, 1].)
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
כתוב top(stack) ש-מחזיר את הפריט העליון (האחרון) מבלי להסירו. אם הערומה ריקה, החזר None.
לחץ על הרץ כדי לראות את התוצא כאן.