Queue

Aus ProgrammingWiki

Ein ADT Queue (Warteschlange) ist dem Stack ähnlich. Hier gibt es ebenso die Operationen

1. zur Instanziierung einer Queue,
2. zum Hinzufügen (enqueue) eines neuen Elements (am Ende: rear) und
3. zum Entfernen (dequeue) des nächsten Elements (am Anfang: front).

Im Gegensatz zum Stack (LIFO) handelt es sich bei einer Queue um eine First-In-First-Out-(FIFO)-Datenstruktur. D.h. die Elemente, die zuerst mit der enqueue-Operation am Ende (rear, tail) der Queue hinzugefügt wurden, werden auch die sein, die zuerst mit der dequeue-Operation am Anfang (head) entfernt werden - so wie man das von einer Warteschlange erwartet.

Eine Queue kann mit einer Doubly Linked List implementiert werden. Da man bei einer Queue sehr häufig Elemente am Ende anfügt und am Anfang entfernt, ist eine flexible Listen-Datenstruktur, wie eben die Linked List, sehr zu empfehlen. Neben der Verwendung einer Doubly Linked List kann auch eine Singly Linked List, für die wir je einen Zeiger auf das aktuell erste bzw. letzte Element speichern, Verwendung finden. Einfügen und entfernen eines Elements können in konstanter Zeit, d.h. in $\mathcal{O}(1)$, erfolgen.

Nun ist es relativ einfach eine Queue mit Singly Linked List zu implementieren. Bei der enqueue-Operation muss man ein neues Node anlegen, dessen Pointer auf das bisher erste Element setzen und den head der Queue entsprechend anpassen. Bei der dequeue-Operation wird das letzte Element entfernt und der Pointer des vorherigen Nodes auf null gesetzt. Außerdem wird der rear*-Pointer nun auf das bisher vorletzte und aktuell letzte Node gesetzt.

class Node: def __init__(self, data): self.data = data self.next = None class Queue: def __init__(self): self.front = self.rear = None def isEmpty(self): return self.front == None # Method to add an item to the queue def EnQueue(self, item): temp = Node(item) if self.rear == None: self.front = self.rear = temp return # gibt False zurück self.rear.next = temp self.rear = temp # Method to remove an item from queue def DeQueue(self): if self.isEmpty(): return temp = self.front self.front = temp.next if(self.front == None): self.rear = None return str(temp.data)

q = Queue() q.EnQueue(10) q.EnQueue(20) q.DeQueue() q.DeQueue() q.EnQueue(30) q.EnQueue(40) q.EnQueue(50) print("Dequeued item is " + q.DeQueue())

ausführen

Für die Queue können wir die Doubly-Linked List, die wir oben implementiert haben, nutzen. Im Unterschied zu obiger Beschreibung der Operationen `enqueue` und `dequeue` werden neue Elemente vorn (front) hinzugefügt und hinten (rear) entfernt. Auf diese Weise wird nicht nur FIFO umgesetzt, sondern auch eine Bewegung der Warteschlange im Speicher bei vielen `enqueue`- und `dequeue`-Operationen vermieden. Man kann sich den Speicher dann auch zyklisch (Kreisstruktur) vorstellen.

class DoublyNode: def __init__(self): self.value = None self.next = None self.prev = None # prev Pointer is required in Doubly Linked List def add(self, value, index): # using prev node as parameter to be able to set prev pointer if index > 1 and self.next is not None: return self.next.add(value, index - 1) elif index == 1: new_node = DoublyNode() new_node.value = value new_node.next = self.next new_node.prev = self self.next.prev = new_node self.next = new_node return True return False def add_from_tail(self, value, index): if index > 1 and self.prev is not None: return self.prev.add_from_tail(value, index - 1) elif index == 1: new_node = DoublyNode() new_node.value = value new_node.next = self new_node.prev = self.prev self.prev.next = new_node self.prev = new_node return True return False def remove(self, index): if index > 0 and self.next is not None: return self.next.remove(index - 1) elif index == 0: self.prev.next = self.next self.next.prev = self.prev return True return False def remove_from_tail(self, index): if index > 0 and self.prev is not None: return self.prev.remove_from_tail(index - 1) elif index == 0: self.next.prev = self.prev self.prev.next = self.next return True return False class DoublyLinkedList: def __init__(self): node = DoublyNode() self.head = node self.tail = node # tail pointer exist to access from end of list self.length = 0 def add(self, value, index=None): if index is None: index = self.length if index == 0 and self.length == 0: self.head.value = value self.length += 1 elif index == 0: new_node = DoublyNode() new_node.value = value new_node.next = self.head new_node.prev = None self.head.prev = new_node self.head = new_node self.length += 1 elif 0 < index < self.length: if self.head.add(value, index): self.length += 1 elif index == self.length: self.add_from_tail(value, 0) def add_from_tail(self, value, index): if index == 0 and self.length == 0: self.tail.value = value self.length += 1 elif index == 0: new_node = DoublyNode() new_node.value = value new_node.next = None new_node.prev = self.tail self.tail.next = new_node self.tail = new_node self.length += 1 elif 0 < index < self.length: if self.tail.add_from_tail(value, index): self.length += 1 elif index == self.length: self.add(value, 0) def remove(self, index): if index >= self.length: return None if index == 0 and self.length == 1: self.head.value = None self.length -= 1 elif index == 0: self.head.next.prev = None self.head = self.head.next self.length -= 1 elif 0 < index < self.length - 1: if self.head.remove(index): self.length -= 1 elif index == self.length - 1: self.remove_from_tail(0) def remove_from_tail(self, index): if index >= self.length: return None if index == 0 and self.length == 1: self.tail.value = None self.length -= 1 elif index == 0: self.tail.prev.next = None self.tail = self.tail.prev self.length -= 1 elif 0 < index < self.length - 1: if self.tail.remove_from_tail(index): self.length -= 1 elif index == self.length - 1: self.remove(0) def print_lst(self): node = self.head for i in range(self.length - 1): print('{0}, '.format(node.value), end='') node = node.next print(node.value) class Queue: def __init__(self): self.lst = DoublyLinkedList() def enqueue(self, value): self.lst.add(value, 0) def dequeue(self): value = self.lst.tail.value self.lst.remove_from_tail(0) return value

queue = Queue() queue.enqueue(4) queue.enqueue(3) queue.enqueue(-1) print(queue.dequeue()) print(queue.dequeue()) print(queue.dequeue())

ausführen