AuK/Konkrete Datenstrukturen/Queue
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Python</language>
Ein ADT Queue (Warteschlange) ist dem Stack ähnlich. Hier gibt es ebenso die Operationen
'' zur Instanziierung einer Queue,
'' zum Hinzufügen (enqueue) eines neuen Elements (am Ende: rear) und
'' 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. 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.
<run id="5f3715574f202">
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())
</run>
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.
<run id="5f3715574f28d">
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())
</run>