Queue
Queue is a linear structure, the order is First In First Out (FIFO)
Operations
enqueue(), insert element at the tail
dequeue(), delete element at the head
front(), return element at head
rear(), return element at rear
Implementation with array
Node
#!/usr/bin/python
""" A model containing Node class """
import copy
__author__ = "Lin Chen"
__version__ = "0.1"
class Node:
"""Single node with double pointers pointing to its previous node and the node after it"""
def __init__(self, data):
"""Initialize a Node
Args:
data : data saved in the node
"""
self._data = data
self._prev = None
self._next = None
@property
def data(self):
return self._data
@data.setter
def data(self, d):
self._data = d
@data.deleter
def data(self):
del self._data
@property
def next(self):
return self._next
@next.setter
def next(self, n):
self._next = n
@next.deleter
def next(self):
del self._next
@property
def prev(self):
return self._prev
@prev.setter
def prev(self, n):
self._prev = n
@prev.deleter
def prev(self):
del self._prev
def __str__(self):
return str(self._data)
Double Linked List
#!/usr/bin/python
""" A modeule containing List class"""
from NodeModule import Node
class List:
"""Linked List class with a pre-defined Node class"""
def __init__(self):
"""Initialize a List
"""
self._head = None
self._tail = None
self._count = 0
def getSize(self):
"""Return the size of the list
Returns:
int : size of the list
"""
return self._count
def access(self, index):
"""Access a node with its index
Args:
index: index of a specified node
Returns:
Node: a pointer of the specified node if the specifid node exists; None, otherwise
"""
if index < 0 or index > self._count-1:
return None
# access the front node
if index == 0:
return self._head
# access the tail node
if index == self._count-1:
return self._tail
if index <= self.getSize()/2: # access the first half
current = self._head
for i in range(index):
current = current.next
return current
else: # access the second half
current = self._tail
for i in range(self.getSize()-index-1):
current = current.prev
return current
return None
def insert(self, index, v):
"""Insert a valude to make the list maintain ascending order
Args:
v : data which can be saved in a node
Returns:
Node: True, if the value is inserted succefully; False, otherwise
"""
if index < 0 or index > self._count:
return False
n = Node(v) # create a node
# insert a node into an empty list
if self.getSize() == 0:
self._head = n
self._tail = n
self._count += 1
return True
# insert a node in the front
if index == 0:
n.next = self._head
self._head.prev = n
self._head = n
self._count += 1
return True
# insert a node at the end
if index == self.getSize():
n.prev = self._tail
self._tail.next = n
self._tail = n
self._count += 1
return True
if index <= self.getSize()/2:
current = self._head
for i in range(index-1):
current = current.next
n.next = current.next
n.prev = current
current.next.prev = n
current.next = n
self._count += 1
return True
else:
current = self._tail
for i in range(self.getSize()-index-1):
current = current.prev
n.next = current
n.prev = current.prev
current.prev.next = n
current.prev = n
self._count += 1
return True
return False
def delete(self, index):
"""Delete a valude located at a specific location in the list
Args:
index (int): location of deletion, 0 is the location before the first element, 1 is the location after the first element
Returns:
boolean: the value of removed node, if the node is deleted succefully; None, otherwise
"""
if index < 0 or index > self._count-1:
return None
if index == 0:
n = self._head
self._head = self._head.next
self._head.prev = None
self._count -= 1
return n
if index == self._count-1:
n = self._tail
self._tail = self._tail.prev
self._tail.next = None
self._count -= 1
return n
if index <= self._count/2:
current = self._head
for i in range(index-1):
current = current.next
n = current.next
current.next = current.next.next
current.next.prev = current
self._count -= 1
return n
else:
current = self._tail
for i in range(self.getSize()-index-2):
current = current.prev
n = current.prev
current.prev = current.prev.prev
current.prev.next = current
self._count -= 1
return n
return None
def __str__(self):
"""Convert the list to a string
Returns:
string : a string represents the list
"""
if self.getSize() == 0:
return "Empty"
current = self._head
output = []
while current is not None:
output.append(str(current))
current = current.next
return " -> ".join(output)
Queue
#!/usr/bin/python
from ListModule import List
class Queue(List):
def __init__(self):
List.__init__(self)
def enqueue(self, v):
"""insert element at the tail
Args:
v : data which can be saved in a node
Returns:
boolean: True, if the value is inserted succefully; False, otherwise
"""
return self.insert(self.getSize(), v)
def dequeue(self):
"""delete a node from the front
Args:
index (int): location of deletion, 0 is the location before the first element, 1 is the location after the first element
Returns:
Node: a pointer of the delete node if the queue is not empty; None, otherwise
"""
return self.delete(0)
def front(self):
"""access the first node in the queue
Returns:
Node: a pointer of the first node if the queue is not empty; None, otherwise
"""
return self.access(0)
def rear(self):
"""access the tail node in the queue
Returns:
Node: a pointer of the tail node if the queue is not empty; Noen, otherwise
"""
return self.access(self._count-1)
Test
#!/usr/bin/python
from QueueModule import Queue
def main():
q = Queue()
# enqueue
q.enqueue(10)
q.enqueue(20)
q.enqueue(15)
q.enqueue(30)
q.enqueue(40)
print(q)
# front
print(q.front().data)
# rear
print(q.rear().data)
# dequeue
n = q.dequeue() # 10
print(n.data) # the value of remove node
print(q)
if __name__ == '__main__':
main()
Queue Sample
A operating system
E-mail system
