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.
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:
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:
GO TO FULL VERSION