基础数据结构 例：栈、队列、链表、数据、字典、树、等

# 栈的顺序表实现

class Stack(object):
def __init__(self):
self.items = []

def isEmpty(self):
return self.items == []

def push(self, item):
return self.items.append(item)

def pop(self):
return self.items.pop()

def top(self):
return self.items[len(self.items)-1]

def size(self):
return len(self.items)

if __name__ == '__main__':
stack = Stack()
stack.push("Hello")
stack.push("World")
stack.push("!")
print(stack.size())
print(stack.top())
print(stack.pop())
print(stack.pop())
print(stack.pop())

# 结果
3
!
!
World
Hello

# 栈的链接表实现

class SingleNode(object):
def __init__(self, item):
self.item = item
self.next = None

class Stack(object):
def __init__(self):
self._head = None

def isEmpty(self):
return self._head == None

def push(self, item):
node = SingleNode(item)
node.next = self._head
self._head = node

def pop(self):
cur = self._head
self._head = cur.next
return cur.item

def top(self):
return self._head.item

def size(self):
cur = self._head
count = 0
while cur != None:
count += 1
cur = cur.next
return count

if __name__ == '__main__':
stack = Stack()
stack.push("Hello")
stack.push("World")
stack.push("!")
print(stack.size())
print(stack.top())
print(stack.pop())
print(stack.pop())
print(stack.pop())

# 结果
3
!
!
World
Hello

class Queue:
"""
顺序队列实现
"""

def __init__(self):
"""
初始化一个空队列，因为队列是私有的
"""
self.__queue = []

def first(self):
"""
获取队列的第一个元素
:return:如果队列为空，则返回None，否则返回第一个元素
"""
return None if self.isEmpty() else self.__queue[0]

def enqueue(self, obj):
"""
将元素加入队列
:param obj:要加入队列的对象
"""
self.__queue.append(obj)

def dequeue(self):
"""
从队列中删除第一个元素
:return:如果队列为空，则返回None，否则返回dequeued元素
"""
return None if self.isEmpty() else self.__queue.pop(0)

def clear(self):
"""
清除整个队列
"""
self.__queue.clear()

def isEmpty(self):
"""
判断队列是否为空
返回:bool值
"""
return self.length() == 0

def length(self):
"""
获取队列长度
并返回
"""
return len(self.__queue)

class PriorQueue:
"""
优先队列实现
"""

def __init__(self, objs=[]):
"""
初始化优先队列，默认队列为空
:参数objs:对象列表初始化
"""
self.__prior_queue = list(objs)
# 排序从最大值到最小值，最小值具有最高的优先级
# 使得“dequeue”的效率为O(1)
self.__prior_queue.sort(reverse=True)

def first(self):
"""
获取优先队列的最高优先级元素O(1)
:return:如果优先队列为空，则返回None，否则返回优先级最高的元素
"""
return None if self.isEmpty() else self.__prior_queue[-1]

def enqueue(self, obj):
"""
将一个元素加入优先队列，O(n)
:param obj:要加入队列的对象
"""
index = self.length()
while index > 0:
if self.__prior_queue[index - 1] < obj:
index -= 1
else:
break
self.__prior_queue.insert(index, obj)

def dequeue(self):
"""
从优先队列中取出最高优先级的元素，O(1)
:return:如果优先队列为空，则返回None，否则返回dequeued元素
"""
return None if self.isEmpty() else self.__prior_queue.pop()

def clear(self):
"""
清除整个优先队列
"""
self.__prior_queue.clear()

def isEmpty(self):
"""
判断优先队列是否为空
返回:bool值
"""
return self.length() == 0

def length(self):
"""
获取优先队列的长度
返回:
"""
return len(self.__prior_queue)

class Loopqueue:
'''
循环队列实现
'''
def __init__(self, length):
self.head = 0
self.tail = 0
self.maxSize = length
self.cnt = 0
self.__list = [None]*length

def __len__(self):
'''
定义长度
'''
return self.cnt

def __str__(self):
'''
定义返回值 类型
'''
s = ''
for i in range(self.cnt):
index = (i + self.head) % self.maxSize
s += str(self.__list[index])+' '
return s

def isEmpty(self):
'''
判断是否为空
'''
return self.cnt == 0

