Preskoči na glavni sadržaj

Stek stek stek stek stek, Stack niko neće!

Chenmo Wang ErJava jezgroOkvir kolekcija (kontejneri)1319 reči4 minuta

Iskreno, klasa Stack se u Java aplikacijama retko koristi, ali je struktura podataka steka izuzetno važna u celokupnom računarskom sistemu. Zato ćemo je ipak obraditi u okviru okvira kolekcija.

Stek (stack), na nekim mestima ga vole zvati "stogom/halom", što meni se ne sviđa — lako se pomeša sa heap-om (gomilom), posebno za početnike, što je prava noćna mora.

Struktura podataka steka

Stek je vrlo korisna struktura podataka; on je kao gomila tanjira — prvi ide na dno, drugi preko prvog, treći preko drugog, a poslednji na sam vrh.

Sa tom gomilom tanjira možemo raditi dve stvari:

  • staviti novi tanjir na vrh
  • skinuti tanjir s vrha

Te dve stvari su lako izvodljive, ali izvući tanjir iz sredine ili s dna je veoma teško. Ako želimo da dođemo do donjeg tanjira, moramo skinuti sve tanjire iznad njega. Takvu operaciju nazivamo "poslednji ušao, prvi izašao", odnosno "Last In First Out" (skraćeno LIFO) — onaj koji je ušao poslednji, izlazi prvi.

Za strukturu podataka steka postoje dve uobičajene akcije:

  • push, na srpskom se prevodi na razne načine, meni se lično više sviđa "potisnuti/pogurati", vrlo slikovito. Kada želimo da stavimo element na vrh steka, ta akcija se zove push.
  • pop, isto tako, meni se lično više sviđa "iskočiti", što nosi snažan efekat animacije, zar ne? Kada želimo da uklonimo element iz steka, ta akcija se zove pop.

Za gornju sliku, element 3 je stavljen poslednji, a prvi je uklonjen — prati princip LIFO.

Pošto smo razumeli osnovne operacije steka, moramo dublje razmisliti o tome kako stek radi. Drugim rečima, da bi ova struktura podataka radila na način steka, šta joj je potrebno?

  1. Stek mora imati pokazivač koji ćemo zvati TOP, a koji pokazuje na element na samom vrhu steka.

  2. Kada inicijalizujemo stek, postavljamo vrednost TOP na -1, tako da pomoću TOP == -1 možemo proveriti da li je stek prazan.

  3. Kada želimo da potisnemo element u stek, povećavamo vrednost TOP za 1 i novi potisnuti element usmeravamo na TOP.

  4. Kada želimo da izbacimo element iz steka, smanjujemo vrednost TOP za 1 i element koji ostaje na vrhu usmeravamo na TOP.

  5. Kada potisnemo element, potrebno je proveriti da li je stek već pun. Drugim rečima, potreban je metod isFull() za tu proveru.

  6. Kada želimo da izbacimo element, potrebno je proveriti da li je stek već prazan. Drugim rečima, potreban je metod isEmpty() za tu proveru.

Kada je stek prazan, TOP je jednako -1; kada se element 1 potisne u stek, stack[0] je 1, a TOP se povećava za 1 i postaje 0; kada se element 2 potisne u stek, stack[1] je 2, a TOP se povećava za 1 i postaje 1; kada se element 3 potisne u stek, stack[2] je 3, a TOP se povećava za 1 i postaje 2; nakon što se element 3 izbaci iz steka, vraća se element stack[2], a TOP se smanjuje za 1 i postaje 1.

Stek po meri

Pretpostavimo da su elementi u steku tipa int; možemo koristiti Java jezik da definišemo najjednostavniji stek. Potrebna su mu 3 polja:

  • int arr[], niz tipa int za čuvanje podataka
  • int top, oznaka tipa int
  • int capacity, kapacitet tipa int
class Stack { 
     private int arr[]; 
     private int top; 
     private int capacity; 
 }

Inicijalizacija steka:

Stack(int size) { 
     arr = new int[size]; 
     capacity = size; 
     top = -1; 
 }

Potiskivanje elementa u stek:

public void push(int x) { 
     if (isFull()) { 
         System.out.println("Prekoračenje\nProgram obustavljen\n"); 
         System.exit(1); 
     } 
  
     System.out.println("Potisnuto " + x); 
     arr[++top] = x; 
 }

Izbacivanje elementa iz steka:

public int pop() { 
     if (isEmpty()) { 
         System.out.println("Stek je prazan"); 
         System.exit(1); 
     } 
     return arr[top--]; 
 }

Vraćanje veličine steka:

public int size() { 
     return top + 1; 
 }

Provera da li je stek prazan:

public Boolean isEmpty() { 
     return top == -1; 
 }

Provera da li je stek pun:

