1.3 Stakke og køer

Mange grundlæggende datatyper repræsenterer samlinger af objekter. Nærmere betegnet består datatypens værdimængde af samlinger af objekter, mens operationerne tilføjer, fjerner og undersøger objekter i samlingen. I dette afsnit betragter vi tre sådanne typer: sækken, køen og stakken. De tre typer tillader alle, at objekter tilføjes til samlingen, men adskiller sig i, om og i hvilken rækkefølge samlingens objekter kan undersøges eller fjernes.

APG for sæk, kø og stak.

Vi definerer funktionaliteten af abstrakte datatyper ved at specificere en anvendlsesprogrammeringsgrænseflade (APG), som fastægger, hvordan en klient anvender datatypen. Disse samlingsdatatyperne illustrerer desuden to kendetegn ved java: Generiske typer og gennemløb.

public class Bag<Item> implements Iterable<Item>

Bag() en tom sæk

void add(Item item) tilføj et element

boolean isEmpty() er sækken tom?

int size() antal elementer i sækken

public class Bag<Item> implements Iterable<Item>
	Bag()	en tom sæk
void	add(Item item)	tilføj et element
boolean	isEmpty()	er sækken tom?
int	size()	antal elementer i sækken

public class Queue<Item> implements Iterable<Item>

Queue() en tom kø

void enqueue(Item item) tilføj et element «sidst» i køen

Item dequeue() afkø et element, dvs. fjern køens «første» (eller «ældste») element

boolean isEmpty() er køen tom?

int size() antal elementer i køen

public class Queue<Item> implements Iterable<Item>
	Queue()	en tom kø
void	enqueue(Item item)	tilføj et element «sidst» i køen
Item	dequeue()	afkø et element, dvs. fjern køens «første» (eller «ældste») element
boolean	isEmpty()	er køen tom?
int	size()	antal elementer i køen

public class Stack<Item> implements Iterable<Item>

Stack() sen tom stak

void push(Item item) stak et element, dvs. læg det «øverst» på stakken

Item pop() afstak et element, dvs. fjern stakkens «øverste» (eller «yngste») element

boolean isEmpty() er stakken tom?

int size() antal elementer i stakken

public class Stack<Item> implements Iterable<Item>
	Stack()	sen tom stak
void	push(Item item)	stak et element, dvs. læg det «øverst» på stakken
Item	pop()	afstak et element, dvs. fjern stakkens «øverste» (eller «yngste») element
boolean	isEmpty()	er stakken tom?
int	size()	antal elementer i stakken

Generiske typer. Vi ønsker at repræsentere samlinger af vilkårlige typer af data. I java muliggøres dette ved hjælp af generiske typer, også kaldet polymorfe typer. Notationen <Item> efter klassenavnet i vores programmeringsgrænseflader definerer navnet Item som typeparameter, dvs. en symbolsk pladsholder for den konkrete type, klienten måtte bruge. Man kan læse Stack<Item> som «stak af items». For eksempel bruger følgende kode en stak af strenge:
Stack stack = new Stack(); stack.push("Test"); ... String next = stack.pop();
Selvpakning. Typeparametre skal være referencetyper, dvs. delklasser af Object. For at understøtte brugen af primitive typer som typeparameter konverterer Java automatisk mellem primitive typer og de tilsvarende pakketyper i tildelinger, metodeargumenter og aritmetiske og logiske udryk. På denne måde kan man bruge primitive typer i forbindelse med generiske typer, som i den følgende kodestump:
Stack<Integer> stack = new Stack<Integer>(); stack.push(17); // selvpakning (fra int til Integer) int i = stack.pop(); // selvudpakning (fra Integer til int)
Den automatiske konvertering mellen en primitiv type og dens pakketype kaldes selvpakning. Den omvendte konvertering fra pakketypen tilbage til den primitive type faldes selvudpakning.
Gennemløb af samlinger. I mange anvendelser ønsker klienten at gennemløbe alle elementer i en samling. Dette paradigme støttes af javas for-hver-konstruktion. Antag fx at samlingen collection er en kø af transaktioner, Queue<Transaction>. Samlingen collection kan gennemløbes, hvis den implementerer grænsefladen Iterable. I så fald kan klienten udskrive transaktionerne med en enkel sætning:
for (Transaction t : collection) StdOut.println(t);
Sæk. En sæk en en samling som ikke understøtter fjernelse. Sækken muliggør indsamling af elementer og gennemløb af de indsamlede elementer. Programmet Stats.java er en sækkeklient som læser en sekvens af reelle tal fra standardindput og udskriver deres gennemsnit og standardafvigelse.
Kø. An kø en en samling baseret på princippet først ind, først ud (FIFU). Princippet at behandle opgaver i samme rækkefølge, som de ankommer, møder vi hyppigt i hverdagen: kunder, som står i kø hos bageren, eller biler, der venter ved en betalingsskranke.
Stak. En stak en en samling baseret på princippet sidst ind, først ud (SIFU). Funktionaliteten kendes fx fra tilbage-knappen på en weblæser, som afstakker de sidste besøgte sider. Programmet Reverse.java er en stakklient, som læser en sekvens af heltal fra standardindput og udskriver dem i omvendt rækkefølge.
Evaluering af aritmetiske udtryk. Programmet Evaluate.java er en stakklient som evaluerer fuldt parentetiserede aritmetiske udtryk. Klienten bruger en algoritme af Edgar W. Dijkstra som baseres på to stakke \(O\) og \(V\) til henholdsvis operatorer og værdier. Algoritmen gennemløber udtrykket fra venstre til højre og behandler hvert symbol som følger:
- Hvis symbolet er en værdi, lægges værdien på \(V\).
- Hvis symbolet er en operator, lægges operatoren på \(O\).
- Venstreparenteser ignoreres.
- Hvis symbolet er en højreparentes, afstakkes en operator fra \(O\) og en eller to værdier fra \(V\), afhængigt af operatorens aritet. Den givne operation udføres og resultatet lægges på \(V\).
Dette er et enkelt eksempel af en kommandofortolker.

