Java stack

Stack i Java betyder vanligtvis klassen från Collection Framework som implementerar List-gränssnittet. Det fungerar enligt principen om Stack-datastrukturen, som används för att organisera en av minnestyperna. Det kan också vara en del av minnet att behålla data. I den här artikeln kommer vi först och främst att uppmärksamma Stack- klassen , överväga dess metoder och ge exempel. Men vi kommer också att prata om en sådan datastruktur som Stack och vad den används till.

Vad är Stack Data Structure

Först och främst, låt oss ta en snabb titt på vad en stackdatastruktur är. Det är en linjär datastruktur som är baserad på Last-in-First-out (LIFO)-principen. Det är typ av anti-kö. Föreställ dig en kortlek eller en hög med böcker i en låda. Boken som du lägger i högen först ligger längst ner, och den första vi tar ut ur lådan är boken som låg överst - alltså den som kom in i lådan sist. Här är en gif-bild för att demonstrera denna princip. Vad händer här? Vi har en kolv där bara en boll kan träffas åt gången. Den första i kolven är en orange boll, sedan lila och till sist grön (jag ber om ursäkt till dem som känner till de mer exakta namnen på dessa färger). Men för att ta ut en orange boll från vår kolvstack måste vi först utvinna den boll som kom dit sist (den gröna), sedan den som var den näst sista (men vid tidpunkten för utvinningen är den den sista ett). Stackdatastrukturen i Java eller någon annanstans i programmering har de två viktigaste operationerna, push och pop . Tryckoperationen sätter in ett element i stapeln och popoperationen tar bort ett element från toppen av stapeln.

Vad är stackdatastrukturen till för?

En av de viktigaste användningsområdena för stacken är att organisera subrutinsamtal. Anropspunkten på stacken lagrar returadressen från subrutinen efter att den har avslutats (och eventuellt parametrarna som skickats). Med varje kapslat (inklusive rekursivt) anrop av subrutiner läggs nya returadresser till i stacken. Med varje returoperation från subrutinen (retur) tas returadressen bort från stacken och kontrollen överförs till den. Denna applikation är så viktig för programmering att i de flesta processorer är returstacken implementerad i hårdvara i instruktionsuppsättningen. I andra fall måste dock stacken modelleras på mer allmänna datastrukturer.

Java Stack Class of Collection Framework

I Java Stack Class är en klass från samlingsramverket som implementerar List-gränssnittet och utökar Vector-klassen. Det implementerar också gränssnitt Collection, Iterable, Cloneable, Serializable. Som du säkert redan har gissat representerar denna klass LIFO-stacken av objekt. Här är anropet till konstruktören av Stack -klassen, det vill säga skapandet av ett objekt av denna klass.

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

Där E är typen av objekt.

Java stackmetoder

Den här klassen har bara en standardkonstruktor och alla metoder i klassen Vector . Dessutom har Stack sina egna 5 metoder:

• boolean empty() metoden kontrollerar om stacken är tom eller inte. Returnerar sant om stacken är tom, falskt om inte.

• Object peek() metoden returnerar elementet som är överst i stacken.

• Objekt pop() metoden returnerar elementet som är överst i stacken och tar bort det.

• Object push(Object element) metoden lägger till det angivna elementet till toppen av stacken.

• int search(Object element) metoden söker i stacken efter det angivna elementet. Om det nödvändiga elementet hittas returneras dess "avstånd" från toppen (serienummer). Om elementet inte hittas returneras -1.

Exempel på stackkod

Låt oss skapa ett programexempel som fungerar som gif-bilden ovan. Vi lägger tre "bollar", orange, lila och gröna, på traven. Låt oss kontrollera om högen är tom. Sedan tar vi ut bollar från högen tills högen är tom.

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

Här är resultatet av detta program: Eftersom Stack ärvs från Vector Class och implementerar List- gränssnittet, har Stack , förutom de klassiska push- och pop-operationerna för denna datastruktur för att lägga till och extrahera element, även standard för liststruktur add( ) och remove() operationer. I vårt exempel kan lägga till element implementeras på samma sätt med metoden add() . Du kan dock extrahera med remove() endast med ett specificerat element, vilket inte är meningsfullt för stackdatastrukturen.

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

Resultatet av programarbetet blir förstås exakt detsamma.

Hur är det med din egen Stack-implementering?

Du kan skapa din egen stackdatastruktur i Java med hjälp av arrayer eller länkade listklasser. I det första fallet tilldelas en kontinuerlig uppsättning celler för att lagra värden i minnet, som används efter behov. I det andra, för varje element i stacken, ordnas ett minnesblock, tillräckligt för att lagra värdet och referenser till föregående och nästa element i stacken. Den array-baserade implementeringen är enklare, effektivare och mer minneseffektiv, men den kräver förkunskaper om stackstorleksgränsen och kan leda till svåra att hitta buggar. Den listbaserade implementeringen är mer robust men mindre effektiv. Låt oss göra en enkel array-baserad implementering av stacken. Det kommer att innehålla funktioner.

• push — en metod som säkerställer tillägg av ett element (i den översta positionen)

• pop — en metod som tar bort ett element (från den översta positionen)

• readTop — en metod som returnerar värdet på elementet som är i position överst

• sEmpty — en metod som kontrollerar att stacken är tom

• isFull — en metod som kontrollerar om vår array där vi lagrar stacken inte är full

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

Låt oss nu implementera ett exempel med tre bollar baserat på vår stack:

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

}

Utgången är här: Om du tittar noga så innehåller den översta variabeln faktiskt indexet för det sista elementet, och referensen till objektet finns kvar i arrayen. Så den här implementeringen behöver förbättras. Fundera på det enklaste sättet att göra detta.

Ska vi använda Java Stack?

Faktum är att Java Stack , liksom dess Vector- förälder, är en äldre klass. Istället används vanligtvis klassen ArrayList . ArrayList synkroniseras inte medan Vector är synkroniserat. Det betyder att med Vector endast en tråd åt gången kan komma åt koden, medan ArrayList kan arbeta med flera trådar. Dessutom är ArrayList effektivare och snabbare. Så du kommer troligen bara att se den här klassen i äldre kod. Men Stack- datastrukturen används i programmering väldigt ofta.