מבני נתונים: מחסנית (Stack) - אלגוריתמים, תרגילים ופתרונות מלאים

עקרונות יסוד במבנה נתונים מחסנית (Stack)

• הגדרת המחסנית: מחסנית היא מבנה נתונים מופשט הפועל לפי עיקרון LIFO (Last-In, First-Out) — האיבר שנכנס אחרון הוא הראשון לצאת.

• פעולות יסוד במחסנית:

  • Push(val) — הכנסת איבר בראש המחסנית.

  • Pop() — הוצאת האיבר מראש המחסנית והחזרת ערכו.

  • Top() / Peek() — צפייה בערכו של האיבר בראש המחסנית ללא הוצאתו.

  • IsEmpty() — בדיקה בוליאנית האם המחסנית ריקה מאיברים.

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

בדיקת ייחודיות איברים במחסנית (AreAllElementsUnique)

• תיאור המשימה: בדיקה האם כל האיברים במחסנית של מספרים שלמים שונים זה מזה (אינם מכילים כפילויות).

• חתימת הפעולה: public static bool AreAllElementsUnique(Stack<int> s)

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

• צעדי האלגוריתם:

  1. הקצאת מחסנית עזר ראשית tempMain לשמירת האיברים שכבר נבדקו.

  2. הגדרת משתנה בוליאני isUnique = true לסימון תוצאת הבדיקה.

  3. בלולאה ראשית (while (!s.IsEmpty() && isUnique)):

  • שליפת האיבר הנוכחי מראש המחסנית: int current = s.Pop().

  • הקצאת מחסנית עזר משנית tempCheck להשוואת האיבר הנוכחי.

  • בלולאה פנימית (while (!s.IsEmpty())): שליפת כל איבר val = s.Pop(), בדיקה אם val == current (אם כן, נקבע isUnique = false), ודחיפתו ל-tempCheck.

  • החזרת האיברים שנבדקו מ-tempCheck בחזרה ל-s בלולאה: while (!tempCheck.IsEmpty()) s.Push(tempCheck.Pop()).

  • דחיפת האיבר current ל-tempMain לצורך שחזור בסוף הטיפול.

  1. שחזור מלא של המחסנית המקורית: העברת כל האיברים מ-tempMain בחזרה ל-s בלולאה while (!tempMain.IsEmpty()) s.Push(tempMain.Pop()).

  2. החזרת הערך הבוליאני isUnique.

public static bool AreAllElementsUnique(Stack<int> s)
{
    Stack<int> tempMain = new Stack<int>();
    bool isUnique = true;

    while (!s.IsEmpty() && isUnique)
    {
        int current = s.Pop();
        Stack<int> tempCheck = new Stack<int>();

        // בדיקת האיבר הנוכחי מול כל שאר האיברים שנשארו במחסנית
        while (!s.IsEmpty())
        {
            int val = s.Pop();
            if (val == current)
            {Reader
                isUnique = false;
            }
            tempCheck.Push(val);
        }

        // החזרת האיברים שנבדקו בחזרה ל-s
        while (!tempCheck.IsEmpty())
        {
            s.Push(tempCheck.Pop());
        }

        // שמירת האיבר שנבדק במחסנית עזר לשחזור המחסנית המקורית
        tempMain.Push(current);
    }

    // שחזור מלא של המחסנית המקורית
    while (!tempMain.IsEmpty())
    {
        s.Push(tempMain.Pop());
    }

    return isUnique;
}

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

• תיאור המשימה: קבלת מחסנית המכילה אותיות אנגליות קטנות בטווח 'a' עד 'z' והחזרת התו המופיע במספר הפעמים הגבוה ביותר (התו השכיח ביותר).

• שימוש בטבלת ASCII ומערך מונים (Counting Array):

  • ערך ה-ASCII של התו 'a' הוא $97$.

  • ערך ה-ASCII של התו 'z' הוא $122$.

  • טווח האותיות הקטנות באלפבית האנגלי מכיל $122 - 97 + 1 = 26$ תווים.

  • ניתן למפות כל תו לאינדקס במערך מונים בגודל $26$ באמצעות הנוסחה: $\text{index} = \text{code} - 97$.