Samlinger implementeret med rækker og dynamiske rækker.

Stak af strenge med fast kapacitet. Programmet FixedCapacityStackOfString.java implementerer en stak med fast kapacitet ved brug af en række.
Generisk stak med fast kapacitet. Programmet FixedCapacityStack.java implementerer en generisk stak med fast kapacitet ved brug af en række.
Stak ved brug af dynamisk række. Programmet ResizingArrayStack.java implementerer en generisk stak ved brug af en dynamisk række. I en dynamisk række ændres størrelsen i forhold til antallet af elementer, således at rækken er stor nok til at indholde alle elementer, men ikke så stor, at den ødsler med pladsen. Vi fordobler rækkens størrelse ved stakning (i metoden push()), hver gang rækken bliver fuld. Vi halverer rækkens størrelse ved afstakning (i metoden pop()), når rækken er fyldt til mindre end en fjerdedel.
Kø ved brug af dynamisk række. Programmet ResizingArrayQueue.java implementerer en kø ved brug af en dynamisk række.

Hægtede lister.

En hægtet liste er en rekursiv datastruktur, som enten er tom (nullisten) eller henviser til en knude, der indedholder et generisk element og en henvisning til en hægtet liste. For at implementere hægtede lister begynder vi med at definere knudeabstraktionen i en indre privatklasse:

private class Node {
   Item item;
   Node next;
}

Opbygning af hægtede lister. For at bygge en hægtet liste med elementerne to, be og or skaber vi først en knude Node for hvert element, sætter feltet item i hver knude til den pågældende streng og hægter endeligt knuderne sammen ved at sætte next-felterne.
Indsættelse i begyndelsen. Det er nemmest at indsætte nye knuder i begyndelsen af en hægtet liste.
Fjernelse fra begyndelsen. Det er også nemt at fjerne den første knude i en hægtet liste.
Indsættelse i enden. For at kunne indsætte en knude i slutningen af en hægtet liste opretholder vi en henvisning til listens sidste knude.
Gennemløb. Idiomet for at gennemløbe knuderne i en hægtet liste er som følger:
for (Node x = first; x != null; x = x.next) { // behandl x.item }

Samlinger implementeret med hægtede lister.

Stak implementeret som hægtet liste. Programmet Stack.java implementerer en generisk stak ved brug af en hægtet liste. Programmet repræsenterer stakken som hægtet liste med staktoppen i listens begyndelse, refereret af instansvariablen first. For at stakke et nyt element ved push() indsættes det i begyndelsen af listen. For at af afstakke et element ved pop() fjernes det fra begyndelsen af listen.
Kø implementeret som hægtet liste. Programmet Queue.java implementer en generisk FIFU-kø ved brug af en hægtet liste. Programmet opretholder køen som en hægtet liste, hvor elementerne er anbragt i rækkefølge fra det ældste element først til det senest indsatte element sidst. Køens begyndelse refereres af instansvariablen first, køens ende referes af instansvariablen last. For at stille et element i køen ved enqueue() sættes det sidst i den hægtede liste. For at afkø et element fra køen ved dequeue() fjernes det fra begyndelsen af den hægtede liste.
Sæk implementeret som hægtet liste. Programet Bag.java implementerer en generisk sæk ved brug af en hægtet liste. Implementationen er identisk med Stack.java bortset fra at metoden push() har ændret navn til add(), og metoden pop() er fjernet.

Gennemløb.

For at forstå, hvordan man gennemløber en hægtet liste, betragter vi først en stump klientkode, der udskriver alle elementer i en samling strenge på hver sin linje.

Stack<String> collection = new Stack<String>();
...
for (String s : collection)
   StdOut.println(s);
...

Denne for-hver-konstruktion er bare en forkortelse for følgende while-sætning:

Iterator<String> i = collection.iterator();
while (i.hasNext()) { 
   String s = i.next();
   StdOut.println(s);
}

Følgende skridt er nødvendige for at implementere gennemløb i en samling:

Vi importerer javas grænseflade java.util.Iterator:
import java.util.Iterator;
Vi udvider klassedeklarationen til at love at implementere gennemløbsmetoden iterator() i hendhold til grænsefladen java.lang.Iterable:
implements Iterable<Item>
Vi implementerer en metode iterator(), der returnerer et objekt fra en klasse, der implementerer grænsefladen Iterator:
public Iterator<Item> iterator() { return new ListIterator(); }
Vi implementerer en indre klasse, der implementerer grænsefladen Iterator ved at stille metoderne hasNext(), next() og remove() til rådighed. Den valgfrie metode remove() implementerer vi som en tom metode, fordi vi helst vil undgå muligheden for at en klient forandrer datastrukturen samtidigt med at en anden gennemløber den.
- Den indre klasse ListIterator i Bag.java viser, hvordan man implementerer grænsefladen Iterator, når den underliggende datastruktur er en hægtet liste.
- Den indre klasse ArrayIterator i ArrayResizingBag.java gør det samme, når den underliggende datastruktur en en række.

Grundlæggende begreber

Sortering