Pop操作的栈复杂度
Stack Complexity of Pop operation
在用链表实现的堆栈中，pop() 操作的大 O 表示法是什么？
用数组实现的堆栈中 pop() 操作的大 O 表示法是什么？
使用链表时，可以保留指向链表第一个和最后一个元素的指针。弹出需要简单地删除其中一个并更新两个（或三个，如果是双向链接的）指针：链表中的一个，它正在查看堆栈的顶部元素，以及列表中第一个元素的一个。所以 O(1)，在这种情况下。
对于数组实现，这取决于。您可以将 pop 操作实现为简单地删除数组中的最后一个元素，并更新大小，这又是 O(1)。然而，通常情况是当堆栈的数组实现增长，然后显着收缩时，项目被移动到一个新数组以节省内存（比如，如果你连续弹出 10.000 次并希望内存没有被不必要地保存，那么你可以将所有剩余的项目复制到一个新的、更小的数组中）。在这种情况下，它将是 O(n)，因为每个元素都需要复制到一个新数组中。
在用链表实现的堆栈中，pop() 操作的大 O 表示法是什么？ 用数组实现的堆栈中 pop() 操作的大 O 表示法是什么？
使用链表时，可以保留指向链表第一个和最后一个元素的指针。弹出需要简单地删除其中一个并更新两个（或三个，如果是双向链接的）指针：链表中的一个，它正在查看堆栈的顶部元素，以及列表中第一个元素的一个。所以 O(1)，在这种情况下。
对于数组实现，这取决于。您可以将 pop 操作实现为简单地删除数组中的最后一个元素，并更新大小，这又是 O(1)。然而，通常情况是当堆栈的数组实现增长，然后显着收缩时，项目被移动到一个新数组以节省内存（比如，如果你连续弹出 10.000 次并希望内存没有被不必要地保存，那么你可以将所有剩余的项目复制到一个新的、更小的数组中）。在这种情况下，它将是 O(n)，因为每个元素都需要复制到一个新数组中。