Java Stack

A verem a Java nyelvben általában azt az osztályt jelenti a Collection Frameworkből, amely megvalósítja a List felületet. A Stack adatstruktúra elvén működik, amely az egyik memóriatípus megszervezésére szolgál. Ez lehet a memória része az adatok tárolására is. Ebben a cikkben mindenekelőtt a Stack osztályra fogunk figyelni, megvizsgáljuk annak módszereit és példákat adunk. De beszélni fogunk egy olyan adatszerkezetről is, mint a Stack , és arról, hogy mire használják.

Mi az a verem adatstruktúra

Először is nézzük meg gyorsan, mi is az a verem adatstruktúra. Ez egy lineáris adatstruktúra, amely a LIFO (Last-in-First-out) elven alapul. Ez egyfajta sorellenes. Képzelj el egy pakli kártyát vagy egy köteg könyvet egy dobozban. Az a könyv, amelyet először tesz a kötegbe, az alul van, és az első, amelyet kivesszük a dobozból, az a könyv, amelyik a tetején volt, vagyis amelyik utoljára került a dobozba. Itt van egy gif kép ennek az elvnek a bemutatására. Mi folyik itt? Van egy lombikunk, amelyben egyszerre csak egy labda üthet el. A lombikban az első egy narancssárga golyó, majd lila, végül zöld (elnézést azoktól, akik ismerik ezeknek a színeknek a pontosabb nevét). Ahhoz azonban, hogy narancssárga golyót kinyerhessünk a lombikrakásunkból, először azt a golyót kell kihúznunk, amelyik utoljára került oda (a zöldet), majd azt, amelyik az utolsó előtti volt (de a kihúzáskor ez az utolsó). egy). A Java vagy más programozási területek verem-adatstruktúrájában a két legfontosabb művelet van, a push és a pop . A push művelet beszúr egy elemet a verembe, a pop művelet pedig eltávolít egy elemet a verem tetejéről.

Mire való a Stack adatstruktúra?

A verem egyik legfontosabb felhasználási módja a szubrutinhívások szervezése. A verem hívási pontja eltárolja a szubrutin visszatérési címét annak befejezése után (és esetleg az átadott paramétereket). Az alprogramok minden egyes beágyazott (beleértve a rekurzív) hívását új visszatérési címek adják hozzá a veremhez. Az alprogram minden visszatérési műveletével (return) a visszatérési cím eltávolításra kerül a veremből, és a vezérlés átkerül rá. Ez az alkalmazás annyira fontos a programozáshoz, hogy a legtöbb processzorban a visszatérési verem az utasításkészletben található hardverben. Más esetekben azonban a veremet általánosabb adatstruktúrákra kell modellezni.

Java Stack Class of Collection Framework

A Java-ban a Stack Class egy osztály a Collection keretrendszerből, amely megvalósítja a List interfészt és kiterjeszti a Vector osztályt. Ezenkívül megvalósítja a Gyűjtemény, Iterálható, Klónozható, Sorosozható felületeket. Amint azt valószínűleg már kitalálta, ez az osztály a LIFO objektumok halmazát képviseli. Itt van a Stack osztály konstruktorának hívása , vagyis az osztály objektumának létrehozása.

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

Ahol E az objektum típusa.

Java veremmódszerek

Ennek az osztálynak csak egy alapértelmezett konstruktora és a Vector osztály összes metódusa van . Ráadásul a Stack saját 5 módszerrel rendelkezik:

• boolean empty() a metódus ellenőrzi, hogy a verem üres-e vagy sem. Igaz, ha a verem üres, hamis értéket ad vissza , ha nem.

• Object peek() a metódus a verem tetején lévő elemet adja vissza.

• Object pop() a metódus visszaadja a verem tetején lévő elemet, és eltávolítja azt.

• Object push (Object element) a metódus hozzáadja a megadott elemet a verem tetejéhez.

• int search(Object element) a metódus a veremben keresi a megadott elemet. Ha a keresett elem megtalálható, akkor a „távolsága” felülről (sorozatszám) kerül visszaadásra. Ha az elem nem található, -1-et ad vissza.

Példa veremkódra

Hozzunk létre egy olyan programpéldát, amely úgy működik, mint a fenti gif kép. Három „golyót”, narancsot, lilát és zöldet teszünk a veremre. Ellenőrizzük, hogy nincs-e üres a verem. Ezután kihúzzuk a golyókat a veremből, amíg a verem ki nem ürül.

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

Íme a program kimenete: Mivel a Stack a Vector Class- tól öröklődik , és a Lista felületet valósítja meg, a Stack az ehhez az adatszerkezethez az elemek hozzáadására és kibontására szolgáló klasszikus push és pop műveletek mellett szabványos a listastruktúra add() és remove() műveletekhez is. Példánkban az elemek hozzáadása az add() metódussal ugyanúgy megvalósítható . A remove() paranccsal azonban csak egy megadott elem mellett lehet kicsomagolni , aminek nincs értelme a verem adatszerkezetében.

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

A programmunka eredménye természetesen pontosan ugyanaz lesz.

Mi a helyzet a saját Stack implementációjával?

Saját verem-adatstruktúrát hozhat létre Java-ban tömbök vagy linkelt listaosztályok használatával. Az első esetben a cellák folyamatos tömbje van hozzárendelve az értékek memóriában való tárolására, amelyeket szükség szerint használnak fel. A másodikban a verem minden eleméhez egy memóriablokkot rendelünk, amely elegendő az érték és a verem előző és következő elemeire való hivatkozások tárolására. A tömb alapú megvalósítás egyszerűbb, hatékonyabb és memóriahatékonyabb, de a verem méretkorlátjának előzetes ismeretét igényli, és nehezen fellelhető hibákhoz vezethet. A listaalapú megvalósítás robusztusabb, de kevésbé hatékony. Készítsük el a verem egyszerű tömb alapú megvalósítását. Funkciókat fog tartalmazni.

• push - egy módszer, amely biztosítja egy elem hozzáadását (a legfelső pozícióban)

• pop - egy módszer, amely biztosítja az elem eltávolítását (a felső pozícióból)

• readTop – egy metódus, amely visszaadja a felső pozícióban lévő elem értékét

• sEmpty – egy módszer, amely ellenőrzi a verem ürességét

• isFull — egy olyan módszer, amely ellenőrzi, hogy a tömbünk, amelyben a veremet tároljuk, nincs-e tele

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

Most hajtsunk végre egy példát három labdával a veremünk alapján:

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

}

A kimenet itt található: Ha alaposan megnézzük, a felső változó valójában az utolsó elem indexét tartalmazza, és az objektumra való hivatkozás a tömbben marad. Tehát ez a megvalósítás némi javításra szorul. Gondolja át ennek legegyszerűbb módját.

Használjunk Java Stacket?

Valójában a Java Stack , akárcsak a Vector szülője, egy örökölt osztály. Ehelyett általában az ArrayList osztályt használják. Az ArrayList nincs szinkronizálva, miközben a Vector szinkronizálva van. Ez azt jelenti, hogy a Vector segítségével egyszerre csak egy szál férhet hozzá a kódhoz, míg az ArrayList több szálal is működhet. Ezenkívül az ArrayList hatékonyabb és gyorsabb. Így ezt az osztályt valószínűleg csak a régi kódban fogja látni. De a Stack adatszerkezetet nagyon gyakran használják a programozásban.