python数据结构和算法
2020-12-22 05:30
标签：png 内存 class mic pop == 就是 遍历 code 该数据结构主要是依靠head的不停改变， 队列是先进先出，栈是先进后出，所以只要把数据一个一个先进的后出即可 主要思想就是利用另一个队列来放主要数据队列的n-1个，然后主要数据队列就只剩下最后一个，取出即可，然后重复，就把最后的先出了 python数据结构和算法 标签：png 内存 class mic pop == 就是 遍历 code 原文地址：https://www.cnblogs.com/yangj-Blog/p/13216900.html栈-先进后出
class Stack():
def __init__(self):
self.items = []
def push(self,item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return len(self.items)-1
def isEmpty(self):
return self.items == []
def size(self):
return len(self.items)
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(‘栈顶元素下标:‘,stack.peek())
print(stack.isEmpty())
print(stack.pop())
print(stack.pop())
print(stack.pop())
队列-先进先出
class Queue():
def __init__(self):
self.items = []
def enqueue(self,item):
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
def isEmpty(self):
return self.items == []
def size(self):
return len(self.items)
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
双向队列-头尾都能进出-实现判断回文
单链表-从头部插入节点
class Node():
def __init__(self,item):
self.item = item
self.next = None
class Link():
def __init__(self):
#构造出一个空的链表
self._head = None
def add(self,item):
node = Node(item) #先创建一个节点，在内存中，再考虑怎样操作
node.next =self. _head
self._head = node
def travel(self):
cur = self._head
while cur:
print(cur.item)
cur = cur.next
link = Link()
link.add(3)
link.add(4)
link.travel()
两个队列实现栈
链表倒置
二叉树
class Node():
def __init__(self,item):
self.item = item
self.left = None
self.right = None
class Tree():
def __init__(self):
self.root = None
def addNode(self,item):
node = Node(item)
if self.root == None:
self.root = node
return
cur = self.root
q = [cur] #用列表来进行遍历节点
while q:
nd = q.pop(0) #先把根结点取出
if nd.left == None:
nd.left = node
return
else:
q.append(nd.left)
if nd.right == None:
nd.right = node
return
else:
q.append(nd.right)
def travel(self):
cur = self.root
q = [cur]
while q:
nd = q.pop(0)
print(nd.item)
if nd.left:
q.append(nd.left)
if nd.right:
q.append(nd.right)
tree = Tree()
tree.addNode(1)
tree.addNode(2)
tree.addNode(3)
tree.addNode(4)
tree.addNode(5)
tree.addNode(6)
tree.addNode(7)
tree.travel()
排序二叉树
class Node():
def __init__(self,item):
self.item = item
self.left = None
self.right = None
class SortTree():
def __init__(self):
self.root = None
def addNode(self,item):
node = Node(item)
cur = self.root
if self.root == None:
self.root = node
return
while cur:
#向右插入
if item>cur.item:
if cur.right == None:
cur.right = node
break
else:
cur=cur.right
#向左插入
else:
if cur.left == None:
cur.left = node
break
else:
cur =cur.left
tree = SortTree()
alist = [3,8,5,7,6,2,9,4,1]
for i in alist:
tree.addNode(i)
上一篇：C#中线程的委托