数据结构-栈

1. 定义：

栈是一种只能在一端进行插入和删除操作的线性数据结构。它遵循后进先出（LIFO, Last In First Out）的原则，即最后插入的元素将是第一个被移除的

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            raise IndexError("pop from an empty stack")

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            raise IndexError("peek from an empty stack")

    def size(self):
        return len(self.items)

# 示例用法
if __name__ == "__main__":
    stack = Stack()
    stack.push(1)
    stack.push(2)
    stack.push(3)
    print("Stack:", stack.items)
    print("Size:", stack.size())
    print("Peek:", stack.peek())
    print("Pop:", stack.pop())
    print("Stack after pop:", stack.items)

2. 主要操作：

栈的主要操作包括push（添加元素到栈顶）、pop（从栈顶移除元素）和peek（查看栈顶元素），以及isEmpty（检查栈是否为空）。

• push

def push(self, item):
        self.items.append(item)  # 添加至列表末尾，类似于栈

• pop

def pop(self):
        if not self.is_empty(): 
            return self.items.pop()  # 删除列表的末尾元素

• peek

def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            raise IndexError("peek from an empty stack")

• isEmpty

def is_empty(self):
        return self.items == []

注：

1. 使用 self.items == [] 来检查栈是否为空。这种方式的逻辑是，如果栈为空，那么 self.items 应该是一个空列表 []，因此通过 self.items == [] 来判断栈是否为空是合适的。
2. 如果我们使用 None 来表示空栈，那么在检查栈是否为空时，我们需要使用 self.items is None。但是，这样做会带来一些问题。
3. 在初始化栈时，我们将 self.items 设置为一个空列表 []，而不是 None。因此，检查栈是否为空时，使用 self.items is None 会导致不一致，因为 self.items 实际上不是 None。
4. 使用 None 来表示空栈可能会引入额外的复杂性。因为 None 是一个特殊的对象，它与其他值的比较和操作可能会导致意外的行为。在这种情况下，使用一个明确的标记来表示空栈（例如空列表 []）会更加清晰和直观。
5. 因此，为了简化逻辑并避免潜在的问题，我们选择使用 self.items == [] 来检查栈是否为空。

3. 特性：

由于栈是一种严格的LIFO数据结构，它的主要特性是顺序性和受限的访问。这意味着只能访问栈的顶部元素，无法直接访问栈中的其他元素。Python 中可以使用列表（List）来实现栈，利用列表的 append() 方法在末尾添加元素，以及 pop() 方法移除并返回末尾元素，实现了栈的基本操作。这种实现方式简单高效，适用于大多数场景。

4. 应用：

栈在许多计算任务中非常有用，包括但不限于实现函数调用（调用栈）、处理递归、后缀表达式求值和语法分析等。

5. 实现方式：

栈可以通过数组或链表实现。数组实现的栈具有固定大小，而链表实现的栈则具有动态大小。