• צעדי האלגוריתם:

  1. הגדרת מערך מונים בגודל $26$: int[] counts = new int[26].

  2. הקצאת מחסנית עזר Stack<char> temp = new Stack<char>() לשמירת תוכנה של המחסנית המקורית.

  3. ריקון המחסנית המקורית בלולאה: שליפת כל תו char ch = s.Pop(), הגדלת המונה המתאים במערך counts[ch - 97]++, ודחיפת התו ל-temp.

  4. שחזור המחסנית המקורית על ידי ריקון temp בחזרה ל-s.

  5. מציאת האינדקס בעל הערך המקסימלי במערך המונים counts.

  6. המרת האינדקס המקסימלי בחזרה לתו ASCII על ידי הוספת $97$ והחזרתו מתהליך החישוב.

public static char MostFrequentChar(Stack<char> s)
{
    int[] counts = new int[26];
    Stack<char> temp = new Stack<char>();

    // סריקת המחסנית ועדכון מערך המונים
    while (!s.IsEmpty())
    {
        char ch = s.Pop();
        counts[ch - 'a']++;
        temp.Push(ch);
    }

    // שחזור המחסנית המקורית
    while (!temp.IsEmpty())
    {
        s.Push(temp.Pop());
    }

    // מציאת התו בעל התדירות הגבוהה ביותר
    int maxIndex = 0;
    for (int i = 1; i < 26; i++)
    {
        if (counts[i] > counts[maxIndex])
        {
            maxIndex = i;
        }
    }

    return (char)(maxIndex + 'a');
}

חיבור איברים מתוואים בשתי מחסניות (SumStacks)

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

• חתימת הפעולה: public static Stack<int> SumStacks(Stack<int> s1, Stack<int> s2)

• צעדי האלגוריתם:

  1. הקצאת שלוש מחסניות עזר: temp1, temp2, ו-resultTemp.

  2. ריקון ושרידה: בלולאת while (!s1.IsEmpty()) שליפת האיברים val1 = s1.Pop() ו-val2 = s2.Pop(), שמירתם במחסניות temp1 ו-temp2 בהתאמה, ודחיפת סכומם val1 + val2 ל-resultTemp.

  3. שחזור מקורות: ריקון temp1 ו-temp2 בחזרה ל-s1 ו-s2 בהתאמה.

  4. הפיכת מחסנית התוצאה: כיוון שהסכומים נדחפו ל-resultTemp החל מראש המחסניות המקוריות, סכום האיברים הראשונים נמצא בתחתית resultTemp. על כן, מעבירים את איברי resultTemp למחסנית חדשה result בלולאה while (!resultTemp.IsEmpty()) result.Push(resultTemp.Pop()) כדי להפוך את הסדר כך שראש המחסנית יכיל את סכום האיברים הראשונים.

  5. החזרת מחסנית התוצאה result.

public static Stack<int> SumStacks(Stack<int> s1, Stack<int> s2)
{
    Stack<int> temp1 = new Stack<int>();
    Stack<int> temp2 = new Stack<int>();
    Stack<int> resultTemp = new Stack<int>();

    // ריקון המחסניות והכנסת הסכומים למחסנית עזר
    while (!s1.IsEmpty())
    {
        int val1 = s1.Pop();
        int val2 = s2.Pop();
        temp1.Push(val1);
        temp2.Push(val2);
        resultTemp.Push(val1 + val2);
    }

    // שחזור המחסניות המקוריות
    while (!temp1.IsEmpty())
    {
        s1.Push(temp1.Pop());
        s2.Push(temp2.Pop());
    }

    // הפיכת מחסנית התוצאה לסדר הנכון (כך שראש המחסנית יהיה סכום האיברים הראשונים)
    Stack<int> result = new Stack<int>();
    while (!resultTemp.IsEmpty())
    {
        result.Push(resultTemp.Pop());
    }

    return result;
}

מיזוג שתי מחסניות ממויינות (MergeSortedStacks)

• תיאור המשימה: קבלת שתי מחסניות ממויינות s1 ו-s2 ומיזוגן למחסנית חדשה ממויינת אחת, כך שהערך הגדול ביותר יימצא בראש המחסנית.

• חתימת הפעולה: public static Stack<int> MergeSortedStacks(Stack<int> s1, Stack<int> s2)

