using System;

namespace Ex

{

    public class Program

    {

        FindMin

            int.MaxValue

        Remove

        /*

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

        הערה: יש לשמור על המחסנית המקורית

        */

        public static Stack<int> Clone (Stack<int> st)

        {

            Stack<int> stCpy = new Stack<int>();   // העתק של מחסנית המקור  

            Stack<int> tmp = new Stack<int>();   // מחסנית עזר

            int item;

            while (!st.IsEmpty())      // ריקון מחסנית המקור למחסנית העזר

                tmp.Push(st.Pop());

            while (!tmp.IsEmpty())

            {

                st.Push(tmp.Pop());

                stCpy.Push(st.Top());

                /* דרך נוספת

                item = tmp.Pop();

                st.Push(item);

                stCpy.Push(item);

                */

            }

            return stCpy;

        }

        /*      

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

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

הערה: יש לשמור על מבנה המחסנית

        */

        /* תיעוד

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

        ומחזירה אמת אם המספר מופיע במחסנית, אחרת שקר

        הערה: יש לשמור על מבנה המחסנית

        */

        public static bool IsExist (Stack<int> st, int num)

        {

            Stack<int> tmp = new Stack<int>();   // מחסנית עזר

            int item;

            bool flag = false;

            while (!st.IsEmpty() && !flag)

            {

                item = st.Pop();

                if (item==num)

                    flag=true;

                tmp.Push(item);

            }

            while (!tmp.IsEmpty())

                st.Push(tmp.Pop());

            return flag;    

        }

/*      

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

ומחזירה את מספר המופעים של הערך במחסנית.

הערה: בתום הפעולה המחסנית צריכה להישאר ללא שינוי

    */

        /*

        תיעוד

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

        הפעולה מחזירה את מספר הפעמים של הערך במחסנית

        הערה: הפעולה שומרת על מבנה המחסנית

        */

        public static int cntNum (Stack<int> st, int num)

        {

            Stack<int> tmp = new Stack<int>();   // מחסנית עזר

            int cnt=0;

            int item;

            while (!st.IsEmpty())

            {

                item = st.Pop();

                if (item==num)

                    cnt++;

                tmp.Push(item);

                /* אפשרות נוספת לפתרון

                if (st.Top()==num)

                    cnt++;

                tmp.Push(st.Pop());

                */

            }

            while (!tmp.IsEmpty())

            {

                st.Push(tmp.Pop());

            }

            return cnt;

        }

        /*

        הפעולה מקבלת מצביע למחסנית מטיפוס מספר שלם

        ומחזירה את גודל המחסנית

        */

        public static int Size (Stack<int> st)

        {

            Stack<int> tmp = new Stack<int>();   // בניית מחסנית עזר    

            int cnt=0, item;    

            while (!st.IsEmpty())   //  כל עוד המחסנית לא ריקה

            {

                cnt++;

                item = st.Pop();

                tmp.Push(item);

                /*

                הערה:

                בימקום שתי השורות האחרונות שרשמנו ניתן לרשום בקצרה שורה אחת בלבד באופן הבא:

                tmp.Push(st.Pop());

                */

            }

            while (!tmp.IsEmpty())

            {

                st.Push(tmp.Pop()); 

            }

            return cnt;

        }

        public static void Main (string[] args)

        {

            Stack<int> st = new Stack<int>();   // הגדרה ובנייה של מחסנית

            int i;

            for (i=90; i>=10; i-=10)

            {

                st.Push(i);      // הכנסת איברים למחסנית

            }

            //Console.WriteLine (st.ToString());       // הדפסת איברי המחסנית החל מראש המחסנית ועד לתחתית המחסנית

            /*

            הפלא המתקבל הוא

            top[10,20,30,40,50,60,70,80,90]bottom

            */

            //Console.WriteLine(Size(st));    // 9

            //Console.WriteLine(IsExist(st,90));   // true

            Console.WriteLine(Clone(st).ToString());

        }

    }

}

​

​

