Oppgave 1

En innlegging av verdiene 1, 2, 3, 3, 3 vil gjøre at de får samme rekkefølge i tabellen siden en ny verdi alltid legges bakerst. For å skille de tre treerne setter vi et nr. bak hver av dem som forteller rekkefølgen de ble lagt inn, dvs. tabellen inneholder 1, 2, 3(1), 3(2), 3(3). Den første som tas ut er den minste, dvs. 1. Deretter flyttes den bakerste til den plassen 1 hadde. Dermed blir tabellen lik: 3(3), 2, 3(1), 3(2). Så er det 2 som tas ut og dermed: 3(3), 3(2), 3(1). Så den første treeren: 3(1), 3(2). Igjen den første treeren og det som blir igjen i tabellen er: 3(2). Når den til slutt tas ut har de tre treerne blitt tatt ut i denne rekkefølgen: 3(3), 3(1), 3(2). På grunn av at den bakerste flyttes til den plassen der den minste lå, vil rekkefølgen like verdier tas ut i være helt uforutsigbart.

Oppgave 2

  public boolean taUt(T verdi)
  {
    int i = 0;
    for (; i < antall; i++)
    {
      if (c.compare(a[i],verdi) == 0) break;
    }

    if (i == antall) return false;  // fant ikke verdi

    antall--;            // reduserer antallet
    a[i] = a[antall];    // tetter igjen ved å flytte den siste verdien

    a[antall] = null;    // nuller for resirkulering
    return true;         // returnerer den minste    
  }

Oppgave 3

import java.util.*;

public class UsortertLenketPrioritetsKø<T> implements PrioritetsKø<T>
{
  private static final class Node<T>
  {
    private T verdi;
    private Node<T> neste;

    private Node(T verdi, Node<T> neste)
    {
      this.verdi = verdi; this.neste = neste;
    }
  } // class Node

  private Node<T> hode;
  private Comparator<? super T> c;
  private int antall;

  public UsortertLenketPrioritetsKø(Comparator<? super T> c)
  {
    this.c = c;
    hode = null;
    antall = 0;
  }

  public void leggInn(T verdi)
  {
    hode = new Node<T>(verdi,hode);
    antall++;
  }

  public T kikk()
  {
    if (antall == 0) throw new NoSuchElementException();

    T maksverdi = hode.verdi;

    for (Node<T> p = hode.neste; p != null; p = p.neste)
      if (c.compare(p.verdi,maksverdi) > 0)
        maksverdi = p.verdi;

    return maksverdi;
  }

  public T taUt()
  {
    if (antall == 0) throw new NoSuchElementException();

    T maksverdi = hode.verdi;
    Node<T> q = null;

    for (Node<T> p = hode; p.neste != null; p = p.neste)
      if (c.compare(p.neste.verdi,maksverdi) > 0)
      {
        maksverdi = p.neste.verdi;
        q = p;
      }

    if (q == null) hode = hode.neste;
    else q.neste = q.neste.neste;

    antall--;

    return maksverdi;
  }

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

  public int antall()
  {
    return antall;
  }

  public void nullstill()
  {
    hode = null;
    antall = 0;
  }

  public String toString()
  {
    if (antall == 0) return "[]";

    StringBuilder s = new StringBuilder();
    s.append('['); s.append(hode.verdi);

    for (Node<T> p = hode.neste; p != null; p = p.neste)
    {
      s.append(','); s.append(' '); s.append(p.verdi);
    }
    s.append(']');

    return s.toString();
  }

}  // class UsortertLenketPrioritetsKø