Kö
En kö är en datastruktur som efterliknar en klassisk kö. Man kallar det ibland för FIFO (first-in first-out).
Som en kö i matsalen
Man ställer sig i kön, väntar. I andra änden har folk "kommit fram" och blir servade.Enqueue och dequeue
Det finns 2 operationer i en kö, dels ställer man sig i kön (Enqueue) och där står man vanligtvis en lång stund. I andra änden blir folk servade (dequeue). Så dels ökar kön där bak och dels minskar den där fram.
Enqueue
Enqueue fyller på kön där bak. Ju mer kön fylls på desto fler element finns kön. Man kan skapa en enkel kö med en lista och låta append agera enqueue. Det är ju vad append gör, lägger till element på slutet.queue = []
queue.append(10)
print(queue)
queue.append(15)
print(queue)
queue.append(6)
print(queue)
Dequeue
Vi kan enkelt implementera dequeue med pop(0). Det är viktigt att vi skickar in argument 0 i pop, annars kommer pop popp:a listan från slutet - dvs vi får en stack snarare än en kö.queue = []
queue.append(10)
print(queue)
queue.append(15)
print(queue)
queue.append(6)
print(queue)
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))
Du ser att den som stått längst i kön är den som kommer ut först, eller hur? Dvs, det fungerar exakt som en kö!
Vi kan enkelt implementera peek genom att titta på element 0, dvs queue[0].
Peek
Peek kommer du kanske ihåg från stacken. Peek finns även i en kö och berättar vilket värde som finns längst fram i kön - utan att bekäna det. Lite som kön utanför krogen där dörrvakten inspekterar dig, men släpper inte in dig.Vi kan enkelt implementera peek genom att titta på element 0, dvs queue[0].
queue = []
queue.append(10)
print(queue)
queue.append(15)
print(queue)
queue.append(6)
print(queue)
print(queue[0])
print(queue.pop(0))
print(queue[0])
print(queue.pop(0))
print(queue.pop(0))
Används till?
Typiska kösystem
Printerspooler, schemaläggning av processer, nätverksprotokoll. Överallt där saker skall utföras enligt FIFO -koncept (first-in first-out), dvs en kö.
Bredden först
Inom sökalgoritmer används kö för att implementera att bredden söks innan djupet.
Skapa en kö
Säg, att vi skulle skapa en kö som en class. Vi kan då bygga en "överrock" på vår lista så att den blir lite mer officiell och representativ.__init___
Init (klassens konstruktor) initierar själva klassen, i detta fall sätter den en lista att vara tom från början.
__len___
Tack vare len kan vi kolla storleken på kön. Det kan ibland vara intressant veta om kön är tom.
__str___
Med str kan vi skriva ut kön.
enqueue
Enqueue gör helt enkelt append på vår lista, vilket är samma sak. Man vill dock att det skall heta enqueue (lägg till i kön).
dequeue
Dequeue plockar senast append:ade objekt. Vi använder funktionen pop som redan finns på listan. Pop går att anropa med ett argument och detta vill vi utnyttja. Med argumentet 0 kommer pop(0) plocka bort första elementet i listan, dvs det som lades dit först.
peek
Peek smygtittar på senaste elementet. Det är käckt med python eftersom vi kan läsa en lista bakifrån, för att läsa sist ditlagda element.
class Queue:
def __init__(self):
self.lst = []
def __len__(self):
return(len(self.lst))
def __str__(self):
return(str(self.lst))
def enqueue(self,obj):
self.lst.append(obj)
def dequeue(self):
return self.lst.pop(0)
def peek(self):
if(len(self.lst)==0):
return None
else:
return(self.lst[0])
queue = Queue()
print(queue)
queue.enqueue(10)
print(queue)
queue.enqueue(20)
print(queue)
queue.enqueue(3.14)
print(queue)
print("Köns storlek=",len(queue))
print(queue.peek())
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())
print("Köns storlek=",len(queue))
print(queue.peek())