Java Stack

Stack ב-Java פירושו בדרך כלל המחלקה מ- Collection Framework המיישמת את ממשק ה- List. זה עובד על העיקרון של מבנה הנתונים Stack, המשמש לארגון אחד מסוגי הזיכרון. זה גם יכול להיות החלק של הזיכרון לשמור נתונים, במאמר זה נשים לב קודם כל למחלקה Stack , נשקול את השיטות שלה וניתן דוגמאות. אבל נדבר גם על מבנה נתונים כמו Stack ולמה הוא משמש.

מהו מבנה נתונים מחסנית

קודם כל, בואו נסתכל במהירות מה זה מבנה נתונים מחסנית. זהו מבנה נתונים ליניארי המבוסס על עקרון ה-Last-in-First-out (LIFO). זה סוג של אנטי-תור. דמיינו חפיסת קלפים או ערימת ספרים בקופסה. הספר ששמים ראשון בערימה נמצא בתחתית, והראשון שנוציא מהקופסה הוא הספר שהיה למעלה - כלומר זה שנכנס אחרון לקופסה. הנה תמונת GIF כדי להדגים את העיקרון הזה. מה קורה פה? יש לנו בקבוק שבו רק כדור אחד יכול לפגוע בכל פעם. הראשון בבקבוק הוא כדור כתום, אחר כך סגול, ולבסוף ירוק (אני מתנצל בפני מי שמכיר את השמות המדויקים יותר של הצבעים הללו). אולם כדי לחלץ כדור כתום מחרמת הבקבוקים שלנו, עלינו לחלץ קודם את הכדור שהגיע לשם אחרון (הירוק), ואז את זה שהיה הלפני אחרון (אבל בזמן החילוץ הוא האחרון) אחד). למבנה הנתונים מחסנית ב-Java או במקום אחר בתכנות יש את שתי הפעולות החשובות ביותר, push ו- pop . פעולת הדחיפה מכניסה אלמנט לערימה ופעולת פופ מסירה אלמנט מהחלק העליון של הערימה.

לשם מה מיועד מבנה הנתונים מחסנית?

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

Java Stack Class of Collection Framework

ב-Java Stack Class היא מחלקה ממסגרת Collection המיישמת ממשק List ומרחיבה את מחלקת Vector. זה גם מיישם ממשקים Collection, Iterable, Cloneable, Serializable. כפי שבטח כבר ניחשתם מחלקה זו מייצגת את ערימת האובייקטים LIFO. הנה הקריאה לבנאי של המחלקה Stack , כלומר, יצירת אובייקט של המחלקה הזו.

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

כאשר E הוא סוג האובייקט.

שיטות Java Stack

למחלקה הזו יש רק בנאי ברירת מחדל אחד ואת כל השיטות של מחלקת Vector . בנוסף, ל-Stack יש 5 שיטות משלה:

• boolean empty() השיטה בודקת אם המחסנית ריקה או לא. מחזירה true אם המחסנית ריקה, false אם לא.

• Object peek() השיטה מחזירה את האלמנט שנמצא בראש הערימה.

• Object pop() השיטה מחזירה את האלמנט שנמצא בראש הערימה ומסירה אותו.

• Object push(Object element) השיטה מוסיפה את האלמנט שצוין לראש הערימה.

• int search(Object element) השיטה מחפשת בערימה את האלמנט שצוין. אם הרכיב הנדרש נמצא, ה"מרחק" שלו מלמעלה (מספר סידורי) מוחזר. אם האלמנט לא נמצא, -1 מוחזר.

דוגמה לקוד מחסנית

בואו ניצור דוגמה לתוכנית שעובדת כמו תמונת ה-GIF שלמעלה. נשים שלושה "כדורים", כתום, סגול וירוק, על הערימה. בוא נבדוק אם הערימה ריקה. לאחר מכן, נחלץ כדורים מהערימה עד שהערימה תתרוקן.

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 ומיישמת את ממשק ה- 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 משלך?

אתה יכול ליצור מבנה נתונים מחסנית משלך ב-Java באמצעות מערכים או מחלקות רשימה מקושרת. במקרה הראשון, מערך רציף של תאים מוקצה לאחסון ערכים בזיכרון, המשמשים לפי הצורך. בשנייה, עבור כל אלמנט של המחסנית, מזמין בלוק זיכרון, המספיק לאחסון הערך והפניות לרכיבים הקודמים והבאים של המחסנית. המימוש המבוסס על מערך הוא פשוט יותר, יעיל יותר וחסכוני יותר בזיכרון, אך הוא דורש ידע מוקדם על מגבלת גודל המחסנית ויכול להוביל לבאגים שקשה למצוא אותם. היישום מבוסס הרשימה חזק יותר אך פחות יעיל. בואו נעשה יישום פשוט מבוסס מערך של המחסנית. זה יכלול פונקציות.

• push - שיטה שתבטיח הוספת אלמנט (במיקום העליון)

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

}

הפלט נמצא כאן: אם מסתכלים היטב, המשתנה העליון מכיל למעשה את האינדקס של האלמנט האחרון, וההתייחסות לאובייקט נשארת במערך. אז היישום הזה זקוק לשיפור מסוים. תחשוב על הדרך הקלה ביותר לעשות זאת.

האם עלינו להשתמש ב-Java Stack?

למעשה, Java Stack , כמו האב הוקטור שלו , הוא מחלקה מדור קודם. במקום זאת, בדרך כלל נעשה שימוש במחלקה ArrayList . ArrayList אינו מסונכרן בעוד וקטור מסונכרן. כלומר עם Vector רק שרשור אחד בכל פעם יכול לגשת לקוד, בעוד ArrayList יכול לעבוד עם שרשורים מרובים. כמו כן, ArrayList יעיל ומהיר יותר. אז סביר להניח שתראה את המחלקה הזו רק בקוד מדור קודם. אבל מבנה הנתונים של Stack משמש בתכנות לעתים קרובות מאוד.