• צעדי האלגוריתם:

  1. הקצאת מחסנית עזר tempResult.

  2. מיזוג בלולאה בסדר עולה: כל עוד שתי המחסניות אינן ריקות (!s1.IsEmpty() && !s2.IsEmpty()), מתבצעת השוואה בין s1.Top() ל-s2.Top(). האיבר הקטן מביניהם נשלף ונדחף ל-tempResult.

  3. טיפול בשאריות: העברת יתרת האיברים ממחסנית s1 (אם נותרו) ל-tempResult, ולאחר מכן העברת יתרת האיברים ממחסנית s2 (אם נותרו) ל-tempResult.

  4. הפיכת התוצאה: ב-tempResult האיברים סודרו בסדר עולה (איברים קטנים בתחתית, איברים גדולים בראש). כדי לקבל מחסנית תוצאה שבה הערך הגדול ביותר נמצא בראש, מעבירים את איברי tempResult למחסנית תוצאה סופית result בלולאה while (!tempResult.IsEmpty()) result.Push(tempResult.Pop()).

  5. החזרת המחסנית הממויינת result.

public static Stack<int> MergeSortedStacks(Stack<int> s1, Stack<int> s2)
{
    Stack<int> tempResult = new Stack<int>();

    // מיזוג האיברים למחסנית זמנית (בסדר עולה)
    while (!s1.IsEmpty() && !s2.IsEmpty())
    {
        if (s1.Top() < s2.Top())
        {
            tempResult.Push(s1.Pop());
        }
        else
        {
            tempResult.Push(s2.Pop());
        }
    }

    // העברת יתר האיברים מ-s1
    while (!s1.IsEmpty())
    {
        tempResult.Push(s1.Pop());
    }

    // העברת יתר האיברים מ-s2
    while (!s2.IsEmpty())
    {
        tempResult.Push(s2.Pop());
    }

    // הפיכת התוצאה כך שהערך הגדול ביותר יהיה בראש המחסנית
    Stack<int> result = new Stack<int>();
    while (!tempResult.IsEmpty())
    {
        result.Push(tempResult.Pop());
    }

    return result;
}

העברת מופעי ערך המקסימום לראש המחסנית (MoveMaxToTop)

• תיאור המשימה: העברת כל המופעים של הערך המקסימלי במחסנית s לראש המחסנית, תוך שמירה על סדרם היחסי של שאר האיברים.

• חתימת הפעולה: public static void MoveMaxToTop(Stack<int> s)

• צעדי האלגוריתם (בחלוקה ל-3 שלבים):

  1. תנאי עצירה מוקדם: אם המחסנית ריקה (s.IsEmpty()), הפעולה מסתיימת מיידית.

  2. שלב 1 — מציאת הערך המקסימלי במחסנית:

  • הגדרת משתנה int maxVal = s.Top() והקצאת מחסנית עזר temp.

  • סריקת המחסנית s בלולאת while (!s.IsEmpty()): שליפת כל איבר val = s.Pop(), עדכון maxVal במידה ו-val > maxVal, ודחיפת האיבר ל-temp.

  1. שלב 2 — ספירת מופעי המקסימום והחזרת שאר האיברים:

  • אתחול מונה int countMax = 0.

  • סריקת מחסנית temp בלולאת while (!temp.IsEmpty()): שליפת איבר val = temp.Pop(). אם val == maxVal, מגדלים את המונה ++countMax. אחרת, דוחפים את האיבר בחזרה למחסנית המקורית s.Push(val).

  1. שלב 3 — דחיפת כל מופעי המקסימום לראש המחסנית:

  • הרצת לולאת פור for (int i = 0; i < countMax; i++) ודחיפת הערך maxVal בחזרה ל-s כמספר מופעיו.

public static void MoveMaxToTop(Stack<int> s)
{
    if (s.IsEmpty()) return;

    Stack<int> temp = new Stack<int>();

    // שלב 1: מציאת הערך המקסימלי במחסנית
    int maxVal = s.Top();
    while (!s.IsEmpty())
    {
        int val = s.Pop();
        if (val > maxVal)
        {
            maxVal = val;
        }
        temp.Push(val);
    }

    // שלב 2: ספירת מופעי המקסימום והחזרת שאר האיברים למחסנית
    int countMax = 0;
    while (!temp.IsEmpty())
    {
        int val = temp.Pop();
        if (val == maxVal)
        {
            ++countMax;
        }
        else
        {
            s.Push(val);
        }
    }

    // שלב 3: דחיפת כל מופעי המקסימום לראש המחסנית
    for (int i = 0; i < countMax; i++)
    {
        s.Push(maxVal);
    }
}