Stakker

Innhold

En stakk - eller stabel - er en samling der vi til enhver tid kun har tilgang til elementet som ble lagt inn sist. Et nytt element legges alltid på toppen av stakken. Hvis vi skal ta ut element, tar vi alltid det øverste. Virkemåten kan sammenliknes med en stabel tallerkener. Den tallerkenen som ble lagt på stabelen sist (den øverste), er vanligvis den vi tar ut først. En stakk behandles på en måte som på engelsk kan beskrives som "Last in, first out" (LIFO). Stakker kalles derfor også for LIFO-køer.

Stakker er nyttige i forskjellige problemstillinger. For eksempel kan "undo"-operasjonen i tekstbehandlere implementeres ved bruk av en stakk. En representasjon av endringene vi gjør på et dokument legges fortløpende på en stakk. Når vi velger "undo", tas siste operasjon vi utførte på dokumentet av stakken og reverseres. Implementasjon av kompilatorer er en annen anvendelse, det stakker blant annet brukes til å kontrollere at paranteser og andre symboler som skal balansere kommer riktig i forhold til hverandre.

Hva er en stakk?

• Samling der vi til enhver tid kun har tilgang til elementet som ble lagt inn sist.
• Et nytt element legges alltid på toppen av stakken.
• Skal vi ta ut et element, tar vi alltid det øverste.
• Sammenlikning: Stabel med tallerkener.
• LIFO-kø (Last in, first out).
• Stakker brukes ofte til å snu rekkefølgen på ting. Ved å pushe alle elementene på stakken og deretter poppe de, blir rekkefølgen snudd.

Grensesnittet Stakk

• Grensesnittet Stakk vist nedenfor inneholder operasjonene som vanligvis kan utføres på en stakk.
• For stakker, kalles operasjonene for å legge til, fjerne og finne for henholdsvis push, pop og top.
• Dere vil kunne finne variasjoner i operasjoner og navnekonvensjoner. For eksempel kalles operasjonen top noen steder for peek.
• Ingen av operasjonene som er listet opp i grensesnittet tillater oss å gå ned i stakken for å fjerne eller omorganiserer elementene på stakken. All aktivitet foregår på toppen av stakken. Hvis vi finner ut at vi trenger tilgang til for eksempel midtre element på stakken for å løse et problem, eller at elementene på stakken burde omorganiseres, har vi valgt feil datastruktur.

package stakker;

public interface Stakk<E> {    
    public void push(E element); // Legge et nytt element p�� stakken
    public E pop(); //Fjerne og returnere ��verste element p�� stakken
    public E top(); //Returnerer ��verste element p�� stakken uten �� fjerne det
    public int antall(); // Antall elementer p�� stakken
    public boolean erTom(); // Er stakken tom 
}

Palindromtester

Palindromer er ord som blir det samme om de leses forlengs eller baklengs, for eksempel "regninger" og "abba".

Oppgave

Lag en algoritme som gjør bruk av en stakk for å bestemme om et ord eller setning er et palindrom eller ikke. Algoritmen må virke både på like og odde antall tegn!

Kompilatorer

• Kompilatorer bruker stakker blant annet til å kontrollere at paranteser kommer riktig i forhold til hverandre, d.v.s. at symbolene balanserer.
• For eksempel må det for hver { finnes en }, for hver [ må det finnes en ] og så videre.
• Opptelling av antall åpningsparanteser og antall sluttparanteser er utilstrekkelig, fordi parantesene også må være riktig plassert i forhold til hverandre. For eksempel er sekvensen [()] riktig, mens sekvensen [(]) er feil.

Algoritme for å sjekke om parantesene balanserer

1. Lag en tom stakk.
2. Les ett og ett tegn fra input-fil:
   1. Hvis lest tegn er en startparantes, push det på stakken.
   2. Ellers, hvis lest tegn er en sluttparantes:
      1. Hvis stakken er tom, rapporter feil.
      2. Ellers, pop stakken og sjekk og symbolet som poppes er korresponderende startparantes. Hvis ikke, rapporter feil.
3. Hvis stakken ikke er tom når alle tegn er lest, rapporter feil.

En enkel implementasjon av parantessjekkeren

package stakker;

import java.util.Stack;

public class ParantesSjekker {
    private static final char [] startParanteser = {'{','[','(','<'};
    private static final char [] sluttParanteser = {'}',']',')','>'}; 
            
