python算法-队列
一、队列的特征性:
1. 先进先出
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
last first
二、类定义队列
class:
1、实例属性
a.first节点
b.last节点
每一个新元素进来时,都是从最后面插入进来;每一个元素要出去,都是从开头向外出。
2、实例方法
a.进队列 enqueue
核心算法: 判断队列是否为空,如果是空则first,last都指向新加入的结点node;
如果不为空,这first指向队列第一个元素位置,在队尾插入元素完成后,last指向向后加1
b.出队列 dequeue
核心算法:
参数:None
返回值:节点的值
队列为空时,return None;队列不为空,记录首节点first,然后将下一个节点的值赋给first(可能为None),最后返回首节点的值。
3、练习:用上述的代码,完成67,45,34节点顺序放入队列,之后从队列的头部开始访问队列里的每一个元素。
4、练习:目前的队列,无法判断队列里面节点的个数,新增一个实例属性self.num,完成队列节点的计算,在是上题的基础上打印队列剩余节点的个数。
三、代码:
#encoding=utf-8
class Node(object):
def __init__(self, val):
self.value = val
self.next = None
class Queue(object):
def __init__(self):
self.first = None
self.last = None
def enqueue(self,n):
if self.first == None:
newNode = Node(n)
self.first = newNode
self.last = newNode
else:
newNode = Node(n)
self.last.next = newNode
self.last = newNode
def dequeue(self):
if self.first == None:
return None
else:
tmpVar = self.first.value
self.first = self.first.next
if self.first == None:
self.last = None
return tmpVar
if __name__ == '__main__':
q = Queue()
varList = [67,45,34,38,96,101]
for var in varList:
q.enqueue(var)
for i in xrange(3):
q.dequeue()
node = q.first
while node != None:
print node.value
node = node.next
最新文章
- KindEditor 给KindEditor赋值
- canvas游戏之贪食蛇
- android项目中配置NDK自动编译生成so文件
- sublime text3 编译less
- java多线程系列4-线程池
- LUA之面向对象
- mysql 2006
- LoadRunner监控Windows和Linux常见问题
- HDU 3078 Network LCA
- TCP\UDP链接的异同
- 28 Corn表达式详解 (转自http://blog.csdn.net/claram/article/details/51785193)
- 《Two Days DIV + CSS》读书笔记——CSS控制页面方式
- Windows系统下远程Linux系统
- webpack4.0各个击破(3)—— Assets篇
- left join inner join 区别
- Python 多继承与MRO-C3算法
- WOSA/XFS PTR Form解析库—FormRule.h
- 路由器mtu值设置
- Visual C++ 使用纪要
- 字符串转换atof atoi atol gcvt strtod strtol strto ul toascii tolower toupper