F4 Länkade listor, köer stackar

Med en nodklass kan vi skapa datastrukturen länkad lista.

class Nod:
   def __init__(self, data, next = None):
      self.data = data
      self.next = None

Exempel på tentatal som man löser genom att rita rad för rad hur minnet ändras.

p = Nod(1)
p.next = Nod(2)
q = Nod(3)
q.next = Nod(4, p)
q.next.next = q
p = None

Noder som inte pekas på städas i python bort av skräpsamlaren men i C måste man manuellt ta bort dem för att frigöra minne.

Här finns en intraktiv animation på hur man kan rita en länkad lista Links to an external site.

En stack fungerar som en tallrikshög. Det man stoppade dit sist plockar man ut först. I den engelska litteraturen en LIFO-struktur (Last In First Out). Gränssnittet till en stack är operationerna/metoderna:

• push(x): Lägg x överst på stacken.
• x = pop(): Plocka ut och returnera det som ligger överst.
• isEmpty(): Undersök om stacken är tom.

En stack kan implementeras med en enkellänkad lista på följande sätt

class Stack:

   def __init__(self):
      self.top = None

#  Lägger x överst på stacken 
   def push(self,x):
      ny = Node(x)
      ny.next = self.top
      self.top = ny

#  Plockar ut och returnerar det översta elementet 
   def pop(self):
      x = self.top.data
      self.top = self.top.next
      return x

#  Returnerar True om stacken är tom, False annars
   def isEmpty(self):
      if self.top == None: 
	 return True
      else: 
	 return False

class Node:
   def __init__(self, x, next = None):
      self.data = x
      self.next = next

Oftast implementas en stack med en vektor/lista/array

En kö är en FIFO-struktur (First In First Out) med följande gränssnitt

• enqueue(x): Stoppa in x sist i kön.
• x = dequeue(): Plocka ut och returnera det som står först i kön.
• isEmpty(): Undersök om kön är tom.

I labb d1 ska ni implementera och använda en kö för att förbereda en kortkonst. En kö kan t ex användas för att hantera skrivarköer. Den som först begärde utskrift ska också få ut sin utskrift först.

class Queue:

    def __init__(self): 
       self.first = None
       self.last = None

    def enqueue(self,x):
        ny = Node(x)
        if self.first == None:  # Om kön är tom blir det på ett sätt...
          - - -                 # ...som du får tänka ut själv.
        else:                   # Annars blir det på ett annat sätt..
          - - -                 # ...som du också får lura ut själv.

    def dequeue(self):
        - - -

    def isEmpty(self):
        - - -

En specialvariant på kö är dequeue (double-ended queue) där man kan lägga till både i början och slutet.

• addFront(x): Lägg in x först.
• addRear(x): Lägg in x sist.
• x = removeFront(): Plocka ut och returnera det som ligger först.
• x = removeRear(): Plocka ut och returnera det som ligger sist.
• isEmpty(): Undersök om dequen är tom.

När influensavaccinet anländer till vårdcentralen bildas en lång kö utanför av folk som vill bli vaccinerade.

Syster Maud inser att vaccinet inte kommer att räcka till alla och ser att många i början av kön är unga och friska. Hon tror att dom som är i minst behov av vaccination hamnat först (dom sprang snabbast). Hon vill se till att personer som är 65 eller äldre vaccineras först. Hur ska hon göra?

Skriv programmet MaudVaccinerar.py som läser filen patienter.txt av typen

Usain 29
Annegret 65
Stanislawa 104
Frankie 47
Inge 74

och skriver ut alla under 65 först.

Yngre måste tillfälligt läggas i ett förvaringsutrymme medan filen läses igenom, till exempel i en stack. Man lägger ett objekt på stacken med anropet push(p) och man hämtar ett objekt från stacken med p = pop().

Algoritm

1. Skapa en tom stack
2. Öppna filen
3. För varje patient i filen:
   • Om patienten är yngre än 65:
     • Pusha hen på stacken
   • annars:
     • Vaccinera
4. Nu är filen genomläst. Så länge stacken inte är tom:
   • Poppa ett element ur stacken
   • Vaccinera

from stack import Stack

class Patient:

   def __init__(self, namn, ålder):
      self.namn = namn
      self.ålder = int(ålder)

   def __str__(self):
      return self.namn + " " + str(self.ålder) + " år"

def main():
   korridor = Stack()
   with open("patienter.txt", encoding = "utf8") as register:
      for rad in register:
	 lista = rad.split()
	 namn = lista[0]
	 ålder = lista[1]
	 p = Patient(namn, ålder)
	 if p.ålder < 65:
	    korridor.push(p)            
	 else: 
	    print("Vaccinerar:", p)

   print("Om vi hinner tar vi också: ")
   while not korridor.isEmpty():       
      p = korridor.pop()             
      print("\t", p)

main()

Här har vi programmerat abstrakt, som om push och pop vore fungerande metoder. Stackimplementationen kommer lite senare!

I vilken ordning kommer personerna ut?

I C behöver vi en definiera en ny typ för vår node

struct Node {
   int data;
   struct Node * next;
};
typedef struct Node Nod

Man kan inte ha medlemsfunktioner/meetoder i structen utan de ligger utanför som fristående funktioner. Gränssnittet för t.ex. stack är i princip detsamma som i python men man måste även ange vilken lista man vill lägga till element. Dessutom måste man ange typerna på parametrarna men mer om det senare.

• push(s, x): Lägg x överst på stacken s
• x = pop(s): Plocka ut och returnera det som ligger överst i stacken s
• isEmpty(s): Undersök om stacken s är tom.