Oppgave 1

Oppgave 5,6,7

import java.util.*;

public class TabellKø<T> implements Kø<T>
{
  private T[] a;      // en tabell
  private int fra;    // posisjonen til den første i køen
  private int til;    // posisjonen til første ledige plass

  private T[] utvidTabell(int lengde)
  {
    T[] b = (T[])new Object[lengde];  // ny tabell

    // kopierer intervallet a[fra:a.length> over i b
    System.arraycopy(a,fra,b,0,a.length - fra);

    // kopierer intervallet a[0:fra> over i b
    System.arraycopy(a,0,b,a.length - fra, fra);

    fra = 0; til = a.length;

    return b;
  }

  public TabellKø(int lengde)
  {
    if (lengde < 1)
      throw new IllegalArgumentException("Må ha positiv lengde!");

    a = (T[])new Object[lengde];

    fra = til = 0;    // a[fra:til> er tom
  }

  public TabellKø()   // standardkonstruktør
  {
    this(8);
  }

  public void leggInn(T t)
  {
    a[til] = t;                       // ny verdi bakerst i køen
    til++;                            // øker til med 1
    if (til == a.length) til = 0;     // hopper til 0
    if (fra == til)                   // sjekker om tabellen er full
      a = utvidTabell(2*a.length);    // dobler tabellen
  }

  public T kikk()
  {
    if (fra == til)
      throw new NoSuchElementException("Køen er tom!");

    return a[fra];
  }

  public T taUt()
  {
    if (fra == til) throw new         // sjekker om køen er tom
      NoSuchElementException("Køen er tom!");

    T temp = a[fra];                  // tar vare på den første i køen
    a[fra] = null;                    // nuller innholdet
    fra++;                            // øker fra med 1
    if (fra == a.length) fra = 0;     // hopper til 0
    return temp;                      // returnerer den første
  }

  public int antall()
  {
    return fra <= til ? til - fra : a.length + til - fra;
  }

  public boolean tom()
  {
    return til == fra;
  }

  public void nullstill()
  {
    while (fra != til)
    {
      a[fra++] = null;
      if (fra == a.length) fra = 0;
    }
  }

  public String toString()
  {
    if (til == fra) return "[]";

    int sfra = fra, stil = til;

    StringBuilder s = new StringBuilder();
    s.append('[').append(a[sfra]);
    sfra++;
    if (sfra == a.length) sfra = 0;

    while (sfra != stil)
    {
      s.append(',').append(' ').append(a[sfra]);
      sfra++;
      if (sfra == a.length) sfra = 0;
    }

    s.append(']');

    return s.toString();
  }

}  // TabellKø

Oppgave 8

  public int indeksTil(T t)
  {
    int k = fra;

    while (k != til)
    {
      if (t.equals(a[k]))
        return fra <= k ? k - fra : a.length + k - fra;

      k++; if (k == a.length) k = 0;
    }
    return -1;  // ikke funnet
  }

Oppgave 9

  public static <T> void snu(Stakk<T> A)
  {
    Kø<T> B = new TabellKø<T>();
    while (!A.tom()) B.leggInn(A.taUt());
    while (!B.tom()) A.leggInn(B.taUt());
  }

Oppgave 10

  public static <T> void snu(Kø<T> A)
  {
    Stakk<T> B = new TabellStakk<T>();
    while (!A.tom()) B.leggInn(A.taUt());
    while (!B.tom()) A.leggInn(B.taUt());
  } 

Oppgave 11

  public static <T> void snu(Kø<T> A)
  {
    Kø<T> B = new TabellKø<T>();
    Kø<T> C = new TabellKø<T>();

    while (!A.tom())
    {
      while (!B.tom()) C.leggInn(B.taUt());
      B.leggInn(A.taUt());
      while (!C.tom()) B.leggInn(C.taUt());
    }
    while (!B.tom()) A.leggInn(B.taUt());
  }

Oppgave 12

  public static <T> void snu(Kø<T> A)
  {
    Kø<T> B = new TabellKø<T>();
    int n = A.antall() - 1;

    while (n >= 0)
    {
      for (int i = 0; i < n; i++) A.leggInn(A.taUt());
      B.leggInn(A.taUt());
      n--;
    }

    while (!B.tom()) A.leggInn(B.taUt());
  }  

Oppgave 13

Dette er ikke helt enkelt, men hvis vi tillater oss å bruke metoden bytt() fra Oppgave 4c) i Avsnitt 4.2.1, så blir det enkelt. Den metoden bruker ingen hjelpestrukturer. Da får vi samme type kode som snur innholdet i en tabell:

  public static <T> void snu(Kø<T> A)
  {
    int i = 0, j = A.antall() - 1;

    while (i < j) bytt(A, i++, j--);
  }

