最近学习《算法导论》,看了栈与队列,觉得用C实现没意思(以前实现过,不过不能通用),遂用最近在研究的Python实现这两个基本的数据结构!
在一个basicds模块里用实现了两个类:Stack和Queue及其各自所支持的操作,写得比较笨:-) 其实完全可以写个基类List,然后从List中派生出类Stack和Queue,这样做可以避免一些重复代码,因为两个类有很多类似的方法,比如isempty, length等等。(当然这些改进还是等待下一版再做吧,:-)
以下是模块basicds模块源码:
basicds.py
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
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()
运行结果:
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。