引言
- 函数调用
- 编译原理：语法分析
- 括号匹配
问题：栈是操作受限的线性表，为什么不直接用数组或者链表？
数组和链表暴露了太多接口，操作虽然灵活，但不可控，容易出错。比如数组支持任意位置插入数组，如果插入位置写错将改变所有数组的内容。
而栈只能在一端插入和删除数据，并且后进先出。
顺序栈
使用数组实现栈
class ArrayStack:
def __init__(self, n) -> None:
self.data = [-1]*n
self.n = n
self.count = 0
def push(self, value):
if self.n == self.count:
return False
self.data[self.count] = value
self.count += 1
return True
def pop(self):
if self.count == 0:
return None
self.count -= 1
return self.data[self.count]
def test_static():
array_stack = ArrayStack(5)
data = ["a", "b", "c", "d", "e"]
for i in data:
array_stack.push(i)
result = array_stack.push("a")
assert not result
data.reverse()
for i in data:
assert i == array_stack.pop()
assert array_stack.pop() is None
if __name__ == '__main__':
test_static()
入栈时间复杂度：O(1)
出栈时间复杂度：O(1)
链式栈
使用链表实现栈
class StackBasedOnLinkedList:
def __init__(self) -> None:
self.top = None
def push(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 pop(self):
if self.top is None:
return -1
result = self.top.data
self.top = self.top.next
return result
class Node:
def __init__(self, data) -> None:
self.data = data
self.next = None
def test_static():
stack = StackBasedOnLinkedList()
data = [1, 2, 3, 4, 5]
for i in data:
stack.push(i)
data.reverse()
for i in data:
assert i == stack.pop()
assert stack.pop() == -1
入栈时间复杂度：O(1)
出栈时间复杂度：O(1)