第一种实现方法:以下堆栈实现假定列表的末尾将保存堆栈的顶部元素。随着堆栈的增长,新项目将添加到列表的末尾。
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
第二种实现方案:该方案假设列表的开头保存了栈顶元素,新项目将被添加在索引0处。
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.insert(0,item)
def pop(self):
return self.items.pop(0)
def peek(self):
return self.items[0]
def size(self):
return len(self.items)
作为数据结构的初学者,我想知道以下内容:
1. 在时间和空间效率方面,哪种实现方式更高效,为什么?
2. 第二种实现方式中的
insert(0)
的时间复杂度是否为O(n),如果是,为什么?