در این جلسه تیم کدگیت را با آموزش پشته در سی شارپ همراهی کنید. پیش نیاز این جلسه شامل موارد زیر است:

  1. آشنایی با متد
  2. آشنایی با شی گرایی
  3. Generic
  4. آشنایی با constructor
  5. آشنایی با for
  6. آشنایی با if
  7. آشنایی با enumerator
  8. آشنایی با استثناها
  9. آشنایی با ارثبری
  10. آشنایی با override
  11. آشنایی با generic

پشته(stack)

پشته یکی از انواع داده‌ساختارها است و برای ذخیره و بازیابی دادهها کاربرد دارد. پشته به شما اجازه دسترسی به یک شی (object) را میدهد، آخرین شی که وارد پشته شده است. اگر ما آخرین شی را حذف کنیم میتوانیم به شی یکی مانده به آخر دسترسی داشته باشیم و همینطور تا آخر …… .ساختار پشته به صورت تصویر زیر است.

پشته در سی شارپ

برای توضیح دادن پشته بهتر است یک مثال ساده بزنیم.مثال در مورد قرار دادن نامه(email هم میشود)است. فرض کنید ما نامه هایی که به دستمان میرسد را روی هم قرار میدهیم پس میتوان نتیجه گرفت نامه ای که بالاتر از همه قرار دارد همین اواخر و زودتر از بقیه به دست شما رسیده است. دومین نامه نسبت به نامه های زیری خود همین ویژگی را دارد. اگر نامه ای بیاید شما آن را در اول قرار می دهید و روی همه نامه های دیگر. معمولا ما با نامه هایی کار داریم که جدید هستند و نامه های قدیمی بعضی از آنها نگه میداریم بعضی از آنها را به زباله می اندازیم!!!

پشته در سی شارپ

این روند که توضیح داده شد تقریبا کاری است که پشته انجام میدهد. پشته مانند نامه ها اول خالی است سپس با آمدن نامه جدید به پشته یک عنصر وارد می شود. با مطالعه نامه میتوانید آن را دور بیندازید یا آن را سر جای قبلش قرار دهید پشته شما می‌توانید دقیقا همین اعمال انجام دهید. خلاصه کارهایی که با پشته میشود انجام داد:

  1. Push: اضافه کردن عنصری به پشته.(آمدن نامه جدید)
  2. Pop: حذف بالاترین(جدیدترین) عنصر در پشته(دور انداختن نامه)
  3. Peek: دسترسی به بالاترین(جدیدترین) عنصر در پشته(بررسی نامه های جدید)
  4. Size: تعداد عناصر پشته (تعداد نامه ها )

برای پیاده سازی ما میتوانیم از دو راه استفاده کنیم:

  1. پیاده سازی پشته در سی شارپ با لیست پیوندی
  2. پیاده سازی پشته در سی شارپ با آرایه

پیاده سازی پشته در سی شارپ با لیست پیوندی

برای پیاده سازی پشته در سی شارپ با لیست پیوندی ابتدا باید با لیست پیوندی و انواع آن آشنا باشید. در آموزش های قبلی در مورد لیست پیوندی صحبت شده و پیشنهاد میشود ابتدا آن را مطالعه کنید سپس به ادامه این آموزش بپردازید.

پیاده سازی لیست پیوندی به طوری که ما را به هدف خودمان برساند بسیار ساده است. برای این کار ما از single linkedlist استفاده میکنیم و هر عنصر جدید(push) که وارد لیست ما شد ما آن را first قرار می دهیم.

پشته در سی شارپ

برای حذف یک عنصر(pop) ما اشاره گره first را به یک خانه جلوتر میبریم و تمام!!!!(به همین سادگی) برای peek صدا زدن ما فقط کافی است first را برگردانیم!!!! حال بهتر است کد توضیحات داده شده را بزنیم.ابتدا کلاس Node میسازیم(در لیست پیوندی توضیح داده شده است).

  public class Node<Item> {

        private Item data;
        private Node<Item> next_node;

        public Node(Item data, Node<Item> next_node) {
            this.data = data;
            this.next_node = next_node;
        }

        public Node(Node<Item> next_node) {
            this.next_node = next_node;
        }

        public Item getData() {
            return data;
        }

        public Node<Item> getNext_node() {
            return next_node;
        }



    }

سپس کلاس دیگری به نام StackWithList میسازیم.در این کلاس stack را میسازیم.

 public class StackWithList<Item> {

        private int N; // size of the stack
        private Node<Item> first; // top of stack


        public StackWithList() {
            N = 0;
            this.first = null;
        }

        public bool isEmpty() {
            return first == null;
        }

        public int size() {
            return N;
        }

        public void push(Item item) {
            Node<Item> oldfirst = first;
            first = new Node<Item>(item, oldfirst);
            N++;

        }

        public Item pop() {
            if (isEmpty())
                throw new System.IndexOutOfRangeException("stack overflow");
            Item item = (Item) first.getData(); // save item to return
            first = first.getNext_node(); // delete first node
            N--;

            return item; // return the saved item
        }

        public Item peek() {
            if (isEmpty())
                throw new System.IndexOutOfRangeException("stack underflow");
            return (Item) first.getData();
        }

        public IEnumerator<Item> GetEnumerator(){
            return new myEnumrator<Item> (first);
        }

    }