public Boolean isFull() { 
     return top == capacity - 1; 
 }

Dodajmo main() metod za direktan test:

public void printStack() { 
     for (int i = 0; i <= top; i++) { 
         System.out.println(arr[i]); 
     } 
 } 
  
 public static void main(String[] args) { 
     Stack stack = new Stack(5); 
  
     stack.push(1); 
     stack.push(2); 
     stack.push(3); 
     stack.push(4); 
  
     stack.pop(); 
     System.out.println("\nNakon izbacivanja elementa"); 
  
     stack.printStack(); 
 }

Rezultat ispisa je sledeći:

Potisnuto 1 
Potisnuto 2 
Potisnuto 3 
Potisnuto 4 

Nakon izbacivanja elementa 
1 
2 
3

Pošto smo stek implementirali pomoću niza, vremenska složenost operacija push i pop je O(1).

Iako je stek vrlo jednostavna struktura podataka — što se, nadam se, vidi iz gornjeg koda, lako se implementira — ipak je izuzetno moćna struktura koja se može koristiti u mnogim scenarijima, kao što su:

1)Obrtanje niza znakova: pošto je stek LIFO, obrtanje niza znakova je lako — potisnite znakove u stek redosledom kojim se pojavljuju, a zatim ih izbacite.

2)Kalkulator: sećam se da su mi tokom pripravničkog staža dodelili mali projekat — da imitiram Win 7 kalkulator, kako bi proverili da li smo zaista stručni. Da bi se izračunao složen izraz, npr. 2 + 5 / 3 * (6 - 2), potreban je stek koji bi prihvatio te brojeve i operatore, a zatim ih na osnovu prioriteta izbacivao i računao.

Hmm, taj proračun je malo složeniji nego što se čini; mladi kolege mogu ga pokušati sami — ne samo da će produbiti razumevanje strukture podataka steka, već će i razmisliti o prioritetu operatora.

Očigledno, stek mi je doneo priliku za pripravnički staž i spasio me od opasnosti da budem eliminisan.

3)Browser: dugme za nazad u pregledaču gura URL-ove koje posetimo u stek; svaki put kada posetimo novu stranicu, novi URL se potiskuje na vrh steka; kada kliknemo na dugme za nazad, najnoviji URL se uklanja iz steka, pa se pristupa onom prethodnom URL-u.

Dobro, kraj časa, toliko o steku za danas.

Klasa Stack

Zapravo, Java je već implementirala stek za nas, i to je java.util.Stack, koja nasleđuje Vector i bezbedna je za niti — pomalo podseća na StringBuffer, malo nespretna.

Najpre jednostavan primer:

Stack<String> stack = new Stack<>();
stack.push("Chenmo Wang Er");
stack.push("Chenmo Wang San");
stack.push("Programer čiji su članci zaista smešni");

System.out.println(stack);

Klasa Stack nije komplikovana, ima samo nekoliko važnih metoda, kao što su push, pop, peek, empty, search itd.

Pogledajmo izvorni kod push metoda:

public E push(E item) { 
     addElement(item); 
  
     return item; 
 }

Iako metod push nema ključnu reč synchronized, on poziva addElement metod klase Vector, na kom je dodata ključna reč synchronized.

public synchronized void addElement(E obj) { 
     modCount++; 
     ensureCapacityHelper(elementCount + 1); 
     elementData[elementCount++] = obj; 
 }

Pogledajmo zatim izvorni kod pop metoda:

public synchronized E pop() { 
     E obj; 
     int len = size(); 
  
     obj = peek(); 
     removeElementAt(len - 1); 
  
     return obj; 
 }

Ovaj metod ima ključnu reč synchronized i prvo poziva peek metod da dohvati element s vrha steka:

public synchronized E peek() {
    int     len = size();

    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}

Zatim poziva removeElementAt metod klase Vector da ukloni element s vrha steka.

Imajte na umu da, ako ovaj metod ne uklanja element s vrha steka, on takođe poziva System.arraycopy za kopiranje niza, jer je donji sloj steka implementiran pomoću niza.

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    protected Object[] elementData;
    protected int elementCount;
    protected int capacityIncrement;
}

Rezime

Stek je vrlo korisna struktura podataka; odlikuje se time da je "poslednji ušao, prvi izašao" i može se koristiti za obrtanje niza znakova, implementaciju kalkulatora, dugme za nazad u pregledaču itd.

Iako se klasa Stack retko koristi, struktura podataka steka je vrlo važna. U Javi se preporučuje upotreba ArrayDeque-a umesto Stack-a, jer ArrayDeque nije bezbedan za niti i ima bolje performanse.

Ako želite da vežbate preko LeetCode-a, možete pokušati sledeći zadatak:

Važeće zagrade — rešenje sam stavio na platformu, možete ga pogledati kao referencu.