Python中的高效堆栈实现

Question

第一个实现:以下堆栈实现假定列表的末尾将保存堆栈的顶部元素.随着堆栈的增长,新项目将添加到列表的末尾.

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).如果有,怎么样？

Answer 1

列表经过优化,可以从最后添加和弹出.从列表的开头插入或删除项目要昂贵得多,因为需要移动所有项目.

Python确实有一个数据结构,collections.deque它被优化用于两端附加.