def isFull(self):
'''
判断是否装满
'''
return self.cnt == self.maxSize

def push(self, data):
'''
添加元素
'''
if self.isFull():
return False
if self.isEmpty():
self.__list[0] = data
self.head = 0
self.tail = 0
self.cnt = 1
return True
self.tail = (self.tail+1)%self.maxSize
self.cnt += 1
self.__list[self.tail] = data
return True

def pop(self):
'''
弹出元素
'''
if self.isEmpty():
return False
data = self.__list[self.head]
self.head = (self.head+1)%self.maxSize
self.cnt -= 1
return data

def clear(self):
'''
清空队列
'''
self.head = 0
self.tail = 0
self.cnt = 0
return True

import threading #引入线程 上锁
import time
from collections import deque # 导入队列


class BlockQueue:
def __init__(self, maxsize=0):
'''
一把锁三个条件（self.mutex,(self.not_full, self.not_empty, self.all_task_done)）,
最大长度与计数君（self.maxsize,self.unfinished）
'''
self.mutex = threading.Lock() # 线程上锁
self.maxsize = maxsize 
self.not_full = threading.Condition(self.mutex)
self.not_empty = threading.Condition(self.mutex)
self.all_task_done = threading.Condition(self.mutex)
self.unfinished = 0

def task_done(self):
'''
每一次put完都会调用一次task_done，而且调用的次数不能比队列的元素多。计数君对应的方法，
unfinished<0时的意思是调用task_done的次数比列表的元素多，这种情况就会抛出异常。
'''
with self.all_task_done:
unfinish = self.unfinished - 1
if unfinish <= 0:
if unfinish < 0:
raise ValueError("The number of calls to task_done() is greater than the number of queue elements")
self.all_task_done.notify_all()
self.unfinished = unfinish

def join(self):
'''
阻塞方法，是一个十分重要的方法，但它的实现也不难，只要没有完成任务就一直wait（），
就是当计数君unfinished > 0 时就一直wait（）知道unfinished=0跳出循环。
'''
with self.all_task_done:
while self.unfinished:
self.all_task_done.wait()

def put(self, item, block=True, timeout=None):
'''
block=True一直阻塞直到有一个空闲的插槽可用，n秒内阻塞，如果在那个时间没有空闲的插槽，则会引发完全的异常。
Block=False如果一个空闲的槽立即可用，则在队列上放置一个条目，否则就会引发完全的异常（在这种情况下，“超时”将被忽略）。
有空位，添加到队列没结束的任务+1，他最后要唤醒not_empty.notify()，因为一开始是要在没满的情况下加锁，满了就等待not_full.wait,
当put完以后就有东西了，每当一个item被添加到队列时，通知not_empty等待获取的线程会被通知。
'''
with self.not_full:
if self.maxsize > 0:
if not block:
if self._size() >= self.maxsize:
raise Exception("The BlockQueue is full")
elif timeout is not None:
self.not_full.wait()
elif timeout < 0:
raise Exception("The timeout period cannot be negative")
else:
endtime = time.time() + timeout
while self._size() >= self.maxsize:
remaining = endtime - time.time()
if remaining <= 0.0:
raise Exception("The BlockQueue is full")
self.not_full.wait(remaining)
self.queue.append(item)
self.unfinished += 1
self.not_empty.notify()

def get(self, block=True, timeout=None):
'''
如果可选的args“block”为True，并且timeout是None，则在必要时阻塞，直到有一个项目可用为止。
如果“超时”是一个非负数，它会阻塞n秒，如果在那个时间内没有可get（）的项，则会抛出空异常。
否则'block'是False，如果立即可用，否则就会抛出空异常，在这种情况下会忽略超时。
同理要唤醒not_full.notify
'''
with self.not_empty:
if not block:
if self._size() <= 0:
raise Exception("The queue is empty and you can't call get ()")
elif timeout is None:
while not self._size():
self.not_empty.wait()
elif timeout < 0:
raise ValueError("The timeout cannot be an integer")
else:
endtime = time.time() + timeout
remaining = endtime - time.time()
if remaining <= 0.0:
raise Exception("The BlockQueue is empty")
self.not_empty.wait(remaining)
item = self._get()
self.not_full.notify()
return item

