پشته جاوا

Stack در جاوا معمولاً به معنای کلاسی از مجموعه Framework است که رابط List را پیاده سازی می کند. این بر اساس اصل ساختار داده Stack کار می کند که برای سازماندهی یکی از انواع حافظه استفاده می شود. همچنین می تواند بخشی از حافظه برای نگهداری داده ها باشد، در این مقاله ابتدا به کلاس Stack می پردازیم ، روش های آن را در نظر می گیریم و مثال می زنیم. اما ما همچنین در مورد ساختار داده ای مانند Stack و آنچه از آن استفاده می شود صحبت خواهیم کرد.

Stack Data Structure چیست؟

اول از همه، بیایید نگاهی گذرا به چیستی ساختار داده پشته بیندازیم. این یک ساختار داده خطی است که بر اساس اصل Last-in-First-out (LIFO) است. یه جورایی ضد صفه یک دسته کارت یا یک دسته کتاب را در یک جعبه تصور کنید. کتابی که ابتدا در پشته گذاشتید در پایین است، و اولین کتابی که از جعبه بیرون می آوریم، کتابی است که در بالا قرار داشت - یعنی کتابی که آخرین بار وارد جعبه شد. در اینجا یک تصویر گیف برای نشان دادن این اصل وجود دارد. اینجا چه خبره؟ ما فلاسکی داریم که هر بار فقط یک توپ می تواند در آن ضربه بزند. اولی در فلاسک یک توپ نارنجی است، سپس بنفش و در نهایت سبز (از کسانی که نام دقیق این رنگ ها را می دانند عذرخواهی می کنم). اما برای اینکه یک توپ نارنجی را از پشته فلاسک خود بیرون بیاوریم، باید ابتدا توپی را که آخرین بار به آنجا رسیده است (سبز) و سپس توپی را که ماقبل آخری بوده است (اما در زمان استخراج آخرین توپ است) استخراج کنیم. یک). ساختار داده پشته ای در جاوا یا هر جای دیگر در برنامه نویسی دارای دو عملیات مهم push و pop است . عملیات فشار یک عنصر را به پشته وارد می کند و عملیات پاپ یک عنصر را از بالای پشته حذف می کند.

ساختار داده Stack برای چیست؟

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

Java Stack Class of Collection Framework

در Java Stack Class یک کلاس از چارچوب مجموعه است که رابط List را پیاده سازی کرده و کلاس Vector را گسترش می دهد. همچنین اینترفیس های Collection، Iterable، Cloneable، Serializable را پیاده سازی می کند. همانطور که احتمالا قبلاً حدس زده اید این کلاس نشان دهنده پشته اشیاء LIFO است. در اینجا فراخوانی سازنده کلاس Stack است ، یعنی ایجاد یک شی از این کلاس.

Stack<E> stack = new Stack<E>();

جایی که E نوع شی است.

روش های پشته جاوا

این کلاس فقط یک سازنده پیش فرض و تمام متدهای کلاس Vector دارد . به علاوه، Stack 5 روش خاص خود را دارد:

• متد خالی () boolean چک می کند که آیا پشته خالی است یا نه. اگر پشته خالی باشد true ، در غیر این صورت false برمی گرداند .

• شیء peek() متد عنصری را که در بالای پشته قرار دارد برمی گرداند.

• شیء pop() متد عنصری را که در بالای پشته قرار دارد برمی گرداند و آن را حذف می کند.

• Object push (Object element) روش عنصر مشخص شده را به بالای پشته اضافه می کند.

• int search (عنصر Object) متد پشته را برای عنصر مشخص شده جستجو می کند. اگر عنصر مورد نیاز پیدا شود، "فاصله" آن از بالا (شماره سریال) برگردانده می شود. اگر عنصر پیدا نشد، -1 برگردانده می شود.

نمونه کد پشته

بیایید یک مثال برنامه بسازیم که مانند تصویر گیف بالا کار کند. ما سه "توپ"، نارنجی، بنفش و سبز را روی پشته قرار می دهیم. بیایید پشته را برای خالی بودن بررسی کنیم. سپس، تا زمانی که پشته خالی شود، توپ ها را از پشته استخراج می کنیم.

