Hvad er stakdatastruktur
Først og fremmest, lad os tage et hurtigt kig på, hvad en stakdatastruktur er. Det er en lineær datastruktur, der er baseret på Last-in-First-out (LIFO) princippet. Det er en slags anti-kø. Forestil dig et sæt kort eller en stak bøger i en æske. Den bog, du lægger i stakken først, er nederst, og den første vi tager ud af kassen er den bog, der var øverst - altså den, der kom sidst i kassen. Her er et gif-billede for at demonstrere dette princip.
Hvad er stakdatastrukturen til?
En af de vigtigste anvendelser af stakken er at organisere subrutineopkald. Opkaldspunktet på stakken gemmer returadressen fra subrutinen, efter at den er afsluttet (og muligvis parametrene passeret). Med hvert indlejret (inklusive rekursivt) kald af subrutiner tilføjes nye returadresser til stakken. Ved hver returoperation fra subrutinen (return) fjernes returadressen fra stakken, og kontrollen overføres til den. Denne applikation er så vigtig for programmering, at returstakken i de fleste processorer er implementeret i hardware i instruktionssættet. I andre tilfælde skal stakken dog modelleres efter mere generelle datastrukturer.Java Stack Class of Collection Framework
I Java Stack Class er en klasse fra Collection frameworket, der implementerer List interface og udvider Vector klasse. Det implementerer også grænseflader Collection, Iterable, Cloneable, Serializable. Som du sikkert allerede har gættet repræsenterer denne klasse LIFO-stakken af objekter. Her er opfordringen til konstruktøren af Stack -klassen, det vil sige oprettelsen af et objekt af denne klasse.
Stack<E> stack = new Stack<E>();
Hvor E er typen af objekt.
Java Stack metoder
Denne klasse har kun én standardkonstruktør og alle Vector- klassens metoder. Plus, Stack har sine egne 5 metoder:-
boolean empty() metoden kontrollerer om stakken er tom eller ej. Returnerer sand , hvis stakken er tom, falsk , hvis ikke.
-
Object peek() metoden returnerer det element, der er øverst i stakken.
-
Object pop() metoden returnerer det element, der er øverst i stakken, og fjerner det.
-
Object push(Object element) metoden tilføjer det angivne element til toppen af stakken.
-
int search(Object element) metoden søger i stakken efter det angivne element. Hvis det nødvendige element findes, returneres dets "afstand" fra toppen (serienummer). Hvis elementet ikke findes, returneres -1.
Eksempel på stak kode
Lad os lave et programeksempel, der virker, såsom gif-billedet ovenfor. Vi lægger tre "bolde", orange, lilla og grønne, på stakken. Lad os tjekke stakken for tomhed. Derefter trækker vi bolde ud af stakken, indtil stakken er 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());
}
}
}
Her er output fra dette 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());
}
}
}
Resultatet af programarbejdet bliver naturligvis helt det samme.
Hvad med din egen Stack-implementering?
Du kan oprette din egen stakdatastruktur i Java ved hjælp af arrays eller sammenkædede listeklasser. I det første tilfælde er et kontinuerligt array af celler allokeret til at gemme værdier i hukommelsen, som bruges efter behov. I den anden, for hvert element i stakken, er der bestilt en hukommelsesblok, tilstrækkelig til at lagre værdien og referencer til de forrige og næste elementer i stakken. Den array-baserede implementering er enklere, mere effektiv og mere hukommelseseffektiv, men den kræver en forudgående viden om stakstørrelsesgrænsen og kan føre til svære at finde fejl. Den listebaserede implementering er mere robust, men mindre effektiv. Lad os lave en simpel array-baseret implementering af stakken. Det vil indeholde funktioner.-
push — en metode, der sikrer tilføjelsen af et element (i den øverste position)
-
pop — en metode, der vil sørge for fjernelse af et element (fra den øverste position)
-
readTop — en metode, der returnerer værdien af det element, der er i topposition
-
sEmpty — en metode, der kontrollerer stakken for tomhed
-
isFull — en metode, der vil kontrollere, om vores array, som vi gemmer stakken i, ikke er fuld
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));
}
}
Lad os nu implementere et eksempel med tre bolde baseret på vores stak:
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());
}
}
}
Output er her:
GO TO FULL VERSION