Python 中的栈

栈是一种遵循后进先出(LIFO)原则的线性数据结构。

想象一叠煎饼——你只能从顶部添加或取出煎饼。

栈基础

栈是一种可以容纳多个元素的数据结构，最后添加的元素会最先被移除。就像煎饼堆，煎饼都是从顶部添加和移除的。这种元素组织方式称为LIFO：后进先出。

基本栈操作：

• push：向栈顶添加新元素
• pop：移除并返回栈顶元素
• peek：返回栈顶元素(不移除)
• isEmpty：检查栈是否为空
• size：获取栈中元素数量

栈可以用数组或链表实现，常用于实现撤销机制、回溯算法、图的深度优先搜索等。栈常与队列(另一种数据结构)一起讨论。

使用 Python 列表实现栈

对于 Python 列表（和数组）而言，栈的外观和行为可以如下所示：

添加：Push 移除：Pop

由于 Python 列表对实现栈所需的功能提供了良好的支持，因此我们可以从创建栈开始，并仅用几行代码就能执行栈操作，如下所示：

实例

使用 Python 列表作为栈（Stack）：

stack = []

# 入栈（Push）
stack.append('A')
stack.append('B')
stack.append('C')
print("栈（Stack）: ", stack)

# 查看栈顶元素（Peek）
topElement = stack[-1]
print("Peek: ", topElement)

# 出栈（Pop）
poppedElement = stack.pop()
print("Pop: ", poppedElement)

# 出栈后的栈
print("Stack after Pop: ", stack)

# 判断栈是否为空（isEmpty）
isEmpty = not bool(stack)
print("isEmpty: ", isEmpty)

# 栈的大小（Size）
print("Size: ", len(stack))

亲自试一试

虽然 Python 列表可以用作栈，但创建一个专门的栈类可以提供更好的封装性和额外的功能：

实例

使用类创建栈：

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

  def push(self, element):
    self.stack.append(element)

  def pop(self):
    if self.isEmpty():
      return "Stack is empty"
    return self.stack.pop()

  def peek(self):
    if self.isEmpty():
      return "Stack is empty"
    return self.stack[-1]

  def isEmpty(self):
    return len(self.stack) == 0

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

# 创建一个栈
myStack = Stack()

myStack.push('A')
myStack.push('B')
myStack.push('C')

print("Stack: ", myStack.stack)
print("Pop: ", myStack.pop())
print("Stack after Pop: ", myStack.stack)
print("Peek: ", myStack.peek())
print("isEmpty: ", myStack.isEmpty())
print("Size: ", myStack.size())

亲自试一试

使用列表/数组实现栈的原因：

• 内存高效：数组元素不像链表节点那样持有下一个元素的地址。
• 易于实现和理解：使用数组实现栈所需的代码比使用链表要少，因此通常也更容易理解。

不使用数组实现栈的一个原因：

• 固定大小：数组占用内存的一部分是固定的。这意味着它可能会占用比实际需要的更多内存，或者如果数组填满，则无法容纳更多元素。

使用链表实现栈

链表由包含某种数据的节点以及指向下一个节点的指针组成。

使用链表的一个主要好处是，节点可以存储在内存中的任何空闲位置，不像数组中的元素那样必须连续存储。链表的另一个优点是，在添加或删除节点时，列表中的其他节点不需要移动。

为了更好地理解使用数组或链表实现栈的优缺点，你应该查看这个页面，它解释了数组和链表在内存中的存储方式。

以下是使用链表实现栈的方法：

实例

使用链表创建栈：

class Node:
  def __init__(self, value):
    self.value = value
    self.next = None

class Stack:
  def __init__(self):
    self.head = None
    self.size = 0

  def push(self, value):
    new_node = Node(value)
    if self.head:
      new_node.next = self.head
    self.head = new_node
    self.size += 1

  def pop(self):
    if self.isEmpty():
      return "Stack is empty"
    popped_node = self.head
    self.head = self.head.next
    self.size -= 1
    return popped_node.value

  def peek(self):
    if self.isEmpty():
      return "Stack is empty"
    return self.head.value

  def isEmpty(self):
    return self.size == 0

  def stackSize(self):
    return self.size

  def traverseAndPrint(self):
    currentNode = self.head
    while currentNode:
      print(currentNode.value, end=" -> ")
      currentNode = currentNode.next
    print()

myStack = Stack()
myStack.push('A')
myStack.push('B')
myStack.push('C')

print("LinkedList: ", end="")
myStack.traverseAndPrint()
print("Peek: ", myStack.peek())
print("Pop: ", myStack.pop())
print("LinkedList after Pop: ", end="")
myStack.traverseAndPrint()
print("isEmpty: ", myStack.isEmpty())
print("Size: ", myStack.stackSize())

亲自试一试

使用链表实现栈的一个原因：

• 动态大小：与数组不同，栈可以动态地增长和缩小。

不使用链表实现栈的原因：

• 额外内存：每个栈元素必须包含指向下一个元素的地址（即下一个链表节点）。
• 可读性：对于某些人来说，代码可能更难阅读和编写，因为它更长且更复杂。

栈的常见应用

栈在许多现实场景中都有应用：

• 文本编辑器中的撤销/重做操作
• 浏览器历史记录（后退/前进）
• 编程中的函数调用栈
• 表达式求值