מדריך לערימות בפייתון

הועלה מחדש על ידי אפלטון

עוקב: 0

מבוא

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

אז מה זה מחסנית? בליבה, מחסנית היא מבנה נתונים ליניארי העוקב אחר LIFO עקרון (Last In First Out).. תחשוב על זה כעל ערימת צלחות בקפיטריה; אתה לוקח רק את הצלחת שנמצאת למעלה, וכאשר מניחים צלחת חדשה, היא עוברת לראש הערימה.

האלמנט האחרון שנוסף הוא האלמנט הראשון שיוסר

עקרון LIFO

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

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

מושגים בסיסיים של מבנה נתונים מחסנית

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

עקרון ה-LIFO (Last In First Out).

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

הערה: דוגמה שימושית נוספת שתעזור לך לעטוף את הראש סביב הרעיון של אופן פעולת הערימות היא לדמיין אנשים נכנסים ויוצאים ממנו מעלית - האדם האחרון שנכנס למעלית הוא הראשון שיצא!

פעולות בסיסיות

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

דחוף - מוסיף אלמנט לראש הערימה. אם הערימה מלאה, פעולה זו עלולה לגרום להצפת מחסנית.

פעולת דחיפה של LIFO

פּוֹפּ - מסיר ומחזיר את האלמנט העליון של הערימה. אם המחסנית ריקה, ניסיון להקפיץ עלול לגרום להזרמת מחסנית.

פעולת LIFO פופ

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

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

כיצד ליישם מחסנית מאפס ב-Python

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

יישום מחסנית באמצעות מערכים

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

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

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

class Stack: def __init__(self, size): self.size = size self.stack = [None] * size self.top = -1

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

מעתה ואילך, ניצור ונסביר שיטה אחת עבור כל אחת מפעולות הערימה הבסיסיות. כל אחת מהשיטות הללו תהיה כלולה בתוך Stack כיתה שזה עתה יצרנו.

בואו נתחיל עם push() שיטה. כפי שצוין קודם לכן, פעולת הדחיפה מוסיפה אלמנט לראש הערימה. קודם כל, נבדוק אם למחסנית נשאר מקום לאלמנט שברצוננו להוסיף. אם הערימה מלאה, נעלה את Stack Overflow יוצא מן הכלל. אחרת, פשוט נוסיף את האלמנט ונתאים את top ו stack בהתאם לכך:

def push(self, item): if self.top == self.size - 1: raise Exception("Stack Overflow") self.top += 1 self.stack[self.top] = item

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

def pop(self): if self.top == -1: raise Exception("Stack Underflow") item = self.stack[self.top] self.top -= 1 return item

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

def peek(self): if self.top == -1: raise Exception("Stack is empty") return self.stack[self.top]

וזה הכל! כעת יש לנו מחלקה המיישמת את ההתנהגות של ערימות באמצעות רשימות ב-Python.

יישום מחסנית באמצעות רשימות מקושרות

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

כפי שכבר דנו ב- "רשימות מקושרות לפייתון" מאמר, הדבר הראשון שנצטרך ליישם לפני הרשימה המקושרת בפועל הוא מחלקה לצומת בודד:

class Node: def __init__(self, data): self.data = data self.next = None

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

יישום זה מאחסן רק שתי נקודות של נתונים - הערך המאוחסן בצומת (data) וההפניה לצומת הבא (next).

הסדרה שלנו בת 3 חלקים על רשימות מקושרות ב-Python:

עכשיו אנחנו יכולים לקפוץ למעמד המחסנית עצמו. הקונסטרוקטור יהיה קצת שונה מהקודם. הוא יכיל רק משתנה אחד - ההתייחסות לצומת בחלק העליון של הערימה:

class Stack: def __init__(self): self.top = None

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

def push(self, item): node = Node(item) if self.top: node.next = self.top self.top = node

השמיים pop() השיטה בודקת אם יש אלמנטים בערימה ומסירה את החלק העליון ביותר אם המחסנית לא ריקה:

def pop(self): if not self.top: raise Exception("Stack Underflow") item = self.top.data self.top = self.top.next return item

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

def peek(self): if not self.top: raise Exception("Stack is empty") return self.top.data

הערה: הממשק של שניהם Stack המחלקות זהות - ההבדל היחיד הוא היישום הפנימי של שיטות המחלקה. זה אומר שאתה יכול לעבור בקלות בין יישומים שונים בלי לדאוג לגבי הפנימיות של השיעורים.

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

כיצד ליישם מחסנית באמצעות המבנים המובנים של Python

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

לפייתון, בהיותה שפה רב-תכליתית ודינמית, אין מחלקת מחסנית ייעודית. עם זאת, מבני הנתונים המובנים שלו, במיוחד רשימות ומחלקת deque מ- collections מודול, יכול לשמש כערימות ללא מאמץ.

שימוש ברשימות Python בתור ערימות

רשימות פייתון יכולות לחקות מחסנית בצורה יעילה למדי בשל האופי הדינמי שלהן והנוכחות של שיטות כמו append() ו pop().

פעולת דחיפה – הוספת אלמנט לראש הערימה היא פשוטה כמו שימוש ב- append() שיטה:
```
stack = []
stack.append('A')
stack.append('B')
```
מבצע פופ - ניתן להשיג את הסרת האלמנט העליון באמצעות ה pop() שיטה ללא שום טיעון:
```
top_element = stack.pop() 
```
מבצע הצצה גישה לחלק העליון מבלי להקפיץ יכולה להתבצע באמצעות אינדקס שלילי:
```
top_element = stack[-1] 
```

שימוש דק שיעור מ אוספים מודול

השמיים deque (קיצור של תור כפול) היא כלי רב תכליתי נוסף להטמעות מחסנית. הוא מותאם להוספות וצפצפות מהירים משני הקצוות, מה שהופך אותו ליעיל מעט יותר עבור פעולות ערימה מאשר רשימות.

אתחול:

from collections import deque
stack = deque()

פעולת דחיפה - בדומה לרשימות, append() נעשה שימוש בשיטה:
```
stack.append('A')
stack.append('B')
```
מבצע פופ - כמו רשימות, pop() השיטה עושה את העבודה:
```
top_element = stack.pop() 
```
מבצע הצצה - הגישה זהה לגישה של רשימות:
```
top_element = stack[-1] 
```

מתי להשתמש באיזה?

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

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

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

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

הצפת מחסנית

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

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

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

מחסנית

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

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

אילוצי זיכרון

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

חששות בטיחות שרשור

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

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

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

סיכום

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

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