    public boolean erBalansert(String input){
        Stakk<Character> stakk = new LenketStakk<Character>(); 
                
        // Leser ett og ett tegn: 
        for (int i=0; i<input.length(); i++){
            char tegn = input.charAt(i); 
            
            // Hvis ��pningsparantes -push p�� stakken
            if (erStartParantes(tegn)){
                System.out.println("Pusher " + tegn + " p�� stakken. "); 
                stakk.push(tegn);
            }
            else if (erSluttParantes(tegn)){
                // Hvis stakken er tom, er ikke parantesene balansert
                if(stakk.erTom())
                    return false; 
                else {
                    char tmp = stakk.pop(); 
                    System.out.println("Popper " + tegn + " av stakken. "); 
                    if (!erPar(tmp, tegn)){
                        System.out.println(tegn + " og " + tmp + " er ikke par! "); 
                        return false; 
                    }
                }
            }            
            // HVis ikke tegn er start- eller sluttparantes, gj��r vi ingenting. 
        }        
        // N�� er alle tegn lest. Parantesene er balansert hvis stakken er tom. 
        return stakk.erTom();        
    }
    
    public boolean erStartParantes(char tegn){
                
        for (char c: startParanteser){
            if(tegn == c)
                return true; 
        }        
        return false;               
    }
    
    public boolean erSluttParantes(char tegn){
        for (char c: sluttParanteser){
            if(tegn == c)
                return true; 
        }
        return false; 
    }
    
    public boolean erPar(char start, char slutt ){
        for (int i=0; i<startParanteser.length; i++)
            if (start == startParanteser[i] && slutt == sluttParanteser[i] )
                return true; 
        return false; 
    }
    
    public static void main(String [] args){
        ParantesSjekker sjekker = new ParantesSjekker();
        System.out.println(sjekker.erBalansert("{[()]}"));                
    }
}

Postfixevaluering

Vi er vant med aritmetiske uttrykk skrevet i infix-notasjon, det vil si at operatorene plasseres mellom operandene. For eksempel:

1 + 9 
1 + 4 * 2
1 + 2 * 3 + 4 * 5 

Når vi evaluerer infix-uttrykk, må vi ta hensyn til presedens-reglene. Alternativt kan aritmetiske uttrykk skrives på postfix-form, det vil si at operatorene kommer etter operandene:

1 9 +  
1 4 2 *+ 
1 2 3 *+ 4 5 * +

Slike uttrykk er enklere å evaluere fordi man ikke trenger å ta hensyn til presedensreglene. Rekkefølgen av operandene (verdiene) og operatorene i uttrykket er tilstrekkelig til å bestemme uttrykkets verdi.

Postfixmaskin

Uttrykk på postfix form kan forholdsvis enkelt evalueres ved bruk av en stakk:

 	
Lag en ny stack S
2. Lag to referanser venstre, høyre til datatyper Operand
3. For alle tegn T i i uttrykket:
	3.1 Hvis T er en operand: Push T på S
	3.2 Ellers:
		3.2.1 Sett høyre til S.pop
		3.2.2 Sett venstre til S.pop
		3.2.3 S.push( eval(venstre, T, høyre) )
4. Returner toppen av S
		
eval(1,+,2) er vanlig infix evaluering: 1 + 2 = 3.

infix2postfix

En stakk kan også brukes til å konvertere et uttrykk på standard-form (infix-notasjon) til postfix. Algoritmen nedenfor gjelder for infix-uttrykk uten paranteser, og kun for operatorene +-*/:

1. Lag en ny stack S
2. For alle tegn T i uttrykket:
  2.1. Hvis T er en operand: Skriv ut T
  2.2. Ellers:
  	2.2.1. Så lenge T har lavere rang enn toppen av S:
		2.2.1.1 Pop S og skriv ut
	2.2.2. Push T på S
3. Pop hele S og skriv ut

Traversere en labyrint

• Labyrint bygget opp som en 2-dimensjonal tabell bestående av 0-er og 1-ere.
• 1: vei
• 0: hindring
• Vil traversere labyrinten, starter opp i øvre venstre hjørne og ende opp i nedre høyre hjørne.
• Strategi:
  • Vi følger en vilkårlig vei så langt som mulig.
  • Hvis vi kommer til en blindvei, returnererer vi til foregående posisjoner i motsatt rekkefølge, og prøver en av de av de andre veiene videre derfra.
  • Besøkte posisjoner må merkes, slik at vi unngår å gå i ring.