class QueueNode():
def __init__(self):
self.data = None
self.next = None
class LinkQueue():
def __init__(self):
tQueueNode = QueueNode()
self.front = tQueueNode
self.rear = tQueueNode
'''判断是否为空'''
def IsEmptyQueue(self):
if self.front == self.rear:
iQueue = True
else:
iQueue = False
return iQueue
'''进队列'''
def EnQueue(self,da):
tQueueNode = QueueNode()
tQueueNode.data = da
self.rear.next = tQueueNode
self.rear = tQueueNode
print("当前进队的元素为：",da)
'''出队列'''
def DeQueue(self):
if self.IsEmptyQueue():
print("队列为空")
return
else:
tQueueNode = self.front.next
self.front.next = tQueueNode.next
if self.rear == tQueueNode:
self.rear = self.front
return tQueueNode.data
def GetHead(self):
if self.IsEmptyQueue():
print("队列为空")
return
else:
return self.front.next.data
def CreateQueueByInput(self):
data = input("请输入元素（回车键确定，#结束）")
while data != "#":
self.EnQueue(data)
data = input("请输入元素（回车键确定，#结束）")
'''遍历顺序队列内的所有元素'''
def QueueTraverse(self):
if self.IsEmptyQueue():
print("队列为空")
return
else:
while self.front != self.rear:
result = self.DeQueue()
print(result,end = ' ')
lq = LinkQueue()
lq.CreateQueueByInput()
print("队列里元素为：")
lq.QueueTraverse()

# 结果

请输入元素（回车键确定，#结束）5
当前进队的元素为：5
请输入元素（回车键确定，#结束）8
当前进队的元素为：8
请输入元素（回车键确定，#结束）9
当前进队的元素为：9
请输入元素（回车键确定，#结束）#
队列的元素为：
5 8 9

class Node(object):
"""节点"""

def __init__(self, elem):
self.elem = elem
self.next = None # 初始设置下一节点为空

'''
上面定义了一个节点的类，当然也可以直接使用python的一些结构。比如通过元组（elem, None）
'''


# 下面创建单链表，并实现其应有的功能


class SingleLinkList(object):
"""单链表"""

def __init__(self, node=None): # 使用一个默认参数，在传入头结点时则接收，在没有传入时，就默认头结点为空
self.__head = node

def is_empty(self):
'''链表是否为空'''
return self.__head == None

def length(self):
'''链表长度'''
# cur游标，用来移动遍历节点
cur = self.__head
# count记录数量
count = 0
while cur != None:
count += 1
cur = cur.next
return count

def travel(self):
'''遍历整个列表'''
cur = self.__head
while cur != None:
print(cur.elem, end=' ')
cur = cur.next
print("\n")

def add(self, item):
'''链表头部添加元素'''
node = Node(item)
node.next = self.__head
self.__head = node

def append(self, item):
'''链表尾部添加元素'''
node = Node(item)
# 由于特殊情况当链表为空时没有next，所以在前面要做个判断
if self.is_empty():
self.__head = node
else:
cur = self.__head
while cur.next != None:
cur = cur.next
cur.next = node

def insert(self, pos, item):
'''指定位置添加元素'''
if pos <= 0:
# 如果pos位置在0或者以前，那么都当做头插法来做
self.add(item)
elif pos > self.length() - 1:
# 如果pos位置比原链表长，那么都当做尾插法来做
self.append(item)
else:
per = self.__head
count = 0
while count < pos - 1:
count += 1
per = per.next
# 当循环退出后，pre指向pos-1位置
node = Node(item)
node.next = per.next
per.next = node

def remove(self, item):
'''删除节点'''
cur = self.__head
pre = None
while cur != None:
if cur.elem == item:
# 先判断该节点是否是头结点
if cur == self.__head:
self.__head = cur.next
else:
pre.next = cur.next
break
else:
pre = cur
cur = cur.next

def search(self, item):
'''查找节点是否存在'''
cur = self.__head
while not cur:
if cur.elem == item:
return True
else:
cur = cur.next
return False


if __name__ == "__main__":

# node = Node(100) # 先创建一个节点传进去

ll = SingleLinkList()
print(ll.is_empty())
print(ll.length())

ll.append(3)
ll.add(999)
ll.insert(-3, 110)
ll.insert(99, 111)
print(ll.is_empty())
print(ll.length())
ll.travel()
ll.remove(111)
ll.travel()