/*

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

ומחזירה את מספר המופעים של הערך במחסנית.

הערה: בתום הפעולה המחסנית צריכה להישאר ללא שינוי

​

​

​

​

​

​

​

​

​

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

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

הערה: יש לשמור על מבנה המחסנית

​

​

​

​

​

​

​

​

כתוב פעולה שמקבלת מצביע למחסנית של מספרים שלמים, ומחזירה העתק של המחסנית

הערה: יש לשמור על מבנה המחסנית

*/

​

​

​

​

​

​

​

​

/*

מחסנית היא מבנה נתונים מופשט המכיל אוסף סדור של איברים מאותו סוג.

למחסנית מוגדר פתח אחד שהוא ראש המחסנית.

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

שיטת הניהול של ההכנסה וההוצאה ממחסנית נקראת שיטת

LIFO

Last In First Out

כלומר, האחרון שנכנס הוא הראשון שיוצא.

​

​

​

​

​

מחסנית היא מבנה נתונים דינאמי,

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

מחסנית אינה מוגבלת במספר האיברים שניתן להכניס אליה.

מחסנית שאין בה איברים היא מחסנית ריקה.

​

​

​

​

​

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

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

מהמחסנית, ולאחר-מכן, העברת הערכים חזרה אל מחסנית המקור,

באופן זה, המבנה המקורי של המחסנית נשמר.

סדר איברי המחסנית המקורית נשמר.

​

ברוב המקרים נרצה לשמור על המחסנית המקורית!

​

​

​

​

​

​

​

המחלקה

Stack<T>

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

T

​

(מחלקה גנרית, כלומר כללית)

​

הפעולות המוגדרות על מחסנית הן:

הכנסת איבר (לראש המחסנית)

הוצאת איבר (מראש המחסנית, והחזרת ערכו)

הצצה לאיבר הנמצא בראש המחסנית מבלי להוציאו (החזרת ערכו של האיבר הנמצא בראש המחסנית ללא הוצאת האיבר)

/*

בנוסף, קיימת פעולה בונה מחסנית, פעולה המחזירה אמת אם המחסנית ריקה אחרת שקר, ופעולה המחזירה מחרוזת המתארת את איברי המחסנית (מראשה ועד סופה)

​

הערה חשובה: לפני שימוש בפעולות של הוצאת איבר ו/או הצצה לראש המחסנית,

חובה לבדוק תחילה האם המחסנית איננה ריקה.

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

ניסיון גישה למבנה נתונים ריק לשם הוצאת איבר או הצצה לראש המבנה הוא שגיאה!!!

​

נראה כעת ממשק של המחלקה מחסנית.

מימוש נראה בהמשך.

​

​

​

​

דוגמאות:

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

הפעולה תכניס למחסנית את האיברים הבאים מהסוף להתחלה:

10,20,30,...,90

ותדפיס את איברי המחסנית.

כלומר, האיבר בראש המחסנית יהיה 10, והאיבר בתחתית המחסנית יהיה 90.

​

​

​

​

​

​

​

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

הפעולה תחשב ותחזיר את גודל המחסנית

(מספר האיברים הקיימים בה)

הערה: חובה לשמור על המחסנית המקורית.

​

​

​

​

​

​

​

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

ומחזירה את מספר המופעים של הערך במחסנית.

הערה: בתום הפעולה המחסנית צריכה להישאר ללא שינוי

​

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

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

הערה: יש לשמור על מבנה המחסנית

​

כתוב פעולה שמקבלת מצביע למחסנית של מספרים שלמים, ומחזירה העתק של המחסנית

הערה: יש לשמור על מבנה המחסנית

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

*/

​

​

​

​

// המחלקה חוליה

public class Node<T> 

{

    private T value;

    private Node<T> next;

    public Node (T value)

    {

        this.value=value;

        this.next=null;

    }

​

    public Node (T value, Node<T> next)

    {

        this.value=value;

        this.next=next;

    }

    public T GetValue()

    {

        return this.value;

    }

​

    public Node<T> GetNext()

    {

        return this.next;

    }

    public void SetValue (T value)

