Oppgave 1 - 5

Her ligger hele klassen LenketStakk<T>:

import java.util.*;

public class LenketStakk<T> implements Stakk<T>
{
  private static final class Node<T>     // en indre nodeklasse
  {
    T verdi;
    Node<T> neste;

    Node(T verdi, Node<T> neste)    // nodekonstruktør
    {
      this.verdi = verdi;
      this.neste = neste;
    }

  } // class Node

  private Node<T> hode;         // stakkens topp
  private int antall;           // antall på stakken

  public LenketStakk()       // konstruktør
  {
    hode = null;
    antall = 0;
  }

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

  @Override
  public T kikk()
  {
    if (antall == 0)
      throw new NoSuchElementException("Stakken er tom!");
    return hode.verdi;
  }

  @Override
  public T taUt()
  {
    if (antall == 0)
      throw new NoSuchElementException("Stakken er tom!");

    T temp = hode.verdi;
    hode = hode.neste;
    antall--;

    return temp;
  }

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

  @Override
  public int antall()
  {
    return antall;
  }

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

  @Override
  public String toString()
  {
    if (tom()) return "[]";

    StringBuilder s = new StringBuilder();

    Node<T> p = hode;
    s.append('['); s.append(p.verdi);

    p = p.neste;
    while (p != null)
    {
      s.append(','); s.append(' '); s.append(p.verdi);
      p = p.neste;
    }
    s.append(']');

    return s.toString();
  }

} // class LenketStakk

Oppgave 6

Det kan se ut som TabellStakk er en god del mer effektiv enn LenketStakk. Da undertegnede brukte en en 2.80GHz Intel Pentium med Windows XP og Java 1.6, tok det 3,3 sekunder med LenketStakk, men bare 0,8 sekunder med TabellStakk.

Oppgave 7

Tidene for Stack, ArrayDeque og LinkedList ble henholdsvis 1,9, 0,8 og 4,7 sekunder. Det betyr at ArrayDeque er den beste å bruke når en trenger en stakk.