堆栈
数组和列表暴露了太多的接口，虽然操作灵活，但不可控，容易出错。如果在插入位置写错数据将会改变整个数组的内容
栈是**操作受限的列表
栈只能在一端进行删除和插入操作，遵循先进后出后进先出的原则
- 数组栈
class ArrayStack:
def __init__(self, volume):
self.vol = volume
self.count = 0
self.data = [-1] * volume
def in_stack(self, value):
"""入栈"""
if self.count == self.vol:
return False
self.data[self.count] = value
self.count += 1
return True
def de_stack(self):
"""出栈"""
if self.count == 0:
return None
self.count -= 1
return self.data[self.count]
def test_stack():
array_stack = ArrayStack(5)
data = ["a", "b", "c", "d", "e"]
for i in data:
array_stack.in_stack(i)
result = array_stack.in_stack("a")
assert not result
data.reverse()
for i in data:
assert i == array_stack.de_stack()
assert not array_stack.de_stack()
入栈时间复杂度：O(1)
出栈时间复杂度：O(1)
- 链式栈
class LinkStack:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def __init__(self):
self.top = None
def en_stack(self, value):
"""入栈"""
new_node = self.Node(value)
if self.top is None:
self.top = new_node
else:
new_node.next = self.top
self.top = new_node
def de_stack(self):
"""出栈"""
if self.top is None:
return -1
result = self.top.data
self.top = self.top.next
return result
def test_link_stack():
link_stack = LinkStack()
data = [1, 2, 3, 4, 5]
for i in data:
link_stack.en_stack(i)
data.reverse()
for j in data:
assert j == link_stack.de_stack()
assert link_stack.de_stack() == -1
入栈时间复杂度：O(1)
出栈时间复杂度：O(1)