Python 中的高效堆栈实现

Question

1st Implementation: 下面的堆栈实现假设列表的末尾将保存堆栈的顶部元素。随着堆栈的增长，新项目将添加到列表的末尾。

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. 哪个实现在时间或 space 方面更有效，为什么？
2. 是第2个实现中insert(0)的时间复杂度O(n)。如果是，如何？

Answer 1

列表针对从末尾追加和弹出进行了优化。从列表开头插入或删除项目的开销要大得多，因为所有项目都需要移动。

Python 确实有一个数据结构，collections.deque，它针对两端追加进行了优化。

Answer 2

在 Python 中，列表是使用可调整大小的其他对象引用数组实现的。

见How are lists implemented?

因此，列表末尾的 pushing/popping 个元素比列表开头的 pushing/popping 个元素更有效率。

Adding/removing 个元素到数组的开头是非常昂贵的，因为您必须将所有其他元素移动到一个 space 之上。另一方面，假设数组末尾有足够的空space，add/remove个元素到数组末尾相对便宜。

当数组已满时，Python会动态分配更多的内存到该数组的末尾，这是昂贵的，但摊销性能仍然非常好。

Answer 3

def __init__(self):
  self.items=[]
def push(self,item):
  self.items.append(item)
def pop(self):
  return self.items.pop()
def isEmpty(self):
  return self.items==[]
def peek(self):
  return self.items[len(self.items)-1]
def size(self):
  return len(self.items)

`

Python 中的高效堆栈实现

Efficient Stack implementation in Python

python

performance

data-structures

stack

abstract-data-type