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

מחסנית

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

דמיינו מחסנית כמו בקבוק צר: אנחנו יכולים להשחיל דברים פנימה לבקבוק, וכדי להוציא אותם, אנחנו צריכים לשלוף אותם מהדבר האחרון שהכנסנו עד הדבר הראשון.
למעשה מחסנית היא כמו רשימה מוגבלת, ברשימה אנחנו יכולים לגשת לכל element שנרצה כל הזמן ובמחסנית אנחנו יכולים לגשת רק לדבר האחרון שהכנסנו כל הזמן, וכדי לגשת לעוד elements אנחנו צריכים להוציא עוד ועוד elements מהמחסנית.
- הקונספט הזה נקרא FILO - first in last out - הelement הראשון שאנחנו מכניסים למחסנית, יצא תמיד אחרון מהמחסנית.
- דוגמה למימוש 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

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

בדוק האם מחרוזת היא פלינדרום בשימוש במחסנית בלבד.
- תזכורת: פלינדרום היא סדר של elements שנקראים אותו הדבר הפוך ורגיל.
דוגמה לפלינדרום: 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

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

- הqueue הוא דומה קצת למחסנית, רק שהראשון שנכנס לqueue, יוצא ראשון. ולשם כך קיים בqueue עקרון 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())

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

סיכום

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

תרגול

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