Stiva Java

Stack în Java înseamnă de obicei clasa din Collection Framework care implementează interfața List. Funcționează pe principiul structurii de date Stack, care este folosită pentru a organiza unul dintre tipurile de memorie. De asemenea, ar putea fi partea memoriei care păstrează datele. În acest articol vom acorda atenție în primul rând clasei Stack , vom lua în considerare metodele acesteia și vom da exemple. Dar vom vorbi și despre o astfel de structură de date precum Stack și pentru ce este folosită.

Ce este Stack Data Structure

În primul rând, să aruncăm o privire rapidă la ce este o structură de date stivă. Este o structură de date liniară care se bazează pe principiul Last-in-First-out (LIFO). Este un fel de anti-codă. Imaginați-vă un pachet de cărți sau un teanc de cărți într-o cutie. Cartea pe care ai pus-o mai întâi în teanc este în partea de jos, iar prima pe care o vom scoate din cutie este cartea care a fost sus - adică cea care a intrat ultima în cutie. Iată o imagine gif pentru a demonstra acest principiu. Ce se petrece aici? Avem un balon în care o singură minge poate lovi o dată. Prima din balon este o minge portocalie, apoi mov și în final verde (îmi cer scuze celor care cunosc denumirile mai exacte ale acestor culori). Totuși, pentru a extrage o minge portocalie din stiva noastră de baloane, trebuie să extragem mai întâi bila care a ajuns ultima acolo (cea verde), apoi cea care a fost penultima (dar în momentul extracției este ultima). unu). Structura de date stiva în Java sau în altă parte în programare are cele mai importante două operații, push și pop . Operația de împingere inserează un element în stivă, iar operația de pop scoate un element din partea de sus a stivei.

Pentru ce este structura de date Stack?

Una dintre cele mai importante utilizări ale stivei este organizarea apelurilor subrutine. Punctul de apel de pe stivă stochează adresa de retur din subrutină după ce aceasta se termină (și, eventual, parametrii trecuți). Cu fiecare apel imbricat (inclusiv recursiv) de subrutine, noi adrese de retur sunt adăugate la stivă. Cu fiecare operațiune de returnare din subrutină (retur), adresa de retur este eliminată din stivă și controlul este transferat acesteia. Această aplicație este atât de importantă pentru programare încât la majoritatea procesoarelor stiva de returnare este implementată în hardware în setul de instrucțiuni. Cu toate acestea, în alte cazuri, stiva trebuie să fie modelată pe structuri de date mai generale.

Clasa Java Stack de cadru de colectare

În Java Stack Class este o clasă din cadrul Collection care implementează interfața List și extinde clasa Vector. De asemenea, implementează interfețele Collection, Iterable, Cloneable, Serializable. După cum probabil ați ghicit deja, această clasă reprezintă teancul LIFO de obiecte. Iată apelul către constructorul clasei Stack , adică crearea unui obiect din această clasă.

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

Unde E este tipul de obiect.

Metode Java Stack

Această clasă are un singur constructor implicit și toate metodele clasei Vector . În plus, Stack are propriile sale 5 metode:

• boolean empty() metoda verifică dacă stiva este goală sau nu. Returnează true dacă stiva este goală, false dacă nu.

• Object peek() metoda returnează elementul care se află în partea de sus a stivei.

• Object pop() metoda returnează elementul care se află în partea de sus a stivei și îl elimină.

• Object push(Object element) metoda adaugă elementul specificat în partea de sus a stivei.

• int search(Object element) metoda caută în stiva elementul specificat. Dacă se găsește elementul necesar, se returnează „distanța” acestuia față de partea de sus (numărul de serie). Dacă elementul nu este găsit, este returnat -1.

Exemplu de cod de stivă

Să creăm un exemplu de program care funcționează, cum ar fi imaginea gif de mai sus. Vom pune trei „bile”, portocaliu, violet și verde, pe stivă. Să verificăm stiva dacă nu este gol. Apoi, vom extrage bile din stivă până când stiva este goală.

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

Iată rezultatul acestui program: Deoarece Stack este moștenit de la Vector Class și implementează interfața List , Stack , pe lângă operațiile clasice push și pop pentru această structură de date pentru adăugarea și extragerea elementelor, are și standard pentru operațiunile add() și remove() din structura listă. În exemplul nostru, adăugarea de elemente poate fi implementată în același mod folosind metoda add() . Cu toate acestea, puteți extrage folosind remove() numai cu un element specificat, ceea ce nu are sens pentru structura de date a stivei.

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

Rezultatul programului de lucru, desigur, va fi exact același.

Cum rămâne cu propria ta implementare Stack?

Vă puteți crea propria structură de date a stivei în Java utilizând matrice sau clase de liste legate. În primul caz, o matrice continuă de celule este alocată pentru a stoca valori în memorie, care sunt utilizate după cum este necesar. În al doilea, pentru fiecare element al stivei, este ordonat un bloc de memorie, suficient pentru a stoca valoarea și referințele la elementele anterioare și următoare ale stivei. Implementarea bazată pe matrice este mai simplă, mai eficientă și mai eficientă în memorie, dar necesită o cunoaștere prealabilă a limitei de dimensiune a stivei și poate duce la erori greu de găsit. Implementarea bazată pe liste este mai robustă, dar mai puțin eficientă. Să facem o implementare simplă bazată pe matrice a stivei. Acesta va include funcții.

• push — o metodă care va asigura adăugarea unui element (în poziția de sus)

• pop — o metodă care va asigura eliminarea unui element (din poziția de sus)

• readTop — o metodă care va returna valoarea elementului care se află în poziția de sus

• sEmpty — o metodă care va verifica stiva pentru golire

• isFull — o metodă care va verifica dacă matricea noastră în care stocăm stiva nu este plină

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

Acum să implementăm un exemplu cu trei bile bazate pe stiva noastră:

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

}

Ieșirea este aici: Dacă te uiți cu atenție, variabila de sus conține de fapt indexul ultimului element, iar referința la obiect rămâne în matrice. Deci această implementare are nevoie de unele îmbunătățiri. Gândiți-vă la cel mai simplu mod de a face acest lucru.

Ar trebui să folosim Java Stack?

De fapt, Java Stack , ca și părintele său Vector , este o clasă moștenită. În schimb, se folosește de obicei clasa ArrayList . ArrayList nu este sincronizat în timp ce Vector este sincronizat. Aceasta înseamnă că, cu Vector, doar un fir la un moment dat poate accesa codul, în timp ce ArrayList poate funcționa cu mai multe fire. De asemenea, ArrayList este mai eficient și mai rapid. Deci, cel mai probabil, veți vedea această clasă numai în codul moștenit. Dar structura de date Stack este folosită foarte des în programare.