کلاس Enumrator هم برای Stack خود مینویسیم.(کاملا مشابه لیست پیوندی)

class myEnumrator<Item>: System.Collections.Generic.IEnumerator<Item>
    {
        private Node<Item> current;

        public myEnumrator(Node<Item> First){
            Node<Item> temp = new Node<Item>(First);
            current = temp;
        }
        #region IEnumerator implementation
        public bool MoveNext ()
        {
            if (!hasNext()) {
                return false;
            }
            //Item item = current.getData();
            current = current.getNext_node ();
            return true;
        }
        public void Reset ()
        {
            throw new NotSupportedException ();
        }
        object System.Collections.IEnumerator.Current {
            get {
                throw new NotSupportedException ();
            }
        }
        #endregion
        #region IDisposable implementation
        public void Dispose ()
        {

        }
        #endregion
        #region IEnumerator implementation
        public Item Current {
            get {
                if (current != null) {
                    return current.getData();
                }
                return default(Item);
            }
        }
        #endregion

        public bool hasNext(){
            if (current.getNext_node() != null)
                return true ;
            return false;
        }

    }

یک main هم برای برنامه خود مینویسیم.

        public static void Main (string[] args)
        {

            StackWithList<String> stack = new StackWithList<String>();
            stack.push("jack");
            stack.push("mike");
            stack.push("dany");
            Console.WriteLine(stack.pop());
            Console.WriteLine("------ items after pop ------");
            foreach(String s in stack){
                Console.WriteLine (s);
            }

            Console.ReadKey ();
        }
    }

در متد main ما یک stack ساختیم و به آن سه string اضافه کردیم. سپس یک عنصر را pop کردیم(آخرین عنصر). سپس یک foreach نوشتیم و کل stack را بعد از pop  چاپ میکند. خروجی به صورت زیر است.

پیاده سازی پشته در سی شارپ با آرایه

در این قسمت به پیاده سازی پشته در سی شارپ توسط آرایه خواهیم پرداخت. ایده کار به این صورت است که ابتدا یک آرایه کوچک در نظر میگیریم(ابتدا به طول دو) و هر بار آرایه ما پر شد طول آن را دو برابر می کنیم. محتوای این آرایه object هایی است که به stack اضافه میشوند. کد زیر پیاده سازی این نوع stack را نشان میدهد.

public class StackWithArray<Item> {
        private Item[] a; // array of items
        private int N;

        public StackWithArray() {
            a =  new Item[2];
        }

        public bool isEmpty() {
            return N == 0;
        }

        public int size() {
            return N;
        }

        private void resize(int capacity) {
            Debug.Assert(capacity>=N);
            Item[] temp =  new Item[capacity];
            for (int i = 0; i < N; i++) {
                temp[i] = a[i];
            }
            a = temp;
        }

        public void push(Item item) {
            if (N == a.Length)
                resize(2 * a.Length); // double size of array if necessary
            a[N++] = item; 
        }

        public Item pop() {
            if (isEmpty())
                throw new System.IndexOutOfRangeException("stack overflow");
            Item item = a[N - 1];
            a[N - 1] = default(Item); 
            N--;
            // shrink size of array if necessary
            if (N > 0 && N == a.Length / 4)
                resize(a.Length / 2);
            return item;
        }

        public Item peek() {
            if (isEmpty()) throw new System.IndexOutOfRangeException("stack underflow");
            return a[N-1];
        }

        public IEnumerator<Item> GetEnumerator(){
            return new ReverseIterator<Item> (N,a);
        }

    }
}

در این جا چون آرایه استفاده میکنیم نیاز به یک iterator که از بالای Stack شروع به خواندن کند، داریم. اسم این کلاس reverseIterator میگذاریم.

class ReverseIterator<Item>: System.Collections.Generic.IEnumerator<Item>
    {

        private int i;
        private Item[] data;

        public ReverseIterator(int N,Item[] data) {
            i = N;
            this.data = data;
        }


        #region IEnumerator implementation
        public bool MoveNext ()
        {
            if(!hasNext()){
                return false;
            }
            i--;
            return true;
        }
        public void Reset ()
        {
            throw new NotImplementedException ();
        }
        object System.Collections.IEnumerator.Current {
            get {
                throw new NotImplementedException ();
            }
        }
        #endregion
        #region IDisposable implementation
        public void Dispose ()
        {

        }
        #endregion
        #region IEnumerator implementation
        public Item Current {
            get {
                return data [i];
            }
        }
        #endregion

        public bool hasNext() {
            return i > 0;
        }

    }

متد main هم دقیقا شبیه پیاده سازی پشته با لیست پیوندی است.

public static void Main (string[] args)
        {
            StackWithArray<String> mystack = new StackWithArray<String>();
            mystack.push("jack");
            mystack.push("mike");
            mystack.push("dany");

            Console.WriteLine(mystack.pop());
            Console.WriteLine("------ items after pop ------");

            foreach(string s in mystack){
                Console.WriteLine(s);
            }

            Console.ReadKey ();
        }

Download “دانلود سورس پشته در سی شارپ” Stack-in-Csharp-www.codegate.ir_.rar – 83 بار دانلود شده است – 44 کیلوبایت

پسورد: www.codegate.ir