Python数据结构与算法基础|第二期：代码实现——栈的顺序存储与链式存储

顺序存储的栈

由于Python内置的列表是顺序存储的，所以我们直接使用列表作为顺序存储的栈的底层。具体代码如下：

class Stack(object):'实现顺序栈。'def __init__(self):'使用列表建立空栈。'self.items = []def IsEmpty(self):'方法：判断是否为空栈，返回布尔值。'if self.items == []:return Trueelse:return Nonedef size(self):'方法：返回栈的大小。'n = len(self.items)return ndef get_TopValue(self):'方法：访问栈顶元素。'if self.IsEmpty == True:return Noneelse:return self.items[-1]def push(self,item):'方法：压栈。'self.items.append(item)def pop(self):'方法：退栈。'self.items.pop()

简单测试：

my_stack = Stack()print('my stack is empty?\n {}'.format(my_stack.IsEmpty()))#创建新栈并压入第一批元素：[my_stack.push(i + 1) for i in range(10)]print("now my stack's size is {}".format(my_stack.size()))print("now my stack's top value is {}".format(my_stack.get_TopValue()))#进行压栈与退栈：my_stack.push(11)print("now my stack's top value is {}".format(my_stack.get_TopValue()))my_stack.pop()print("now my stack's top value is {}".format(my_stack.get_TopValue()))

测试结果：

my stack is empty?Truenow my stack's size is 10now my stack's top value is 10now my stack's top value is 11now my stack's top value is 10

可以看到我们的栈可以正常工作。

链式存储的栈

我们使用属性head代替指针指向栈顶，使用实例化Node类（由于Node类只在Stack类里使用，所以我们直接使用它暴露的属性而不定义其它方法）记录每一个节点的数据域data与指针域prev（指向前件），实现链式存储的栈，具体代码为

class Node(object):'定义节点。'def __init__(self):self.data = Noneself.prev = Noneclass Stack(object):'定义栈。'def __init__(self):'初始化一个空的栈顶元素'self.top = Noneself.size = 0def IsEmpty(self):'方法：判断栈是否为空。'if self.size == 0:return Trueelse:return Nonedef get_size(self):'方法：返回栈的大小。'return self.sizedef get_TopValue(self):'方法：访问栈顶元素。'if not self.IsEmpty():return self.top.dataelse:return Nonedef push(self,data):'方法：压栈。'node = Node()node.data = dataif self.IsEmpty == True:#此时压入的节点没有前件，其prev指针仍为None，只需将top指针指向当前节点即可。self.top = nodeelse:#此时压入的节点不是栈中的第一个元素，需要将其prev指针指向前件，并将top指针指向当前节点。node.prev = self.topself.top = nodeself.size += 1def pop(self):'方法：退栈。'if self.get_size() == 1:self.top = Noneself.size -= 1elif self.get_size() != 0:node = self.top.prevself.top = nodeself.size -= 1 else:raise IndexError('当前栈已经是空栈。')

简单测试：

my_stack = Stack()print('my stack is empty?\n {}'.format(my_stack.IsEmpty()))#创建新栈并压入第一批元素：[my_stack.push(i + 1) for i in range(10)]print("now my stack's size is {}".format(my_stack.get_size()))print("now my stack's top value is {}".format(my_stack.get_TopValue()))#进行压栈与退栈：my_stack.push(11)print("now my stack's top value is {}".format(my_stack.get_TopValue()))my_stack.pop()print("now my stack's top value is {}".format(my_stack.get_TopValue()))#进行11次退栈操作：for i in range(11):print('第{}次：'.format(i + 1))my_stack.pop()print("now my stack's top value is {}".format(my_stack.get_TopValue()))

测试结果：

my stack is empty?Truenow my stack's size is 10now my stack's top value is 10now my stack's top value is 11now my stack's top value is 10第1次：now my stack's top value is 9第2次：now my stack's top value is 8第3次：now my stack's top value is 7第4次：now my stack's top value is 6第5次：now my stack's top value is 5第6次：now my stack's top value is 4第7次：now my stack's top value is 3第8次：now my stack's top value is 2第9次：now my stack's top value is 1第10次：now my stack's top value is None第11次：Traceback (most recent call last):File "带链的栈.py", line 88, in <module>my_stack.pop()File "带链的栈.py", line 69, in popraise IndexError('当前栈已经是空栈。')IndexError: 当前栈已经是空栈。

说明我们定义的栈可以工作。