class Node(object):
def __init__(self,val,p=0):
self.data = val
self.next = p
self.prev = p

class LinkList(object):
def __init__(self):
self.head = 0

def __getitem__(self, key):

if self.is_empty():
print 'linklist is empty.'
return

elif key <0 or key > self.getlength():
print 'the given key is error'
return

else:
return self.getitem(key)

 

def __setitem__(self, key, value):

if self.is_empty():
print 'linklist is empty.'
return

elif key <0 or key > self.getlength():
print 'the given key is error'
return

else:
self.delete(key)
return self.insert(key)

def initlist(self,data):

self.head = Node(data[0])

p = self.head

for i in data[1:]:
node = Node(i)
p.next = node
node.prev = p
p = p.next

def getlength(self):

p = self.head
length = 0
while p!=0:
length+=1
p = p.next

return length

def is_empty(self):

if self.getlength() ==0:
return True
else:
return False

def clear(self):

self.head = 0


def append(self,item):

q = Node(item)
if self.head ==0:
self.head = q
else:
p = self.head
while p.next!=0:
p = p.next
p.next = q
q.prev = p


def getitem(self,index):

if self.is_empty():
print 'Linklist is empty.'
return
j = 0
p = self.head

while p.next!=0 and j <index:
p = p.next
j+=1

if j ==index:
return p.data

else:

print 'target is not exist!'

def insert(self,index,item):

if self.is_empty() or index<0 or index >self.getlength():
print 'Linklist is empty.'
return

if index ==0:
q = Node(item,self.head)

self.head = q

p = self.head
post = self.head
j = 0
while p.next!=0 and j<index:
post = p
p = p.next
j+=1

if index ==j:
q = Node(item,p)
post.next = q
q.prev = post
q.next = p
p.prev = q


def delete(self,index):

if self.is_empty() or index<0 or index >self.getlength():
print 'Linklist is empty.'
return

if index ==0:
q = Node(item,self.head)

self.head = q

p = self.head
post = self.head
j = 0
while p.next!=0 and j<index:
post = p
p = p.next
j+=1

if index ==j:
post.next = p.next
p.next.prev = post

def index(self,value):

if self.is_empty():
print 'Linklist is empty.'
return

p = self.head
i = 0
while p.next!=0 and not p.data ==value:
p = p.next
i+=1

if p.data == value:
return i
else:
return -1


l = LinkList()
l.initlist([1,2,3,4,5])
print l.getitem(4)
l.append(6)
print l.getitem(5)

l.insert(4,40)
print l.getitem(3)
print l.getitem(4)
print l.getitem(5)

l.delete(5)
print l.getitem(5)

l.index(5)

# 结果
5
6
4
40
5
6

class ListNode:
def __init__(self, x):
self.val = x
self.next = None


def reverse(head): # 循环的方法反转链表
if head is None or head.next is None:
return head
# 定义反转的初始状态
pre = None
cur = head
newhead = head
while cur:
newhead = cur
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return newhead

if __name__ == '__main__':
head = ListNode(1) # 测试代码
p1 = ListNode(2) # 建立链表1->2->3->4->None;
p2 = ListNode(3)
p3 = ListNode(4)
head.next = p1
p1.next = p2
p2.next = p3
p = reverse(head) # 输出链表 4->3->2->1->None
while p:
print(p.val)
p = p.next

class ListNode:
def __init__(self, x):
self.val = x
self.next = None


def reverse(head, newhead): # 递归，head为原链表的头结点，newhead为反转后链表的头结点
if head is None:
return
if head.next is None:
newhead = head
else:
newhead = reverse(head.next, newhead)
head.next.next = head
head.next = None
return newhead

if __name__ == '__main__':
head = ListNode(1) # 测试代码
p1 = ListNode(2) # 建立链表1->2->3->4->None
p2 = ListNode(3)
p3 = ListNode(4)
head.next = p1
p1.next = p2
p2.next = p3
newhead = None
p = reverse(head, newhead) # 输出链表4->3->2->1->None
while p:
print(p.val)
p = p.next

>>> map(hash, (0, 1, 2, 3)) 

[0, 1, 2, 3] 

>>> map(hash, ("namea", "nameb", "namec", "named")) 

[-1658398457, -1658398460, -1658398459, -1658398462]