#!/usr/bin/python
# -*- coding: utf-8 -*-
'''
Created on 2015-2-3
@author: beyondzhou
@name: test_linklistqueue.py
'''
def test_linklistqueue():
# import pyListQueue
from myqueue import linkListQueue
print '#Init a queue named smith using enqueue'
smith = linkListQueue()
smith.enqueue('CSCI-112')
smith.enqueue('MATH-121')
smith.enqueue('HIST-340')
smith.enqueue('ECON-101')
print '\n#output smith queue'
for element in smith:
print element
print '\n#dequeue one item'
smith.dequeue()
print '\n#output smith after dequeue'
for element in smith:
print element
smith.enqueue('ECON-102')
print '\n#output smith after enqueue again'
for element in smith:
print element
print '\n#get the length of queue'
print 'the lenght of queue is ', len(smith)
print '\n#check wheter the queue is empty'
if smith.isEmpty():
print 'queue is empty!'
else:
print 'queue is not empty!'
print '\n#dequeue all items'
while not smith.isEmpty():
smith.dequeue()
print '\n#check wheter the queue is empty after dequeue all items'
if smith.isEmpty():
print 'queue is empty!'
else:
print 'queue is not empty!'
print '\n#init again'
smith.enqueue('CSCI-112')
smith.enqueue('MATH-121')
smith.enqueue('HIST-340')
smith.enqueue('ECON-101')
print '\n#output smith queue'
for element in smith:
print element
if __name__ == "__main__":
test_linklistqueue()# Implementation of the Queue ADT using a linked list
class linkListQueue:
# Creates an empty queue
def __init__(self):
self._qhead = None
self._qtail = None
self._count = 0
# Returns True if the queue is empty
def isEmpty(self):
return self._qhead is None
# Returns the number of items in the queue
def __len__(self):
return self._count
# Adds the given item to the queue
def enqueue(self, item):
node = _LinkListQueueNode(item)
if self.isEmpty():
self._qhead = node
else:
self._qtail.next = node
self._qtail = node
self._count += 1
# Removes and returns the first item in the queue
def dequeue(self):
assert not self.isEmpty(), "Cannot dequeue from an empty queue."
node = self._qhead
if self._qhead is self._qtail:
self._qtail = None
self._qhead = self._qhead.next
self._count -= 1
return node.item
# Returns an iterator for traversing the list of items
def __iter__(self):
return _LinkListQueueIterator(self._qhead)
# Private storage class for creating the linked list nodes
class _LinkListQueueNode(object):
def __init__(self, item):
self.item = item
self.next = None
# Defines a linked list iterator
class _LinkListQueueIterator:
def __init__(self, queueHead):
self._curNode = queueHead
def __iter__(self):
return self
def next(self):
if self._curNode is None:
raise StopIteration
else:
item = self._curNode.item
self._curNode = self._curNode.next
return item#Init a queue named smith using enqueue #output smith queue CSCI-112 MATH-121 HIST-340 ECON-101 #dequeue one item #output smith after dequeue MATH-121 HIST-340 ECON-101 #output smith after enqueue again MATH-121 HIST-340 ECON-101 ECON-102 #get the length of queue the lenght of queue is 4 #check wheter the queue is empty queue is not empty! #dequeue all items #check wheter the queue is empty after dequeue all items queue is empty! #init again #output smith queue CSCI-112 MATH-121 HIST-340 ECON-101
Python 使用单链表实现队列 (基于class, 包含迭代器)
原文：http://blog.csdn.net/guaguastd/article/details/43449275