پشته یا همون Stack به زبون جاوا (زبون آدمیزاد 😈)

​

سلام سلام صد تا سلام به تو ستاره (مفهوم استعاری از ستاره میباشد :)

خوب بریم ببینیم Stack چی میگه.

‫پشته‬‫‪،‬‬ ‫ساختمان‬ ‫داده‬ ‫اي‬ ‫است‬ ‫كه‬ ‫حذف‬ ‫و‬ ‫اضافه‬ ‫از‬ ‫بالاي‬ ‫آن‬ ‫انجام‬ ‫مي‌شود‬ ‫‪.‬‬‫پشته‬‫ را FILO ‫مي‌نامند‬ ‫‪،‬‬‫چون‬ ‫آخرين‬ ‫عنصر‬ ‫وارد‬ ‫شده‬ ‫در‬ ‫آن‪،‬‬ ‫اولين‬ ‫عنصري‬ ‫است‬ ‫كه‬ ‫از‬ ‫آن‬ ‫برداشته‬ ‫مي‌شود‬ ‫‪.‬‬‫‪top‬‬‫‪‬‬ ‫مشخص‬ ‫كننده‬ ‫عنصر‬ ‫بالايي‬ ‫پشته میباشد‬:

مطابق شکل ابتدا ما یک پشته خالی داریم. بعد با هر عمل push (یعنی هل دادن- شما میتونید اضافه کردن به پشته در نظر بگیرید) ما یک عنصر (که جلوتر توی کد ما بهش item) اضافه میشه. و هربار به بالای قبلی اضافه میشه. و با هر بار عمل pop اون ها از بالا به ترتیب خاج میشن. راستی O این عبارت هم از مرتبه (1)O هست.

برای درک بهتر میتونیم اون رو به دسته از کتاب تعمیم بدیم که روی هم قرار دارن. برای برداشتن باید چیکار کنیم؟ آفرین یکی از بالا برداریم.
به شکل زیر نوجه کنید:

خیلی وقت ها این مفهوم توی برنامه نویسی هم استفاده میشه. مثلا وقتی که تابع بازگشتی داریم. یا مثلا برای تبدیل postfix ، infix و prefix (شاید برای این ها هم مطلب نوشتم، مفاهیم ساده ای دارند)

خوب حالا بریم با زبون برنامه نویسی جاوا (Java) ببینیم چطوری این سیستم کار میکنه (نگران این که جاوا بلد نیستید نباشید، مفهوم رو بگیرید. تازه اون رو هم ساده میگم که در کنارش جاوا هم یادبگیرید.)

بریم؟؟‌ (یه لبخند، نفس عمیق، یه قلب قهوه، چایی، آب) رفتیم که بریم.

خب من اولش یه interface ساده ساختم برای ساده سازی کار (interface موقعی به کار میره که ما بخوایم ایده بهتری از کارهامون داشته باشیم که مثلا میخوایم چیکار کنیم، بعدا دربارش یه وبلاگ کامل مینویسم)

public interface StackInterFace {
    
        public boolean push (int item); // add item to stack
        public int pop();       // remove the last item and push back 
        public void stackIsFull();      // when stack is full call
    }

کدی که نوشتم یعنی من تابع push، pop و پشته ام پر هست رو دارم و باید از این ها استفاده کنم (این ها بیشتر برای خوانایی کد هست و این که یادم نره باید چه توابعی رو پیاده سازی کنم. البته هزار تا دلیل دیگه هم داره ولی به همین بسنده میکنم)

قسمت بعدی داستان ساختن یک کلاس جدید به اسم پشته هست (اما نیازی نبود، صرفا با این کار کار خودمو راحت کردم، که اگه بعدا خواستم از این مفهوم استفاده کنم راحت باشم) نترسین خیلی وارد داستان شی گرایی نمیشیم، مفهوم رو بگیرید:)

public static class Stack implements StackInterFace {

        private int length = 0; // length of stack
        

        private int[] stack;
        private int top = -1;


