Föreläsning 7: Stackar och köer

Länkad lista

En länkad lista består av poster av den här typen.
 
class Node {
    int value;
    Node next;

    public Node(int num) {
	value = num;
	next = null;
    }
}

Den ritas som en rad av lådor där varje låda innehåller ett tal och en referens till nästa låda. Den sista lådan refererar inte till någonting vilket man åstadkommer genom att sätta next = null. För att förenkla skapandet av nya poster finns också en konstruktormetod (Node()) som initierar den nyskapade posten med lämpliga värden.

Listan skapas genom upprepade p = new Node(x) i programmet, där p är deklarerad som Node p och x är ett heltal. För att komma åt den länkade listan måste man åtminstone ha en referens kvar till den första lådan. Beroende på hur man ritar listan kallas den pekaren top, first eller front. Just nu tänker vi oss lådraden som vertikal och använder därför top. Den första posten i listan kan vi skapa så här.

 
    Node top = new Node(17);
Hur dom övriga posterna skapas väntar vi med ett tag. Först måste vi nämligen bestämma oss för om nya poster ska läggas in först i listan eller sist i listan.

Stack och kö

En lista där en ny post läggs in ovanpå listan kallas för stack; en lista där nya poster läggs in sist kallas . I båda fallen gäller att om man ska ta ut en post ur listan, så är det den första som tas ut. En tallrikstrave på en lunchservering är exempel på en stack, en kundkö på posten är exempel på en kö. Eftersom stackar används ständigt i datavärlden har det utbildats en standard för vilka anrop man kan göra till en stack. När man vill lägga elementet x på stacken gör man anropet stack.push(x). När man vill ta bort översta elementet heter det y = stack.pop(), där y sedan kan användas. Weiss skriver i stället y=topAndPop(), men tills vidare kör vi med den kortare och vanligare benämningen.

Insättning sist i en kö kan heta enqueue(x) och utplockning av första elementet kan heta y = dequeue(). I stället för dessa ovanliga ord används också put() och get(), särskilt om kön beskrivs av en egen klass Queue. Efter att ha skapat en kö (Queue queue = new Queue()) kan man alltså använda queue.put(x) och y = queue.get().

Både för stack och kö kan det finnas ytterligare anrop definierade. Viktigast är den booleska metoden empty(), alltså till exempel

    if (stack.empty())
	stack.push(4711);
 
    while (!queue.empty())
	System.out.print(queue.get());   
Nu närmast ska vi skriva en metod stack.show() som skriver ut stackens innehåll på skärmen (utan att förstöra stacken).

Att gå igenom lista

Sätt ett pekfinger på översta posten, skriv ut talet i posten på skärmen, flytta pekfingret till nästa post, skriv ut talet etc. Sluta när pekfingret pekar ut i tomma intet.
 
    public void show() {
        Node p = top;
        while(p != null) {
            System.out.print(p.value + " ");
            p = p.next;
	}
    }
Varför behövs hjälppekaren p? Följande kod skriver också ut stacken, men efteråt är inte stacken sej lik!
 
    public void show() {
        while(top != null) {
            System.out.print(top.value + " ");
            top = top.next;
	}
    }

Att ta bort en post ur listan

Den första posten tas lätt bort ur listan med satsen top = top.next;. Vi vill dock att anropet pop() ska returnera det tal som fanns i den borttagna posten och därför är det bäst att kopiera över talet i variabeln x innan man tar bort posten.
 
    public int pop() {
	int x = top.value;
    	top = top.next;
    	return x;
    }
Om stacken är tom, dvs top är null, kommer uttrycket top.value att ge felavbrott. Därför är det bäst att vara säker på att stacken inte är tom innan man anropar pop().

Att sätta in en post i listan

En ny post med talet x i skapas med
 
    Node p = new Node(x);
Om den ska läggas på en stack behövs följande satser.
 
    p.next = top;
    top = p;
Om den ska in sist i en kö ser det oftast ut så här.
 
    back.next = p;
    back = p;
Men! Om kön är tom kan man inte skriva back.next, och då gör man i stället så här.
 
    front = p;
    back = p;

En heltalsstack

Här har vi lagt alla stackmetoderna i en klass IntStack. Då vi i framtiden kanske vill ha flera stackar låter vi klassen IntStack vara en mall och utelämnar därmed alla static. När vi vill ha en ny heltalsstack skapar vi den först med new IntStack(). Exempel:
 
    IntStack stacken = new IntStack();
    stacken.push(17);
    // flera push()...
    stacken.show();
    while (!stacken.empty()) {
	int x = stacken.pop();
	// Gör något med talet vi plockade ut...
    }
Och så här ser klassen ut. Lägg märke till att pekaren top är private, så man kan inte komma åt top utanför klassen.
class Node {
    int value;
    Node next;

    public Node(int num) {
	value = num;
	next = null;
    }
}// Node

public class IntStack {
    private Node top;

    public IntStack() {
	top = null;
    }

    public void push(int x) {
	Node p = new Node(x);
	p.next = top;
	top = p;
    }

    public int pop() {
	int x = top.value;
	top = top.next;
	return x;
    }

    public boolean empty() {
	return (top == null);
    }

    public void show() {
	Node p = top;
	while(p != null) {
	    System.out.print(p.value + " ");
	    p = p.next;
	}
    }
}// IntStack


^ Upp till kurssidan.


Sidansvarig: <efo@nada.kth.se>
Senast ändrad 16 januari 2003
Tekniskt stöd: <webmaster@nada.kth.se>