如何基于数组或者链表实现栈

可以使用数组或链表来实现栈的数据结构。

基于数组的实现：
1. 创建一个固定大小的数组来存储栈的元素。
2. 使用一个变量 top 来表示栈顶的索引，初始值为 -1。
3. 当有新元素入栈时，将 top 加一，并将新元素存储在 top 的位置。
4. 当需要弹出栈顶元素时，返回 top 位置的元素，并将 top 减一。
5. 可以通过判断 top 是否等于 -1 来检查栈是否为空。

基于链表的实现：
1. 创建一个链表节点类，包含一个数据域和一个指向下一个节点的指针。
2. 使用一个指针 top 指向栈顶节点，初始值为 null。
3. 当有新元素入栈时，创建一个新节点，并将其指针指向当前的 top 节点，然后更新 top 指针为新节点。
4. 当需要弹出栈顶元素时，返回 top 节点的数据域，并将 top 指针更新为下一个节点。

无论是基于数组还是链表的实现，栈的操作时间复杂度都是 O(1)。选择哪种实现方式取决于具体的需求和场景。如果需要支持动态大小的栈，链表实现更加灵活。如果栈的大小固定且较小，数组实现可能更高效。