数据结构-队列

队列

队列的节点从头部删除（出队），从尾部插入（入队）

为先进先出的数据结构

实现分2个文件： ListModule.py 和 QueueModule.py

测试为1个文件：testQueue.py

ListModule.py

  1 # ListModule.py
  2 # Classes List and Node definitions.
  3 
  4 class Node:
  5    """Single node in a data structure"""
  6 
  7    def __init__( self, data ):
  8       """Node constructor"""
  9       
 10       self._data = data
 11       self._nextNode = None
 12     
 13    def __str__( self ):
 14       """Node data representation"""
 15 
 16       return str( self._data )      
 17 
 18 class List:
 19    """Linked list"""
 20 
 21    def __init__( self ):
 22       """List constructor"""
 23 
 24       self._firstNode = None
 25       self._lastNode = None
 26 
 27    def __str__( self ):
 28       """List string representation"""
 29 
 30       if self.isEmpty():
 31          return "empty"
 32 
 33       currentNode = self._firstNode
 34       output = []
 35 
 36       while currentNode is not None:
 37          output.append( str( currentNode._data ) )
 38          currentNode = currentNode._nextNode
 39 
 40       return " ".join( output )      
 41 
 42    def insertAtFront( self, value ):
 43       """Insert node at front of list"""
 44 
 45       newNode = Node( value )
 46 
 47       if self.isEmpty():  # List is empty
 48          self._firstNode = self._lastNode = newNode
 49       else:   # List is not empty
 50          newNode._nextNode = self._firstNode
 51          self._firstNode = newNode
 52         
 53    def insertAtBack( self, value ):
 54       """Insert node at back of list"""
 55 
 56       newNode = Node( value )
 57 
 58       if self.isEmpty():  # List is empty
 59          self._firstNode = self._lastNode = newNode
 60       else:  # List is not empty
 61          self._lastNode._nextNode =  newNode
 62          self._lastNode = newNode
 63 
 64    def removeFromFront( self ):
 65       """Delete node from front of list"""
 66 
 67       if self.isEmpty():  # raise exception on empty list
 68          raise IndexError, "remove from empty list"
 69 
 70       tempNode = self._firstNode
 71 
 72       if self._firstNode is self._lastNode:  # one node in list
 73          self._firstNode = self._lastNode = None
 74       else:
 75          self._firstNode = self._firstNode._nextNode
 76 
 77       return tempNode
 78 
 79    def removeFromBack( self ):
 80       """Delete node from back of list"""
 81 
 82       if self.isEmpty():  # raise exception on empty list
 83          raise IndexError, "remove from empty list"
 84      
 85       tempNode = self._lastNode
 86 
 87       if self._firstNode is self._lastNode:  # one node in list
 88          self._firstNode = self._lastNode = None
 89       else:
 90          currentNode = self._firstNode
 91 
 92          # locate second-to-last node
 93          while currentNode._nextNode is not self._lastNode:
 94                currentNode = currentNode._nextNode
 95                
 96          currentNode._nextNode = None
 97          self._lastNode = currentNode
 98 
 99       return tempNode
100     
101    def isEmpty( self ):
102       """Returns true if List is empty"""
103 
104       return self._firstNode is None

QueueModule.py

 1 # QueueModule.py
 2 # Class Queue definition
 3 
 4 from ListModule import List
 5 
 6 class Queue( List ):
 7     """
 8     Queue composed from linked list
 9     """
10 
11     def __init__( self ):
12         """
13         Queue constructor
14         """
15         # List object data member
16         self._queueList = List()
17 
18     def __str__( self ):
19         """
20         Queue string representation
21         """
22         # call List method __str__
23         return str( self._queueList )
24 
25     def enqueue(self,element):
26         """
27         Enqueue element
28         """
29         # Method enqueue calls List method insertAtBack
30         self._queueList.insertAtBack( element )
31 
32     def dequeue(self):
33         """
34         Dequeue element
35         """
36         # Method dequeue calls List method removeFromFront
37         return self._queueList.removeFromFront()
38 
39     def isEmpty( self ):
40         """
41         Return 1 if Queue is empty
42         """
43         # call List method isEmpty
44         return self._queueList.isEmpty()

testQueue.py

 1 # testQueue.py
 2 # Driver to test Class Queue
 3 
 4 from QueueModule import Queue
 5 
 6 queue = Queue()
 7 
 8 print "Processing a queue"
 9 
10 for i in range( 4 ):
11     # Insert items in Queue object by calling method enqueue
12     queue.enqueue(i)
13     print "The queue is:",queue
14 
15 while not queue.isEmpty():
16     # Remove items from Queue object by calling method dequeue
17     dequeue = queue.dequeue()
18     print dequeue,"dequeued"
19     print "The queue is",queue