Oppgave 14

  public static <T> void sorter(Kø<T> A, Comparator<? super T> c)
  {
    if (A.antall() <= 1) return;

    Kø<T> B = new TabellKø<T>();
    Kø<T> C = new TabellKø<T>();

    B.leggInn(A.taUt());

    while (!A.tom())
    {
      T averdi = A.taUt();
      while (!B.tom() && c.compare(B.kikk(),averdi) < 0)
        C.leggInn(B.taUt());

      C.leggInn(averdi);

      while (!B.tom()) C.leggInn(B.taUt());
      Kø<T> D = B; B = C; C = D;
    }

    while (!B.tom()) A.leggInn(B.taUt());
  } 

Oppgave 15

  public static <T> void sorter(Kø<T> A, Comparator<? super T> c)
  {
    Kø<T> B = new TabellKø<T>();  // hjelpekø
    int n = A.antall();

    while (n > 0)
    {
      T min = A.kikk();

      for (int i = 0; i < n; i++)
      {
        T temp = A.taUt();
        A.leggInn(temp);
        if (c.compare(temp,min) < 0) min = temp;
      }
      for (int i = 0; i < n; i++)
      {
        T temp = A.taUt();
        if (c.compare(temp,min) == 0) B.leggInn(temp);
        else A.leggInn(temp);
      }
      n = A.antall();
    }
    while (!B.tom()) A.leggInn(B.taUt());
  } 

Oppgave 16

Starter med å lage en hjelpemetode som finner posisjonen til den største av de k første verdiene i køen. Den lages slik at køen etterpå er som den var før. Metoden bruker ingen hjelpestrukturer:

  public static <T> int maks(Kø<T> A, int k, Comparator<? super T> c)
  {
    int m = 0;
    T maksverdi = A.taUt();
    A.leggInn(maksverdi);

    for (int i = 1; i < k; i++)
    {
      T verdi = A.taUt();
      if (c.compare(verdi, maksverdi) > 0)
      {
        m = i; maksverdi = verdi;
      }
      A.leggInn(verdi);
    }
    int n = A.antall();
    for (int i = k; i < n; i++) A.leggInn(A.taUt());

    return m;
  }

Ved hjelp av denne og av metoden bytt() fra Oppgave 4c) i Avsnitt 4.2.1 (som heller ikke bruker hjelpestrukturer), kan vi sortere ved å bruke utvalgssortering. Vi finner først den største og legger den bakerst, så den neste største som vi legger nest bakerst, osv:

  public static <T> void sorter(Kø<T> A, Comparator<? super T> c)
  {
    for (int i = A.antall(); i > 0; i--)
    {
      int m = maks(A, i, c);
      bytt(A, m, i - 1);
    }
  }

Oppgave 17

public class KøStakk<T> implements Stakk<T>
{
  private Kø<T> kø, tempkø;

  public KøStakk()
  {
    kø = new TabellKø<T>();
    tempkø = new TabellKø<T>();
  }

  public void leggInn(T t)
  {
    while (!kø.tom()) tempkø.leggInn(kø.taUt());
    kø.leggInn(t);
    while (!tempkø.tom()) kø.leggInn(tempkø.taUt());
  }

  public T kikk()
  {
    if (kø.tom()) throw
      new NoSuchElementException("Køen er tom!");

    return kø.kikk();
  }

  public T taUt()
  {
    if (kø.tom()) throw
      new NoSuchElementException("Køen er tom!");

    return kø.taUt();
  }

  public int antall()
  {
    return kø.antall();
  }

  public boolean tom()
  {
    return kø.tom();
  }

  public void nullstill()
  {
    kø.nullstill();
  }

  public String toString()
  {
    return kø.toString();
  }

} // class KøStakk

Oppgave 18

public class StakkKø<T> implements Kø<T>
{
  private Stakk<T> A, B;

  public StakkKø()
  {
    A = new TabellStakk<T>();
    B = new TabellStakk<T>();
  }

  public void leggInn(T t)
  {
    A.leggInn(t);
  }

  public T kikk()
  {
    if (B.tom()) while (!A.tom()) B.leggInn(A.taUt());

    if (B.tom()) throw
      new NoSuchElementException("Køen er tom!");

    return B.kikk();
  }

  public T taUt()
  {
    if (B.tom()) while (!A.tom()) B.leggInn(A.taUt());

    if (B.tom()) throw
      new NoSuchElementException("Køen er tom!");

    return B.taUt();
  }

  public int antall()
  {
    return A.antall() + B.antall();
  }

  public boolean tom()
  {
    return A.tom() && B.tom();
  }

  public void nullstill()
  {
    A.nullstill(); B.nullstill();
  }

  public String toString()
  {
    if (A.tom()) return B.toString();

    Stakk<T> C = new TabellStakk<T>();
    while (!B.tom()) C.leggInn(B.taUt());
    while (!A.tom()) B.leggInn(A.taUt());
    while (!C.tom()) B.leggInn(C.taUt());
    return B.toString();
  }

} // class StakkKø