10.3 מחסנית ותור הרצאה

מחסנית

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

דמיינו מחסנית כמו בקבוק צר: אנחנו יכולים להשחיל דברים פנימה לבקבוק, וכדי להוציא אותם, אנחנו צריכים לשלוף אותם מהדבר האחרון שהכנסנו עד הדבר הראשון.
למעשה מחסנית היא כמו רשימה מוגבלת, ברשימה אנחנו יכולים לגשת לכל איבר שנרצה כל הזמן ובמחסנית אנחנו יכולים לגשת רק לדבר האחרון שהכנסנו כל הזמן, וכדי לגשת לעוד איברים אנחנו צריכים להוציא עוד ועוד איברים מהמחסנית.
- הקונספט הזה נקרא FILO - first in last out - האיבר הראשון שאנחנו מכניסים למחסנית, יצא תמיד אחרון מהמחסנית.
- דוגמה למימוש stack בפייתון:

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop() if not self.is_empty() else None

    def is_empty(self):
        return len(self.items) == 0

שאלה מודרכת: פלינדרום

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

def is_palindrome(s):
    stack = Stack()

    # Push each character into the stack
    for char in s:
        stack.push(char)

    # Pop characters from the stack and compare with the string
    for char in s:
        if char != stack.pop():
            return False

    return True

תור

תור או באנגלית queue הוא מבנה נתונים שמאוד מזכיר רשימה, תור הוא מיוחד בזכות הצורה שבה אנחנו מכניסים ומוציאים איברים לתור.
- כדי להכניס איברים לתור אנחנו משתמשים בפעולה push (לפעמים זה נקרא enqueue), שדוחפת איברים לתחילת התור. וכדי להוציא איברים אנחנו משתמשים בפעולה pop (לפעמים זה נקרא dequeue), שמוציאה את האיבר הראשון ומחזירה אותו.

- התור הוא דומה קצת למחסנית, רק שהראשון שנכנס לתור, יוצא ראשון. ולשם כך קיים בתור עקרון FIFO - first in, first out - הראשון שנכנס הוא הראשון שיוצא.
- כדי להשתמש בqueue אפשר להשתמש במודול queue
- .

from queue import Queue
q = Queue(maxsize = 3)
q.put('a')
q.put('b')
q.put('c')
print(q.get())
print(q.get())
print(q.get())

- כאשר אפשר להגדיל גודל מרבי לתור, עם put נדחוף איברים לתור ועם get נוציא מהתור.

סיכום

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

תרגול

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