Lab 3 - Stackar, köer, listor mm

Uppgiften

Den här laborationen går ut på att lära sig mekanismerna för de grundläggande länkade datastrukturerna Lista, Stack, och Kö och att få prova på att skapa en egen iterator. Dessa klasser ska göras som generiska klasser. Ni får även öva på undantag, interface och paket.

Scenariot är en simulering av en stormarknad med kunder som kommer och handlar varor och går till kassan. För att hålla reda på kunderna används en lista, för en kunds varukorg används en stack, och för kunderna i en kassa används en kö, så klart!

Er uppgift är att implementera ett paket som heter myutil som innehåller de generiska klasserna MyList, MyStack och MyQueue. MyList ska också kunna returnera en instans av MyListIterator som implementerar interfacet Iterator för listan (detta interface finns definierat i paketet java.util). Era klasser ska följa specifikationen nedan. Samtliga klasser ska vara generiska, dvs kunna innehålla element av godtycklig typ.

I den här labben ska ni själva programmera dessa datastrukturer, för att få en insikt i hur de är uppbyggda. Implementationen ska göras med hjälp av en länkad struktur med noder, för att ni ska få öva på detta. Ni ska alltså inte använda existerande datastrukturklasserna i Javas klassbibliotek, exempelvis LinkedList, vilket man annars normalt skulle göra, utan göra er helt egna implementation av en länkad lista.

Det finns ett stormarknadssimuleringsprogram som använder klasserna MyList, MyStack och MyQueue. När era klasser är implementerade korrekt ska detta gå att köra och fungera på ett rimligt sätt. Utöver detta program kan det vara bra att göra separata testprogram för era klasser för att säkerställa att de fungerar. Dessutom är det bra att kunna testa varje klass för sig innan alla andra klasser är klara. Detta är obligatoriskt för att testa att MyListIterator verkligen fungerar korrekt. Ett exempel på ett testprogram för MyStack finns tillgängligt. Testklasserna ska inte ligga i paketet myutil, utan i ett annat, fristående paket.

Definition av klasser som ska implementeras

De klasser ni ska implementera (förutom testprogram) ska ligga i ett paket som heter myutil. Lägg paketet i en egen mapp som heter myutil. Tänk igenom hur synligheten av klasser och variabler bör se ut när de ligger i ett paket. Bör alla klasser vara synliga utanför paketet tex?

De klasser ni ska implementera ska fungera som respektive abstrakt datatyp är beskriven i kursboken. Enbart de metoder som finns i klassbeskrivningarna nedan behöver dock implementeras.

MyStack<E>

Metoder
 public void push(E element)
    Lägger till ett element först i stacken
 
 public E pop()
    Ger det första elementet i stacken
    Kastar exception
    
 public boolean isEmpty()
    Funktion för att ta reda på om stacken är tom
     
 public int size()
    Ger antalet element i stacken

MyQueue<E>

Metoder
 public void enqueue(E element)
    Lägger till ett element sist i kön
 
 public E dequeue()
     Ger elementet först i kön
     Kastar exception
     
 public boolean isEmpty()
     Funktion för att ta reda på om kön är tom
     
 public int size() 
    Ger antalet element i kön

MyList<E>

Ska vara en "singly linked list"
Metoder
 public void add(E element)
    Ska lägga till ett nytt element i listan 
    
 public E getRandomElement()
    Ska returnera ett slumpmässigt element utan att ta bort det ur listan
    Kastar exception
    
 public boolean isEmpty()
     Funktion för att ta reda på om listan är tom
    
 public int size()
    Ger antalet element i listan
 
 public Iterator<E> iterator()
    Returnerar en instans av MyListIterator för den aktuella listan

MyListIterator<E>

(För detaljer om hur de här funktionerna ska fungera, se specifikationen av interfacet i Javas API, länkat nedan:) 
MyListIterator<E> implements Iterator<E>
Metoder
 public boolean hasNext()
 
 public E next()
    Kastar exception
  
 public void remove()
    Kastar exception

E ovan är den generiska typen för datat som ska lagras i strukturerna.

I en del metoder kan det uppstå fel som ska leda till att ett undantag (Exception) kastas. Vilka metoder detta gäller ses ovan. Ett exempel är metoden pop(), vilken ska ge ett undantag om den körs på en tom stack. De undantag ni kastar kan lämpligtvis vara befintliga undantagsklasser. Det är dock även möjligt att göra egna undantagsklasser, som isf ärver från lämplig befintlig undantagsklass. Undantagsklassen ska vara rimlig, det vill säga beskriva felet som uppstår på något sätt. Titta gärna i befintliga klasser som LinkedList vad de kastar för undantag i liknande situationer. Era undantagsklasser måste vara av typen RuntimeException för att det ska fungera med kodskelettet. Använd gärna Javas API för att hitta lämpliga klasser. Tips: börja med att hitta RuntimeException och se i JavaDoc'en vilka klasser det finns som ärver av den.

Utöver detta kommer det att behövas en nodklass, konstruktorer för klasserna, och antagligen en del privata hjälpfunktioner. Nodklassen ska ligga i paketet myutil, och användas av de övriga klasserna. Ni ska alltså inte ha undantagsklassen som en intern klass i era andra klasser, eftersom den koden i så fall måste upprepas på flera ställen.

Ni ska kommentera era klasser och metoder med javadoc-kommentarer, och generera javadoc-dokumentation.

Given kod

Testprogrammet finns här. Spara koden i filerna Supermarket.java, Customer.java och Checkout.java, i den katalog du tänkt jobba i.

Skumma igenom den givna koden lite kort, och notera t.ex. hur det finns en delay i SuperMarket som justerar hur fort programmet kör, och hur slumpen används för att göra varje körning annorlunda från den föregående. Starta simuleringen med klassen Supermarket där main-metoden finns.

Examination

Bifoga följande i ett mail till er labassistent:

  • All källkod. Alla klasser och publika metoder ska vara kommenterade med javadoc-kommenterar. Koden ska följa kodstandarden och vara enhetligt indenterad.
  • En länk till er javadoc-dokumentation

Checklista för inlämnat material:

  • Är alla delar inlämnade?
  • Används lämpliga och tydliga namn för klasser, metoder och variabler?
  • Följer koden kodkonventionerna(se "Kursmaterial")?
  • Är koden enhetligt indenterad?
  • Är koden kommenterad enligt kodkonventionen?
  • Används en rimlig åtkomstnivå för klasser, variabler och metoder?
  • Uppfyller programmet kravspecifikationen?
  • Ligger era klasser i ett paket som heter myutil?
  • Är paketet välstrukturerat?
  • Är datastrukturerna implementerade med hjälp av en egen nod-klass?
  • Testar testprogrammet för MyListIterator att alla metoder för iteratorn fungerar korrekt?


Ursprungligen skapad för kurserna HKGBB7 och TDDC30 vid Linköpings universitet av Mikael Kindborg, Sara Stymne, Johan Janzén, Jonas Lindgren m.fl 2004-2013. Uppdaterad för 5LN446 av Sara Stymne 2013.