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

    Implementation with list
    1. # QueueModule.py
    2. #!/usr/bin/python3
    3. class Queue(object):
    4.     def __init__(self):
    5.         self.items = []
    6.  
    7.     def isEmpty(self):
    8.         return len(self.items) == 0
    9.  
    10.     def enqueue(self, v):
    11.         try:
    12.             self.items.insert(0,v)
    13.             return True
    14.         except Exception as e:
    15.             return False
    16.  
    17.     def dequeue(self):
    18.         try:
    19.             item = self.items.pop()
    20.             return item
    21.         except Exception as e:
    22.             return None
    23.  
    24.     def size(self):
    25.         return len(self.items)
    26.  
    27.     def front(self):
    28.         if self.size() == 0:
    29.             return None
    30.         return self.items[self.size()-1]
    31.  
    32.     def rear(self):
    33.         if self.size() == 0:
    34.             return None
    35.         return self.items[0]
    36.  
    37.     def __str__(self):
    38.         s = 'rear ->'
    39.  
    40.         output = []
    41.  
    42.         for item in self.items:
    43.             output.append(str(item))
    44.  
    45.         s += '->'.join(output)
    46.  
    47.         s += '-> front'
    48.  
    49.         return s
    50.             
    1. #!/usr/bin/python3
    2. from QueueModule import Queue
    3.  
    4. def main():
    5.     q = Queue()
    6.  
    7.     q.enqueue(4)
    8.     q.enqueue('dog')
    9.     q.enqueue(True)
    10.  
    11.     print(q) # rear ->True->dog->4-> front
    12.     print(q.size()) # 3
    13.  
    14.     print(q.dequeue()) # 4
    15.  
    16.     print(q.front()) # dog
    17.     print(q.rear()) # True
    18.  
    19. if __name__ == '__main__':
    20.     main()
    21.
    Implementation with linked list
    1. #!/usr/bin/python3
    2. """ A model containing Node class """
    3. import copy
    4.  
    5. __author__ = "Lin Chen"
    6. __version__ = "0.1"
    7.  
    8. class Node:
    9.     """Single node with double pointers pointing to its previous node and the node after it"""
    10.  
    11.     def __init__(self, data):
    12.         """Initialize a Node
    13.         
    14.         Args:
    15.             data : data saved in the node
    16.         """
    17.         self._data = data
    18.         self._prev = None
    19.         self._next = None
    20.  
    21.     @property
    22.     def data(self):
    23.         return self._data
    24.  
    25.     @data.setter
    26.     def data(self, d):
    27.         self._data = d
    28.  
    29.     @data.deleter
    30.     def data(self):
    31.         del self._data
    32.  
    33.     @property
    34.     def next(self):
    35.         return self._next
    36.  
    37.     @next.setter
    38.     def next(self, n):
    39.         self._next = n
    40.  
    41.     @next.deleter
    42.     def next(self):
    43.         del self._next
    44.  
    45.     @property
    46.     def prev(self):
    47.         return self._prev
    48.  
    49.     @prev.setter
    50.     def prev(self, n):
    51.         self._prev = n
    52.  
    53.     @prev.deleter
    54.     def prev(self):
    55.         del self._prev
    56.  
    57.     def __str__(self):
    58.         return str(self._data)
    59.
    Double Linked List
    1. #!/usr/bin/python
    2. """ A modeule containing List class"""
    3.  
    4. from NodeModule import Node
    5.  
    6. class List:
    7.     """Linked List class with a pre-defined Node class"""
    8.  
    9.     def __init__(self):
    10.         """Initialize a List
    11.         """
    12.         self._head = None
    13.         self._tail = None
    14.         self._count = 0
    15.  
    16.     def getSize(self):
    17.         """Return the size of the list
    18.         
    19.         Returns:
    20.             int : size of the list
    21.         """
    22.         return self._count
    23.  
    24.     def access(self, index):
    25.         """Access a node with its index
    26.  
    27.         Args:
    28.             index: index of a specified node
    29.  
    30.         Returns:
    31.             Node: a pointer of the specified node if the specifid node exists; None, otherwise
    32.         """
    33.         if index < 0 or index > self._count-1:
    34.             return None
    35.  
    36.         # access the front node
    37.         if index == 0:
    38.             return self._head
    39.  
    40.         # access the tail node
    41.         if index == self._count-1:
    42.             return self._tail
    43.  
    44.         if index <= self.getSize()/2: # access the first half
    45.             current = self._head
    46.             for i in range(index):
    47.                 current = current.next
    48.             return current
    49.         else: # access the second half
    50.             current = self._tail
    51.             for i in range(self.getSize()-index-1):
    52.                 current = current.prev
    53.             return current
    54.  
    55.         return None
    56.  
    57.     def insert(self, index, v):
    58.         """Insert a valude to make the list maintain ascending order
    59.  
    60.         Args:
    61.             v : data which can be saved in a node
    62.  
    63.         Returns:
    64.             Node: True, if the value is inserted succefully; False, otherwise
    65.         """
    66.         if index < 0 or index > self._count:
    67.             return False
    68.  
    69.         n = Node(v) # create a node
    70.  
    71.         # insert a node into an empty list
    72.         if self.getSize() == 0:
    73.             self._head = n
    74.             self._tail = n
    75.             self._count += 1
    76.             return True
    77.  
    78.         # insert a node in the front
    79.         if index == 0:
    80.             n.next = self._head
    81.             self._head.prev = n
    82.             self._head = n
    83.             self._count += 1
    84.             return True
    85.  
    86.         # insert a node at the end
    87.         if index == self.getSize():
    88.             n.prev = self._tail
    89.             self._tail.next = n
    90.             self._tail = n
    91.             self._count += 1
    92.             return True
    93.  
    94.         if index <= self.getSize()/2:
    95.             current = self._head
    96.             for i in range(index-1):
    97.                 current = current.next
    98.             n.next = current.next
    99.             n.prev = current
    100.             current.next.prev = n
    101.             current.next = n
    102.             self._count += 1
    103.             return True
    104.         else:
    105.             current = self._tail
    106.             for i in range(self.getSize()-index-1):
    107.                 current = current.prev
    108.             n.next = current
    109.             n.prev = current.prev
    110.             current.prev.next = n
    111.             current.prev = n
    112.             self._count += 1
    113.             return True
    114.  
    115.         return False
    116.  
    117.     def delete(self, index):
    118.         """Delete a valude located at a specific location in the list
    119.  
    120.         Args:
    121.             index (int): location of deletion, 0 is the location before the first element, 1 is the location after the first element
    122.  
    123.         Returns:
    124.             boolean: the value of removed node, if the node is deleted succefully; None, otherwise
    125.         """
    126.         if index < 0 or index > self._count-1:
    127.             return None
    128.  
    129.         if index == 0:
    130.             n = self._head
    131.             self._head = self._head.next
    132.             self._head.prev = None
    133.             self._count -= 1
    134.             return n
    135.  
    136.         if index == self._count-1:
    137.             n = self._tail
    138.             self._tail = self._tail.prev
    139.             self._tail.next = None
    140.             self._count -= 1
    141.             return n
    142.  
    143.         if index <= self._count/2:
    144.             current = self._head
    145.             for i in range(index-1):
    146.                 current = current.next
    147.             n = current.next
    148.             current.next = current.next.next
    149.             current.next.prev = current
    150.             self._count -= 1
    151.             return n
    152.         else:
    153.             current = self._tail
    154.             for i in range(self.getSize()-index-2):
    155.                 current = current.prev
    156.             n = current.prev
    157.             current.prev = current.prev.prev
    158.             current.prev.next = current
    159.             self._count -= 1
    160.             return n
    161.  
    162.         return None
    163.  
    164.     def __str__(self):
    165.         """Convert the list to a string
    166.  
    167.         Returns:
    168.             string : a string represents the list
    169.         """
    170.         if self.getSize() == 0:
    171.             return "Empty"
    172.  
    173.         current = self._head
    174.         output = []
    175.  
    176.         while current is not None:
    177.             output.append(str(current))
    178.             current = current.next
    179.  
    180.         return " -> ".join(output)
    181.
    Queue
    1. #!/usr/bin/python
    2.  
    3. from ListModule import List
    4.  
    5. class Queue(List):
    6.     def __init__(self):
    7.         List.__init__(self)
    8.  
    9.     def enqueue(self, v):
    10.         """insert element at the tail
    11.  
    12.         Args:
    13.             v : data which can be saved in a node
    14.  
    15.         Returns:
    16.             boolean: True, if the value is inserted succefully; False, otherwise
    17.         """
    18.         return self.insert(self.getSize(), v)
    19.  
    20.     def dequeue(self):
    21.         """delete a node from the front
    22.  
    23.         Args:
    24.             index (int): location of deletion, 0 is the location before the first element, 1 is the location after the first element
    25.  
    26.         Returns:
    27.             Node: a pointer of the delete node if the queue is not empty; None, otherwise
    28.         """
    29.         return self.delete(0)
    30.  
    31.     def front(self):
    32.         """access the first node in the queue
    33.  
    34.         Returns:
    35.             Node: a pointer of the first node if the queue is not empty; None, otherwise
    36.         """
    37.         return self.access(0)
    38.  
    39.     def rear(self):
    40.         """access the tail node in the queue
    41.  
    42.         Returns:
    43.             Node: a pointer of the tail node if the queue is not empty; Noen, otherwise
    44.         """
    45.         return self.access(self._count-1)
    46.
    Test
    1. #!/usr/bin/python
    2.  
    3. from QueueModule import Queue
    4.  
    5. def main():
    6.     q = Queue()
    7.  
    8.     # enqueue
    9.     q.enqueue(10)
    10.     q.enqueue(20)
    11.     q.enqueue(15)
    12.     q.enqueue(30)
    13.     q.enqueue(40)
    14.     print(q)
    15.  
    16.     # front
    17.     print(q.front().data)
    18.  
    19.     # rear
    20.     print(q.rear().data)
    21.  
    22.     # dequeue
    23.     n = q.dequeue() # 10
    24.     print(n.data) # the value of remove node
    25.     print(q)
    26.  
    27. if __name__ == '__main__':
    28.     main()
    29.
    Queue Sample
  • A operating system
  • E-mail system