    {

        this.value=value;

    }

    public void SetNext(Node<T> next)

    {

        this.next=next;

    }

​

    // הפעולה מחזירה אמת אם קיימת חוליה עוקבת, אחרת מחזירה שקר

    public bool HasNext()

    {

       return this.next != null;

    }

    public override String ToString()

    {

        return this.value.ToString();

        // שורה זו מחזירה מחרוזת של ערכי כל שרשרת החוליות

         // אבל, בקוד המקורי של תוכנית הלימודים זה לא בשימוש, אלא יש להחזיר מחרוזת של חוליה אחת בלבד

        //return "("+this.left+" "+this.next()+")";

    }

}

​

​

​

​

​

​

​

​

// המחלקה מחסנית

public class Stack<T> 

{

    private Node<T> first;

    public Stack()

    {

        this.first=null;

    }

    public bool IsEmpty()

    {

        return this.first==null;

    }

    public void Push (T x)

    {

        this.first=new Node<T> (x,this.first);

    }

      public T Pop ()

    {

        T x=this.first.GetValue();

        this.first=this.first.GetNext();

        return x;

    }

    public T Top ()

    {

        return this.first.GetValue();

    }

    public override String ToString()

    {

        String str="top[";

        Node<T> pos = this.first;

        while (pos!=null)

        {

            str=str+pos.GetValue().ToString();

            if (pos.GetNext()!=null)

                str=str+",";

            pos=pos.GetNext();

        }

        str=str+"]bottom";

        return str;

    }

}

​

​

// המחלקה תור

public class Queue<T> 

{

    private Node<T> first;

    private Node<T> last;

    public Queue ()

    {

        this.first=null;

        this.last=null;

    }

    public bool IsEmpty()

    {

        return this.first==null;

    }

    public void Insert (T x)

    {

        Node<T> temp = new Node<T>(x);

        if (first==null)

            first=temp;

        else

            last.SetNext(temp);

        last=temp;

    }

    public T Remove ()

    {

        T x=this.first.GetValue();

        this.first=this.first.GetNext();

        if (first==null)

            last=null;

        return x;

    }

    public T Head ()

    {

        return this.first.GetValue();

    }

    public override String ToString ()

    {

        String str="head[";

        Node<T> pos = this.first;

        while (pos!=null)

        {

            str=str+pos.GetValue().ToString();

            if (pos.GetNext()!=null)

                str=str+",";

            pos=pos.GetNext();

        }

        str=str+"]end";

        return str;

    }

​

}

​

​

​

​

​

​

​

// המחלקה חוליה בינארית

public class BinNode<T>

{

    private T value;             

    private BinNode<T> left;     

    private BinNode<T> right;

    public BinNode (T x)

    {

        this.value = x;

        this.left = null;

        this.right = null;

    }

    public BinNode (BinNode<T> left, T x, BinNode<T> right)

    {

        this.value = x;

        this.left = left;

        this.right = right;

    }

    public T GetValue()

    {

        return this.value;

    }

    public BinNode<T> GetLeft()

    {

        return this.left;

    }

    public BinNode<T> GetRight()

    {

        return this.right;

    }

    public bool HasLeft()

    {

        if (this.left!=null) 

            return true;

        return false;

    }

    public bool HasRight()

    {

        if (this.right!=null) 

            return true;

        return false;

    }

    public void SetValue(T x)

    {

        this.value = x;

    }

    public void SetLeft(BinNode<T> left)

    {

        this.left = left;

    }

    public void SetRight(BinNode<T> right)

    {

        this.right = right;

    }

    public override String ToString ()

    {

         // שורה זו מחזירה מחרוזת של ערכי העץ כולו, או לחילופין את ערכי כל שרשרת חוליות דו-כיוונית

         // אבל, בקוד המקורי של תוכנית הלימודים זה לא בשימוש, אלא יש להחזיר מחרוזת של חוליה אחת בלבד

        //return "("+this.left+" "+this.value.ToString()+" "+this.right+")";

        return this.value.ToString();

    }

}

​

​

​

​

​

​

​