最近学习《算法导论》,看了栈与队列,觉得用C实现没意思(以前实现过,不过不能通用),遂用最近在研究的Python实现这两个基本的数据结构! 在一个basicds模块里用实现了两个类:Stack和Queue及其各自所支持的操作,写得比较笨:-) 其实完全可以写个基类List,然后从List中派生出类Stack和Queue,这样做可以避免一些重复代码,因为两个类有很多类似的方法,比如isempty, length等等。(当然这些改进还是等待下一版再做吧,:-) 以下是模块basicds模块源码: basicds.py Python语言: 高亮代码由发芽网提供
01 class Stack(object) : 02 def __init__(self) : 03 self.stack = [] 04 05 def push(self, item) : 06 self.stack.append(item) 07 08 def pop(self) : 09 if self.stack != [] : 10 return self.stack.pop(-1) 11 else : 12 return None 13 14 def top(self) : 15 if self.stack != [] : 16 return self.stack[-1] 17 else : 18 return None 19 20 def length(self) : 21 return len(self.stack) 22 23 def isempty(self) : 24 return self.stack == [] 25 26 27 class Queue(object) : 28 def __init__(self) : 29 self.queue = [] 30 31 def enqueue(self, item) : 32 self.queue.append(item) 33 34 def dequeue(self) : 35 if self.queue != [] : 36 return self.queue.pop(0) 37 else : 38 return None 39 40 def head(self) : 41 if self.queue != [] : 42 return self.queue[0] 43 else : 44 return None 45 46 def tail(self) : 47 if self.queue != [] : 48 return self.queue[-1] 49 else : 50 return None 51 52 def length(self) : 53 return len(self.queue) 54 55 def isempty(self) : 56 return self.queue == [] 代码很简单,不解释不注释,呵呵~ 使用例程: 注意basicds.py必须放在Python解释器可以搜索的路径里(使用import时会搜索模块),这里basicds.py和example.py在同一个目录下,属于Python解释器可搜索范围。 example.py Python语言: 高亮代码由发芽网提供
01 #!/usr/bin/env python 02 03 import basicds 04 05 s = basicds.Stack() # get a stack 06 q = basicds.Queue() # get a queue 07 08 09 for i in range(10) : 10 s.push(i) 11 q.enqueue(i) 12 13 # stack s 14 print 'length of stack s is %d' %s.length() 15 print 'top of stack s is %d' %s.top() 16 print 'pop an item %d from stack s' %s.pop() 17 print 'now, top of stack s is %d' %s.top() 18 19 print '\n' 20 21 #queue q 22 print 'length of queue q is %d' %q.length() 23 print 'head of queue q is %d' %q.head() 24 print 'tail of queue q is %d' %q.tail() 25 print 'del an item %d from queue q' %q.dequeue() 26 print 'now, head of queue q is %d' %q.head() 27 print 'tail of queue q is %d' %q.tail() 运行结果: |
|