python实现链表队列栈
实现如下
#!/usr/bin/python
# -*- coding: utf-8 -*-
#便于测试 data 使用数字
class Node(object):
def __init__(self,data):
self.data = data
self.next = None
self.prev = None
class List(object):
def __init__(self):
self.next = self
self.prev = self
self.size = 0
# 是否为空
def empty(self):
return self.size == 0
# 长度
def lsize(self):
return self.size
# 适用于队列
def put(self,node): # 入队
node.next = self.next
node.prev = self
self.next.prev = node
self.next = node
self.size += 1
def get(self): # 出队
if self.size == 0:
return None
node = self.prev
node.prev.next = self
self.prev = node.prev
self.size -= 1
return node
# 适用于栈
def push(self,node): # 入栈
node.next = self.next
node.prev = self
self.next.prev = node
self.next = node
self.size += 1
def pull(self): # 出栈
if self.size == 0:
return None
node = self.next
node.next.prev = self
self.next = node.next
self.size -= 1
return node
# 适用于链表 在某些情况下也可以当队列或栈处理
def add(self,node): #头部插入
node.next = self.next
node.prev = self
self.next.prev = node
self.next = node
self.size += 1
def append(self,node): #尾部插入
node.prev = self.prev
node.next = self
self.prev.next = node
self.prev = node
self.size += 1
def insert(self,node,index): #index前面插入
cur = self
for i in range(self.lsize()):
cur = cur.next
if cur.data == index:
node.next = cur
node.prev = cur.prev
cur.prev.next = node
cur.prev = node
self.size += 1
return True
return False
def remove(self,index): #删除节点
cur = self
for i in range(self.lsize()):
cur = cur.next
if cur.data == index:
cur.prev.next = cur.next
cur.next.prev = cur.prev
self.size -= 1
return True
return False
def item(self): # 迭代
cur = self
for i in range(self.lsize()):
cur = cur.next
yield cur.data
def find(self,data): # 查找节点是否存在
return data in self.item()
if __name__ == '__main__':
l = List()
for i in range(10):
n = Node(i+1)
l.push(n)
print('queue size =',l.lsize())
while l.empty() != True:
print(l.pull().data)
print('queue size =',l.lsize())
for i in range(10):
n = Node(i+1)
l.put(n)
print('stack size =',l.lsize())
while l.empty() != True:
print(l.get().data)
print('stack size =',l.lsize())
for i in range(10):
n = Node(i+1)
#l.add(n)
l.append(n)
print('list size =',l.lsize())
print('insert 66 to list =',l.insert(Node(66),6))
print('list size =',l.lsize())
print('6 in list =',l.find(6))
print('remove 6 from list =',l.remove(6))
print('6 in list =',l.find(6))
ite = l.item()
print(ite)
for i in ite:
print(i)
