Stackar och köer

Stack

I en stack placeras nya data överst i stacken och data hämtas också överst i stacken. Ordningen kallas ibland LIFO ("Last In Frist Out"). Stackar används ofta i matematiska rutiner och är fundamental för den interna funktionen i datorer.

Kö

I köer placeras nya data längst bak i kön och data hämtas från början av kön. Ordningen kallas ibland FIFO ("First In First Out"). Köer används då det är viktigt att bevara ordningen på datan.

Exempel som buffer

Följande övningar visar exempel på hur stack och kö fungerar som buffrar. En buffer lagrar temporärt data. De kan bland annat användas för att kunna processa data i jämn takt trots att den inkommande datan kommer in i mer ojämn takt vid internetuppkopplingar, bränning av skivor och mycket mer. Nedanstående exempel visar principen för en sådan buffer i form av en stack och en kö.

Övning 2.16

#Simulerar en stack där 0-2 nya element tillkommer varje sekund och ett
# poppas.

import random
import time

#Fyller stacken med 6 bokstäver. A underst i stacken
stack = ["A", "B", "C", "D", "E", "F"]
alfa = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
i = 6
while True :
    try : 
        print("Processar " + stack.pop())    
        print(stack)
    except IndexError :
        print("Stacken tom! Avslutar")
        break
    
    antal_nya = random.randint(0,2)
    while antal_nya > 0 :
        stack.append(alfa[i])
        i = (i + 1) % 26
        antal_nya = antal_nya - 1
    time.sleep(1)
    
print("Slut")

Övning 2.17

#Simulerar en kö (buffer) där 0-2 nya element tillkommer varje sekund och ett
# poppas.

import random
import time

#Fyller kön med 6 bokstäver. A först i kön
queue = ["A", "B", "C", "D", "E", "F"]
alfa = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
i = 6
while True :
    try : 
        print("Processar " + queue.pop(0))    
        print(queue)
    except IndexError :
        print("Buffern tom! Avslutar")
        break
    
    antal_nya = random.randint(0,2)
    while antal_nya > 0 :
        queue.append(alfa[i])
        i = (i + 1) % 26
        antal_nya = antal_nya - 1

    time.sleep(1)
    
print("Slut")