        // constactor
        public Stack (int length ){
            this.length = length;
            stack = new int[length];
        }

        //gettr for stack
        public int[] getStack(){
            return stack;
        }
    }

خوب برای این که ما بتونیم از توابعی که از پیش تو interface تعریف کزدیم استفاده کنیم باید از استفاده implements تا به کلاس مورد نظر بگیم که داداش تو حتما باید اون توابع از پیش تعریف شده رو داشته باشی. (پیاده سازی اون توابع در کد بالا نیست و جلو تر میبینیم)

چیز هایی که تو این کلاس تعریف شده:

1. تعریف متغیر اندازه، برای تایین ماکزیمم خانه هایی که پشته دارد.
2. یک لیست که بیانگر پشته هست.
3. متغیر top که نشون میده اندیس بالایی ترین خانه پشته چند هست
4. توی تابع (متد) سازنده، تعداد خانه ها رو همون زمانی که یه شی (object) جدید ساخته میشه تعیین میکنیم و لیست پشته رو با اون خانه ها تنظیم میکنیم
5. و درنهایت با توجه به این که متغیر stack یک لیست خصوصی (private) است (به دلیل محصورسازی) برای آن متدی برای دریافت تعیین میکنم

خوب حالا باید توی کلاس Stack که تعریف کردیم اون سه تا تابع رو بیاریم:

این جوری (Override@ برای این هست که ما داریم اون رو دوباره مینویسمش، جون از interface داریم اون رو میاریم)

خوب از چک کردن برای این که تابه پر هست یا نه شروع میکنیم:

@Override
    public void stackIsFull() {
        System.err.println(&quotStack is full.&quot);
    }

همون طور که میبینید، بسیار ساده هست، اگه پر بود ارور میده و میگه پشته پر شده.

حالا نوبت متد push هست، اون هم بسیار راحته :

@Override
    public boolean push(int item) {
        if (top >= length-1 ){
            stackIsFull();
            return false;
        }
        top++;
        stack[top] = item;
        return true;
    }

اول چک میکنه که ببینه پر شده پشته یا نه (اگه پر شده بود، تابع پر بودن تابع رو صدا میزنه) و برامون خروجی false رو برمیگردونه، اگه خونه خالی داشتیم که بتونیم آیتم رو اضافه کنیم یکی به نشون دهنده این که بالاترین عنصر (یعنی همون top) اضافه میکنیم و به پشته اون عنصر رو اضافه میکینم. و تمام.

حالا آخرین مرحله مون مونده که باید بهش برسیم و اون هم چیزی نیست بجز pop :

@Override
    public int pop() {
        if (top==-1){
            return -1;
        }
        int item = stack[top];
        stack[top] = 0;
        top--;
        return item;// first return the top and then  (top -1 )
    }

خوب این هم بسیار ساده هست

اول چک میکنه که پشته خالی هست یا نه، بعد متغیر جدیدی به اسم item میسازه و اون عنصر مورد نظر توش میذاره، جای اون عنصر تو پشته صفر میذاره، از top که نشون دهنده اندیس بالاترین خونه بود رو یکی کم میکنه و در آخر هم خروجی رو برمیگردونه.

خوب من برای تست که تابع تست هم نوشتم(سعی کنید اعداد و این ها رو تغییر بدید تا ببینید چی میشه)

public static int[] testStack(){

        Stack stack = new Stack(5);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.pop();
        stack.push(5);
        stack.pop();
        stack.push(6);
        stack.pop();
        stack.push(7);
        stack.pop();

        return stack.getStack();
    }

خوب درود بر ما که تونستیم به همین راحتی یه کد جالب و پرکاربرد توی برنامه نویسی بزنیم که توی ساختمان داده ها بسیار پرکاربرد و مهمه.

نمایش کلی برنامه رو میتونید توی گیت هاب من پیدا کنید.

برای دیدن کد ها کلیک کنید.

​​میتونید عین همین متن رو تو وبلاگ شخصی من هم بخونید (همینه اما ژانگولرش بیشتره :)