Nada

Föreläsning 7: Stackar och köer

Länkad lista

En länkad lista består av poster av den här typen.
 
class Node     {
  int tal      ;
  Node next    ;}
Den ritas som en rad av lådor där varje låda innehåller ett tal och en pekare till nästa låda. Den sista lådan pekar inte på någonting och det åstadkommer man genom att sätta next=null.

Listan har skapats genom upprepade p=new Node() i programmet, där p är deklarerad som Node p. För att komma åt den länkade listan måste man åtminstone ha en pekare kvar på den första lådan. Beroende på hur man ritar listan kallas den pekaren top, first eller front. Just nu tänker vi oss lådraden som vertikal och använder därför top. Den första posten i listan kan vi skapa så här.

 
  Node top        ;
  top = new Node();
  top.tal = 17    ;
  top.next= null  ;
Hur dom övriga posterna skapas väntar vi med ett tag. Först måste vi nämligen bestämma oss för om nya poster ska läggas in först i listan eller sist i listan.

Stack och kö

En lista där en ny post läggs in ovanpå listan kallas för stack; en lista där nya poster läggs in sist kallas . I båda fallen gäller att om man ska ta ut en post ur listan, så är det den första som tas ut. En tallrikstrave på en lunchservering är exempel på en stack, en kundkö på posten är exempel på en kö. Eftersom stackar används ständigt i datavärlden har det utbildats en standard för vilka anrop man kan göra till en stack. När man vill lägga elementet x på stacken gör man anropet push(x), när man vill ta bort översta elementet heter det y=pop() och så flyttas elementet in i variabeln y i stället. Weiss skriver i stället y=topAndPop(), men tills vidare kör vi med den kortare och vanligare benämningen.

Insättning sist i en kö kan heta enqueue(x) och utplockning av första elementet kan heta y=dequeue(). I stället för dessa ovanliga ord används också put och get, särskilt om kön ligger som en särskild class Queue. Då ser det alltså ut som Queue.put(x) och y=Queue.get().

Både för stack och kö kan det finnas ytterligare anrop definierade. Viktigast är den booleska metoden empty, alltså till exempel

    if (Stack.empty()) Stack.push(4711);
    while (!Queue.empty()) System.out.print(Queue.get());   
Nu närmast ska vi skriva en metod Stack.show() som skriver ut stackens innehåll på skärmen (utan att förstöra stacken).

Att gå igenom lista

Sätt ett pekfinger på översta posten, skriv ut talet i posten på skärmen, flytta pekfingret till nästa post, skriv ut talet etc. Sluta när pekfingret pekar ut i tomma intet.
 
  void show()                                              {
    Node p = top                                           ;
    while(p!=null)                                         {
      System.out.print(p.tal+" ")                          ;
      p=p.next                                             ;}}
Varför behövs hjälppekaren p? Följande kod skriver också ut stacken, men efteråt är inte stacken sej lik!
 
  void show()                                              {
    while(top!=null)                                       {
      System.out.print(top.tal+" ")                        ;
      top=top.next                                         ;}}

Att ta bort en post ur listan

Den första posten tas lätt bort ur listan med satsen top=top.next; Vi vill att anropet pop() ska returnera det tal top.tal som fanns i den borttagna posten och därför är det bäst att kopiera över det i variabeln x innan man tar bort posten.
 
  int pop()                                                {
    int x = top.tal                                        ;
    top=top.next                                           ;
    return x                                               ;}
Om stacken är tom, dvs top är null, kommer uttrycket top.tal att ge felavbrott. Därför är det bäst att vara säker på att stacken inte är tom innan man anropar pop().

Att sätta in en post i listan

En ny post med talet x i skapas med
 
    p = new Node();
    p.tal=x       ;
Om den ska läggas på en stack behövs följande satser.
 
    p.next=top    ;
    top = p       ;
Om den ska in sist i en kö ser det oftast ut så här.
 
    p.next=null   ;
    back.next=p   ;
    back=back.next;
Men om kön är tom kan man inte skriva back.next, och då gör man i stället så här.
 
    p.next=null   ;
    front=p       ;
    back=p        ;

En abstrakt heltalsstack

Här har vi lagt alla stackmetoderna i en klass IntStack. Eftersom vi inte skrivit något static före metoderna måste man först skapa ett stackobjekt innan man kan anropa dom. Exempel:
 
    IntStack stacken = new IntStack()                      ;
    stacken.push(17)                                       ;
    stacken.show()                                         ;
    if(!stacken.empty())  x=stacken.pop()                  ;
Och så här ser klassen ut. Lägg märke till att pekaren top är private, så man kan inte skriva stacken.top.
 
class Node                                                 {
  int tal                                                  ;
  Node next                                                ;}
class IntStack                                             {
  private Node top=null                                    ;
  void push(int x)                                         {
    Node p = new Node()                                    ;
    p.tal=x                                                ;
    p.next=top                                             ;
    top = p                                                ;}
  int pop()                                                {
    int x = top.tal                                        ;
    top=top.next                                           ;
    return x                                               ;}
  boolean empty()                                          {
    return (top==null)                                     ;}
  void show()                                              {
    Node p = top                                           ;
    while(p!=null)                                         {
      System.out.print(p.tal+" ")                          ;
      p=p.next                                             ;}}}

Sidansvarig: <henrik@nada.kth.se>
Senast ändrad 14 mars 2000
Tekniskt stöd: <webmaster@nada.kth.se>