جافا ستاك

المكدس في Java يعني عادةً الفئة من Collection Framework التي تنفذ واجهة القائمة. وهو يعمل على مبدأ بنية البيانات Stack، والتي تستخدم لتنظيم أحد أنواع الذاكرة. كما يمكن أن يكون جزءًا من الذاكرة لحفظ البيانات، في هذه المقالة سنهتم أولاً بفئة Stack ، وننظر في طرقها ونعطي أمثلة. لكننا سنتحدث أيضًا عن بنية البيانات مثل Stack وما يتم استخدامه من أجله.

ما هو هيكل البيانات المكدس

أولاً، دعونا نلقي نظرة سريعة على ماهية بنية البيانات المكدسة. إنها بنية بيانات خطية تعتمد على مبدأ Last-in-First-out (LIFO). إنه نوع من مكافحة الطابور. تخيل مجموعة من البطاقات أو مجموعة من الكتب في صندوق. الكتاب الذي وضعته في المكدس أولاً موجود في الأسفل، وأول كتاب سنخرجه من الصندوق هو الكتاب الذي كان في الأعلى - أي الكتاب الذي دخل الصندوق أخيرًا. هنا صورة GIF لتوضيح هذا المبدأ. ما الذي يحدث هنا؟ لدينا دورق يمكن أن تضرب فيه كرة واحدة فقط في كل مرة. أول ما في الدورق كرة برتقالية، ثم أرجوانية، وأخيرا خضراء (أعتذر لمن يعرف الأسماء الدقيقة لهذه الألوان). ومع ذلك، من أجل استخراج كرة برتقالية من مجموعة القارورة، نحتاج أولاً إلى استخراج الكرة التي وصلت إلى هناك أخيرًا (الكرة الخضراء)، ثم الكرة التي كانت قبل الأخيرة (ولكن في وقت الاستخراج كانت الأخيرة واحد). تحتوي بنية بيانات المكدس في Java أو في أي مكان آخر في البرمجة على أهم عمليتين، هما Push و Pop . تقوم عملية الدفع بإدراج عنصر في المكدس وتقوم عملية البوب ​​بإزالة عنصر من أعلى المكدس.

ما هو الغرض من بنية بيانات Stack؟

أحد أهم استخدامات المكدس هو تنظيم المكالمات الروتينية الفرعية. تقوم نقطة الاتصال الموجودة على المكدس بتخزين عنوان المرسل من الروتين الفرعي بعد انتهائه (وربما المعلمات التي تم تمريرها). مع كل استدعاء متداخل (بما في ذلك التكراري) للروتينات الفرعية، تتم إضافة عناوين إرجاع جديدة إلى المكدس. مع كل عملية إرجاع من الروتين الفرعي (الإرجاع)، تتم إزالة عنوان الإرجاع من المكدس ويتم نقل التحكم إليه. يعد هذا التطبيق مهمًا جدًا للبرمجة، حيث يتم تنفيذ مكدس الإرجاع في معظم المعالجات في الأجهزة الموجودة في مجموعة التعليمات. ومع ذلك، في حالات أخرى، يجب تصميم المكدس وفقًا لهياكل بيانات أكثر عمومية.

Java Stack Class of Collection Framework

في Java Stack Class هي فئة من إطار المجموعة التي تنفذ واجهة القائمة وتوسع فئة Vector. كما أنها تنفذ واجهات Collection، Iterable، Cloneable، Serializable. كما قد تكون خمنت بالفعل، فإن هذه الفئة تمثل مكدس الكائنات LIFO. هنا يتم استدعاء مُنشئ فئة Stack ، أي إنشاء كائن من هذه الفئة.

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

حيث E هو نوع الكائن

طرق جافا المكدس

تحتوي هذه الفئة على مُنشئ افتراضي واحد فقط وجميع أساليب فئة Vector . بالإضافة إلى ذلك، لدى Stack 5 طرق خاصة به:

