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)，如果是，为什么？

- Kshitij Saraogi

---

请参阅 https://wiki.python.org/moin/TimeComplexity。请注意，`self.items[-1]` 可以让您更轻松地获取最后一个元素。 - jonrsharpe

是的，请重新编写您的“peek”方法。并将其命名为tos，可能是（栈顶）。 - Pynchia

感谢@jonrsharpe提供的链接。 - Kshitij Saraogi

Answer 1

• 列表优化了从末尾添加和弹出操作。在列表开头插入或删除项更加昂贵，因为需要移动所有项。
• Python具有数据结构，它经过优化可同时在两端进行添加操作。

- Daniel Roseman

Answer 2

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

参见 如何实现列表？ 因此，在列表末尾推入/弹出元素比在列表开头推入/弹出元素更有效率。

将元素添加/删除到数组的开头非常昂贵，因为您必须将所有其他元素向右移动一个空间。另一方面，假设数组末尾有足够的空闲空间，向数组末尾添加/删除元素相对较便宜。

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

- ben_frankly

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)

`

- minitechi