Python 使用list实现无边际优先队列 (基于class, 包含迭代器)

Python 使用list实现无边际优先队列 (基于class, 包含迭代器)

#!/usr/bin/python 
# -*- coding: utf-8 -*-

'''
Created on 2015-2-4
@author: beyondzhou
@name: test_listpriorityqueue.py
'''

def test_listpriorityqueue():
    
    # import pyListQueue
    from myqueue import ListPriorityQueue
    
    print '#Init a queue named smith using enqueue'
    smith = ListPriorityQueue()
    smith.enqueue('purple', 5)
    smith.enqueue('black', 1)
    smith.enqueue('orange', 3)
    smith.enqueue('white', 0)
    smith.enqueue('green', 1)
    smith.enqueue('yellow', 5)    
    
    print '
#output smith queue'
    for element in smith:
        print element
           
    print '
#dequeue one item'
    smith.dequeue()
    
    print '
#output smith after dequeue'
    for element in smith:
        print element 
        
    print '
#dequeue another item'
    smith.dequeue()
    
    print '
#output smith after dequeue another item'
    for element in smith:
        print element 
        
    print '
#get the length of queue'
    print 'the lenght of queue is ', len(smith)
    
    print '
#check wheter the queue is empty'
    if smith.isEmpty():
        print 'stack is empty!'
    else:
        print 'stack is not empty!'
        
    print '
#dequeue all items'
    while not smith.isEmpty():
        smith.dequeue()
    
    print '
#check wheter the queue is empty after dequeue all items'
    if smith.isEmpty():
        print 'stack is empty!'
    else:
        print 'stack is not empty!'
    
if __name__ == __main__:
    test_listpriorityqueue()

# Implementation of the unbounded Priority Queue ADT using a Python list
# with new items appended to the end
class ListPriorityQueue:
    # Create an empty unbounded priority queue
    def __init__(self):
        self._qList = list()

    # Returns True if the queue is empty
    def isEmpty(self):
        return len(self) == 0

    # Returns the number of items in the queue
    def __len__(self):
        return len(self._qList)

    # Adds the given item to the queue
    def enqueue(self, item, priority):
        # Create a new instance of the storage class and append it to the list
        entry = _ListPriorityQEntry(item, priority)
        self._qList.append(entry)

    # Removes and returns the first item in the queue
    def dequeue(self):
        assert not self.isEmpty(), Cannot dequeue from an empty queue.
        
        # Find the entry with the highest priority
        highest = self._qList[0].priority
        index = 0
        for i in range(self.__len__()):
            # See if the ith entry contains a higher priority (smaller integer).
            if self._qList[i].priority < highest:
                highest = self._qList[i].priority
                index = i
                
        # Remove the entry with the highest priority and return the item
        entry = self._qList.pop(index)
            
        return entry.item

    # Returns the array queue's iterator for traversing the elements
    def __iter__(self):
        return _ListPriorityQueueIterator(self._qList)

# Private storage class for associating queue items with their priority
class _ListPriorityQEntry(object):
    def __init__(self, item, priority):
        self.item = item
        self.priority = priority

# Implementation of iter
class _ListPriorityQueueIterator:
    def __init__(self, theList):
        self._setItems = theList
        self._curItem = 0
    def __iter__(self):
        return self
    def next(self):
        if self._curItem < len(self._setItems):
            item = self._setItems[self._curItem]
            self._curItem += 1
            return item.item, item.priority
        else:
            raise StopIteration

#Init a queue named smith using enqueue

#output smith queue
('purple', 5)
('black', 1)
('orange', 3)
('white', 0)
('green', 1)
('yellow', 5)

#dequeue one item

#output smith after dequeue
('purple', 5)
('black', 1)
('orange', 3)
('green', 1)
('yellow', 5)www.Bkjia.com

#dequeue another item

#output smith after dequeue another item
('purple', 5)
('orange', 3)
('green', 1)
('yellow', 5)

#get the length of queue
the lenght of queue is  4

#check wheter the queue is empty
stack is not empty!

#dequeue all items

#check wheter the queue is empty after dequeue all items
stack is empty!