• منطقية فارغة () تتحقق الطريقة مما إذا كانت المكدس فارغة أم لا. يُرجع صحيحًا إذا كان المكدس فارغًا، ويُرجع خطأ إذا لم يكن كذلك.

• نظرة خاطفة على الكائن () تقوم الطريقة بإرجاع العنصر الموجود في الجزء العلوي من المكدس.

• Object pop() تقوم الطريقة بإرجاع العنصر الموجود في الجزء العلوي من المكدس وإزالته.

• دفع الكائن (عنصر الكائن) تضيف الطريقة العنصر المحدد إلى أعلى المكدس.

• int search(عنصر الكائن) تبحث الطريقة في المكدس عن العنصر المحدد. إذا تم العثور على العنصر المطلوب، يتم إرجاع "المسافة" الخاصة به من الأعلى (الرقم التسلسلي). إذا لم يتم العثور على العنصر، فسيتم إرجاع -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 Class وينفذ واجهة القائمة ، فإن Stack ، بالإضافة إلى عمليات الدفع والبوب ​​الكلاسيكية لبنية البيانات هذه لإضافة العناصر واستخراجها، لديه أيضًا معيار لعمليات إضافة بنية القائمة () وإزالة () . في مثالنا، يمكن تنفيذ إضافة العناصر بنفس الطريقة باستخدام طريقة add() . ومع ذلك، يمكنك الاستخراج باستخدام الإزالة () فقط باستخدام عنصر محدد، وهو ما لا معنى له بالنسبة لبنية بيانات المكدس.

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 الخاص بك؟

يمكنك إنشاء بنية بيانات المكدس الخاصة بك في Java باستخدام المصفوفات أو فئات القائمة المرتبطة. في الحالة الأولى، يتم تخصيص مجموعة مستمرة من الخلايا لتخزين القيم في الذاكرة، والتي يتم استخدامها حسب الحاجة. في الثانية، لكل عنصر من عناصر المكدس، يتم ترتيب كتلة من الذاكرة، كافية لتخزين القيمة والمراجع إلى العناصر السابقة والتالية من المكدس. يعد التنفيذ القائم على المصفوفة أبسط وأكثر كفاءة وأكثر كفاءة في استخدام الذاكرة، ولكنه يتطلب معرفة مسبقة بحد حجم المكدس ويمكن أن يؤدي إلى أخطاء يصعب العثور عليها. يعد التنفيذ القائم على القائمة أكثر قوة ولكنه أقل كفاءة. لنقم بتنفيذ تنفيذ بسيط للمكدس يعتمد على المصفوفة. وسوف تشمل وظائف.

• الدفع - طريقة تضمن إضافة عنصر (في الموضع العلوي)

• البوب ​​- طريقة توفر إزالة عنصر (من الموضع العلوي)

• 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());
       }
   }

}

الإخراج هنا: إذا نظرت عن كثب، فإن المتغير العلوي يحتوي بالفعل على فهرس العنصر الأخير، ويظل المرجع إلى الكائن في المصفوفة. لذلك يحتاج هذا التنفيذ إلى بعض التحسين. فكر في أسهل طريقة للقيام بذلك.

هل يجب أن نستخدم Java Stack؟

في الواقع، يعد Java Stack ، مثل أصله المتجه ، فئة قديمة. بدلاً من ذلك، عادةً ما يتم استخدام فئة ArrayList . لا تتم مزامنة ArrayList أثناء مزامنة Vector . وهذا يعني أنه باستخدام Vector، يمكن لخيط واحد فقط في كل مرة الوصول إلى الكود، بينما يمكن لـ ArrayList العمل مع سلاسل رسائل متعددة. كما أن ArrayList أكثر كفاءة وأسرع. لذلك من المرجح أن ترى هذه الفئة فقط في الكود القديم. ولكن يتم استخدام بنية بيانات Stack في البرمجة كثيرًا.