Stack是一种线性存储结构，特点:先进后出，只能在栈顶进行插入和删除。
node.py
class Node: def __init__(self,value): self.value = value self.pre = None # 指向前一个节点的指针
stack.py
from node import Nodeclass Stack: def __init__(self): self.point = None self.length = 0 def push(self,value): node = Node(value) if self.point!= None: node.pre = self.point self.point = node else: self.point = node self.length += 1 def pop(self): if self.point!= None: node = self.point self.point = node.pre node.pre = None self.length -= 1 return node.value else: return None def isNone(self): if self.length > 0: return False else: return True
栈的应用：十进制转二进制
示例1：
from stack import Stackimport mathdef ten_to_tow(n): if n > 1: stack = Stack() temp = n while(temp> 0): mod = temp % 2 stack.push(mod) temp = math.floor(temp/2) v = stack.pop() while(stack.isNone()==False): v = v*10+stack.pop() return v else: return nprint(ten_to_tow(6))
示例2：
from stack import Stackimport mathdef ten_to_two(n): stack=Stack() while (n>0): mod = n % 2 stack.push(mod) n = math.floor(n/2) for i in range(stack.length): v=stack.pop() print(v,end='')ten_to_two(9)
最小栈
from node import Nodeclass MinStack: def __init__(self): self.point = None self.length = 0 def push(self,value): node = Node(value) if self.point!= None: if node.value>self.point.value: minV=self.pop() self.add(node) self.length += 1 self.add(Node(minV)) else: self.point = node self.length += 1 def add(self,node): node.pre = self.point self.point = node def pop(self): if self.point!= None: node = self.point self.point = node.pre node.pre = None self.length -= 1 return node.value else: return None def isNone(self): if self.length > 0: return False else: return True
队列
队列是先进先出的线性表，它只允许在表的后端进行插入操作，称为入队；它只允许在表的前端进行删除操作，称为出队。
node.py
class Node: def __init__(self,value): self.value = value self.next = None # 指向后一个节点的指针
quence.py
from node import Nodeclass Quenece: def __init__(self): self.head = None self.rear = None self.length = 0 def inQue(self,value): node = Node(value) if self.head!=0: self.rear.next = node self.rear = node else: self.head = node self.rear = node self.length += 1 def OutQue(self): node = self.head if node.next!=None: self.head = node.next node.next = None else: self.head = None self.rear = None self.length -= 1 return node.value def isNone(self): if self.head!=None: return False else: return True
两个栈实现一个队列
stackque.py
from stack import Stackclass StackQue: def __init__(self): self.a=Stack() self.b=Stack() def appendTail(self,value): if self.b.isNone() == False: b_length=self.b.length for i in range(b_length): self.a.push(self.b.pop()) self.a.push(value) def deleteHead(self): if self.a.isNone() == False: a_length = self.a.length for i in range(a_length): self.b.push(self.a.pop()) return self.b.pop()stackque = StackQue()for i in range(5): stackque.appendTail(i)for i in range(2): print(stackque.deleteHead())for i in range(7,10): stackque.appendTail(i)for i in range(10): print(stackque.deleteHead())
以递归的方式反转一个栈
from stack import Stackfrom node import Nodestack = Stack()def rev(node): global stack preNode = node.pre if preNode!=None: rev(preNode) preNode.pre = node else: stack.point = nodefor i in range(1,6): stack.push(i)node = stack.pointrev(node)node.pre = Nonefor i in range(stack.length): print(stack.pop())
递归加栈实现汉诺塔问题
from node import Nodeclass Stack: def __init__(self): self.point = None self.length = 0 self.name = None def push(self, value): node = Node(value) if self.point != None: node.pre = self.point self.point = node else: self.point = node self.length += 1 def pop(self): if self.point != None: node = self.point self.point = node.pre node.pre = None self.length -= 1 return node.value else: return None def isNone(self): if self.length > 0: return False else: return Truea=Stack()a.name='A'b=Stack()b.name='B'c=Stack()c.name='C'def move(n,s1,s2,s3): if n!=1: move(n-1,s1,s3,s2) move(1,s1,s2,s3) move(n-1,s2,s1,s3) else: s3.push(s1.pop()) print(s1.name,'=>',s3.name)for i in range(4,0,-1): a.push(i)n=a.lengthmove(n,a,b,c)for i in range(n): print(c.pop())