Stack是一种线性存储结构，特点:先进后出，只能在栈顶进行插入和删除。
node.py
class Node:
def __init__(self,value):
self.value = value
self.pre = None # 指向前一个节点的指针
stack.py
from node import Node
class 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 Stack
import math
def 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 n
print(ten_to_tow(6))
示例2：
from stack import Stack
import math
def 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 Node
class 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 Node
class 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 Stack
class 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 Stack
from node import Node
stack = Stack()
def rev(node):
global stack
preNode = node.pre
if preNode!=None:
rev(preNode)
preNode.pre = node
else:
stack.point = node
for i in range(1,6):
stack.push(i)
node = stack.point
rev(node)
node.pre = None
for i in range(stack.length):
print(stack.pop())
递归加栈实现汉诺塔问题
from node import Node
class 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 True
a=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.length
move(n,a,b,c)
for i in range(n):
print(c.pop())