Implementasjon

En noe modifisert variant av programmet fra læreboka.

package stakker;

import java.util.Stack;

public class Labyrint {

    public static final char PROVD = '0';
    public static final char STI = '+';
    
    
    public char[][] grid =
            {{' ', ' ', ' ', 'X', ' ', ' ', 'X', 'X', 'X', ' ', ' ', ' ', ' '},
        {' ', 'X', 'X', ' ', ' ', 'X', ' ', ' ', ' ', ' ', 'X', 'X', ' '},
        {' ', ' ', ' ', ' ', ' ', 'X', ' ', 'X', ' ', 'X', ' ', 'X', 'X'},
        {'X', 'X', 'X', 'X', ' ', ' ', ' ', 'X', ' ', 'X', ' ', ' ', ' '},
        {' ', ' ', ' ', 'X', ' ', ' ', ' ', 'X', ' ', 'X', ' ', ' ', ' '},
        {' ', 'X', ' ', 'X', 'X', 'X', 'X', ' ', ' ', ' ', 'X', 'X', ' '},
        {' ', 'X', ' ', ' ', ' ', ' ', ' ', ' ', 'X', ' ', ' ', ' ', ' '},
        {' ', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
        {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '}};

    
    /*
    private char [][] grid = 
    {{' ',' ','X','X','X'}, 
    {'X',' ','X',' ',' '}, 
    {'X',' ',' ',' ',' '}, 
    {'X','X','X','X',' '},
    {'X','X','X','X',' '}}; 
    */
    private Stack<Posisjon> pushNyPos(Posisjon npos, Stack<Posisjon> stack) {

        if (npos.erGyldig()) {
            grid[npos.rad][npos.kolonne] = PROVD;  // merker posisjonen som bes��kt
            stack.push(npos);
            System.out.println("Lagt til p�� stakk: " + npos);
        }

        return stack;
    }

    public void markerSti(Stack<Posisjon> s) {
        while (s.size() > 0) {
            Posisjon pos = s.pop();
            if (pos.erSti) 
                grid[pos.rad][pos.kolonne] = STI;
            else
                System.out.println("Ikke sti: " + pos); 
                    
            //System.out.println(pos.x+","+pos.y);
            
        }
    }

    public boolean traverser() {
        boolean fremme = false;
        Posisjon pos = new Posisjon(0, 0);
       
        Stack<Posisjon> stack = new Stack<Posisjon>();
        
        // Posisjonen til ��vre venstre hj��rne legges p�� stakken
        stack = pushNyPos(new Posisjon(0, 0), stack);

        while (!fremme && (!stack.empty())) {
            
            // Ser p�� ��verste posisjon 
            pos = stack.peek();
            System.out.println("pos: " + pos);
            System.out.println("\t\tstakk:" + stack);
            
            pos.erSti = true; 
            //Sjekker om vi er fremme
            if (pos.rad == grid.length - 1 && pos.kolonne == grid[0].length - 1) {
                fremme = true;  // the maze is solved
                System.out.println("Fremme! ");
            
            } else {
                // Sjekker om det finnes noen veier videre fra ��verste posisjon
                // p�� stakken
                int size = stack.size();
                stack = pushNyPos(new Posisjon(pos.rad, pos.kolonne - 1), stack);
                stack = pushNyPos(new Posisjon(pos.rad, pos.kolonne + 1), stack);
                stack = pushNyPos(new Posisjon(pos.rad - 1, pos.kolonne), stack);
                stack = pushNyPos(new Posisjon(pos.rad + 1, pos.kolonne), stack);

                // Hvis det ikke er noen vei videre, poppes stakken.  
                if (size == stack.size()) {
                    stack.pop();
                }
            }
        }
        markerSti(stack);
        return fremme;
    }

    @Override
    public String toString() {
        String result = "\n";

        for (int rad = 0; rad < grid.length; rad++) {
            for (int kolonne = 0; kolonne < grid[rad].length; kolonne++) {
                result += grid[rad][kolonne] + "";
            }

            result += "\n";
        }

        return result;
    }

    private class Posisjon {

        private int rad;
        private int kolonne;
        private boolean erSti;

        private Posisjon(int x, int y) {
            rad = x;
            kolonne = y;
            erSti = false;
        }

        private boolean erGyldig() {
            boolean svar = false;

            //Sjekker om vi er innenfor tabellens grenser 
            if (rad >= 0 && rad < grid.length &&
                    kolonne >= 0 && kolonne < grid[rad].length) {
                // Sjekker om cellen er pr��vd tidligere eller blokkert. 
                if (grid[rad][kolonne] == ' ') {
                    svar = true;
                }
            }
            return svar;
        }

        @Override
        public String toString() {
            return "(" + rad + ", " + kolonne + ")";
        }
    }

    public static void main(String[] args) {
        Labyrint l = new Labyrint();
        if (l.traverser()) {
            System.out.println("Labyrinten er traversert");
        } else {
            System.out.println("Labyrinten kan ikke traverseres");
        }
        System.out.println(l);
    }
}

Stakk implementert med tabell

package stakker;

public class TabellStakk<E> implements Stakk<E> {

    private static final int KAPASITET = 100; 
    private E [] data; 
    private int topp; 
    
    public TabellStakk() {
        data = (E[])(new Object [KAPASITET]); 
        topp = -1; 
    }
    
    public void push(E element) {
        if (topp +1 == data.length)
            utvidKapasitet();
        
        data[++topp] = element; 
    }

    private void utvidKapasitet() {
        E[] nyTabell =   (E[]) new Object [data.length*2];
        
        for (int i = 0; i < data.length; i++) {
            nyTabell[i] = data[i];
        }

        data = nyTabell;
    }
    
    public E pop() {
        if (erTom())
            return null; 
        
        E tmp = data[topp];
        data[topp--]=null; 
        return tmp;
    }

    public E top() {
        if (erTom())
            return null; 
        return data[topp]; 
    }

    public int antall() {
        return topp; 
    }

    public boolean erTom() {
        return (topp == -1);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder(); 
        for (int i=topp; i>=0; i--)
            sb.append("\t" + data[i]+"\n");
        
        return sb.toString(); 
    }
    
    public static void main(String [] args){
        TabellStakk<Integer> stakk = new TabellStakk<Integer>(); 
        stakk.push(1);
        stakk.push(2);
        stakk.push(3);
        System.out.println(stakk);
        System.out.println("top: " + stakk.top()); 
        while (!stakk.erTom()){
            System.out.println(stakk.pop()); 
        }
    }
}

Stakk implementert med lenket liste

package stakker;
public class LenketStakk<E> implements Stakk<E>{

    private StakkNode topp; 
    private int antall; 
    
    public void push(E element) {
        topp = new StakkNode(element, topp); 
        antall++; 
    }

    public E pop() {
        if (erTom())
            return null; 
        StakkNode tmp = topp; 
        topp = topp.under; 
        antall--;
        return tmp.element; 
    }

    public E top() {
        if (erTom())
            return null; 
        return topp.element; 
    }

    public int antall() {
        return antall; 
    }

    public boolean erTom() {
        return antall == 0; 
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder(); 
        
        StakkNode p = topp; 
        for (int i=0; i<antall; i++){
            sb.append("\t" + p.element+"\n"); 
            p = p.under; 
        }
        return sb.toString(); 
    }
    
    private class StakkNode{
        private StakkNode under; 
        private E element; 
        
        private StakkNode(E element, StakkNode under){
            this.element = element;
            this.under = under; 
        }
    }
    
    public static void main(String [] args){
        Stakk<Integer> stakk = new LenketStakk<Integer>(); 
        stakk.push(1);
        stakk.push(2);
        stakk.push(3);
        stakk.push(4);
        
        stakk.pop(); 
        stakk.pop(); 
        stakk.pop(); 
        stakk.pop(); 
        
        System.out.println(stakk.erTom());         
    }
}

Klassen java.util.Stack

• Inneholder metodene push, pop, peek, empty og search
• Metoden search søker etter et element og returnerer distansen fra toppen av stakken ned til første forekomst av dette elementet.
• Arver fra klassen Vector . Det betyr at diverse operasjoner som kan utføres på en Vector også kan utføres på en Stack, selv om en Vector og en Stack er konseptuelt forskjellige.