import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.push("Orange Ball");
           myStack.push("Violet Ball");
           myStack.push("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }

این هم خروجی این برنامه: از آنجایی که Stack از کلاس Vector به ارث رسیده است و رابط List را پیاده سازی می کند، Stack علاوه بر عملیات فشار و پاپ کلاسیک برای این ساختار داده برای افزودن و استخراج عناصر، دارای استانداردی برای عملیات add() و remove() ساختار لیست نیز می باشد. در مثال ما، افزودن عناصر را می توان به همان روش با استفاده از متد add() پیاده سازی کرد . با این حال شما می توانید با استفاده از remove() فقط با یک عنصر مشخص شده استخراج کنید، که برای ساختار داده پشته معنی ندارد.

import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.add("Orange Ball");
           myStack.add("Violet Ball");
           myStack.add("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }

نتیجه کار برنامه البته دقیقاً همین خواهد بود.

در مورد پیاده سازی Stack خودتان چطور؟

شما می توانید ساختار داده پشته خود را در جاوا با استفاده از آرایه ها یا کلاس های لیست پیوندی ایجاد کنید. در حالت اول، یک آرایه پیوسته از سلول ها برای ذخیره مقادیر در حافظه اختصاص داده می شود که در صورت نیاز از آنها استفاده می شود. در مرحله دوم، برای هر عنصر پشته، یک بلوک حافظه مرتب می شود که برای ذخیره مقدار و ارجاع به عناصر قبلی و بعدی پشته کافی است. پیاده‌سازی مبتنی بر آرایه ساده‌تر، کارآمدتر و کارآمدتر از حافظه است، اما نیاز به دانش قبلی از محدودیت اندازه پشته دارد و می‌تواند منجر به یافتن اشکالات سخت شود. پیاده سازی مبتنی بر لیست قوی تر اما کارآمدتر است. بیایید یک پیاده سازی ساده مبتنی بر آرایه از پشته ایجاد کنیم. شامل توابع خواهد بود.

• فشار - روشی که افزودن یک عنصر (در موقعیت بالا) را تضمین می کند.

• pop - روشی که حذف یک عنصر (از موقعیت بالا) را فراهم می کند.

• readTop - روشی که مقدار عنصری را که در موقعیت بالا قرار دارد برمی گرداند

• sEmpty - روشی که پشته را برای خالی بودن بررسی می کند

• isFull - روشی که بررسی می کند آیا آرایه ما که پشته را در آن ذخیره می کنیم پر نیست یا خیر

import java.util.Arrays;

public class MyStack {

   private int maxSize;
   private String[] stackArray;
   private int top;

   public MyStack(int size) {
       this.maxSize = size;
       stackArray = new String[maxSize];
       top = -1;
   }

   public String push (String element) {
       return stackArray[++top] = element;

   }

   public String pop (String element) {

       if (isEmpty())
       {
           System.out.println("Underflow\nProgram Terminated");
           System.exit(-1);
       }

       System.out.println("Removing " + readTop());

       return stackArray[top--];

   }

   public String readTop() {
       return stackArray[top];

   }

   public boolean isEmpty() {
       return (top ==  -1);
   }

   public boolean isFull() {
       return (top == maxSize - 1);
   }

   public void printStack(){
       System.out.println(Arrays.toString(stackArray));
   }
}

حالا بیایید یک مثال را با سه توپ بر اساس پشته خود پیاده سازی کنیم:

public class myStackTest {
   public static void main(String[] args) {
       MyStack  myStack = new MyStack(3);
       System.out.println("Is my stack empty? " + myStack.isEmpty());

       myStack.push("Orange Ball");
       myStack.push("Violet Ball");
       myStack.push("Green Ball");

      myStack.printStack();

       System.out.println("Is my stack empty? " + myStack.isEmpty());
       while (!myStack.isEmpty()) {
           myStack.pop(myStack.readTop());
           System.out.println("Is my stack empty? " + myStack.isEmpty());
       }
   }

}

خروجی اینجاست: اگر به دقت نگاه کنید، متغیر top در واقع حاوی شاخص آخرین عنصر است و ارجاع به شی در آرایه باقی می ماند. بنابراین این پیاده سازی نیاز به بهبود دارد. به ساده ترین راه برای انجام این کار فکر کنید.

آیا باید از جاوا استک استفاده کنیم؟

در واقع، پشته جاوا ، مانند والد Vector خود ، یک کلاس قدیمی است. در عوض، معمولاً از کلاس ArrayList استفاده می شود. در حالی که Vector همگام است ، ArrayList همگام نیست . این بدان معناست که با Vector تنها یک رشته در یک زمان می تواند به کد دسترسی داشته باشد، در حالی که ArrayList می تواند با چندین رشته کار کند. همچنین، ArrayList کارآمدتر و سریعتر است. بنابراین به احتمال زیاد این کلاس را فقط در کدهای قدیمی خواهید دید. اما ساختار داده Stack اغلب در برنامه نویسی استفاده می شود.