Python数据结构与算法中的栈详解(1)

什么是栈

栈，亦称“下推栈”，是一种特殊的有序集合。其核心特征在于所有的添加（入栈）和移除（出栈）操作均严格限制在栈的同一端，即“栈顶”，而另一端则固定为“栈底”。这种结构决定了最新入栈的元素将最先被移除，且元素距离栈底越远，意味着其在栈中停留的时间越短。

这种排序机制被称为LIFO（last-in first-out），即“后进先出”。它提供了一种基于元素加入时间的排序逻辑：最近添加的元素位于栈顶，而最早添加的元素则位于栈底。

栈的概念在日常生活中随处可见。以咖啡馆为例，通常会有一个托盘或盘子堆叠的栈。顾客从顶部取走一个托盘，下一位顾客接着取走下方的托盘，这正是栈操作的直观体现。

利用栈的反转特性，计算机应用中也有大量实例。例如浏览器的“返回”按钮功能：当用户在不同网页间跳转时，访问过的URL被依次存入栈中。当前浏览的网页位于栈顶，最早访问的网页位于栈底。点击返回按钮时，系统便从栈顶开始逆向弹出并展示之前的网页。

构建一个栈

如前所述，栈是元素的有序集合，添加与移除操作均发生在顶端。基于LIFO原则，栈主要支持以下核心操作：

• 将一个元素添加到栈的顶端
• 将栈顶端的元素移除
• 返回栈顶端的元素
• 返回栈中元素的数目

明确了栈的基本特性之后，我们开始用代码构建它。在面向对象的编程语言中(以Python为例)，每当需要在Python中实现像栈这样的抽象数据类型时 ，就可以通过创建一个类的途径实现它，且数据类型的特性、操作方法等也可以通过在类中定义方法实现。

我们来明确一下这个类的具体方法：

• 创建一个空栈。它不需要参数，且会返回一个空栈。 Stack()
• 将一个元素添加到栈的顶端。它需要一 个参数item ，且无返回值。 push(item)
• 将栈顶端的元素移除。它不需要参数，但会返回顶端的元素，并且修改栈的内容。 pop()
• 返回栈顶端的元素，但是并不移除该元素。 它不需要参数，也不会修改栈的内容。 peek()
• 返回栈中元素的数目。它不需要参数，且会返回一个整数。 size()
• 检查栈是否为空。它不需要参数，且会返回一个布尔值。 isEmpty()
• 打印这个栈/列表，它不需要参数，会输出栈的内容。 look()

因为栈是元素的集合，所以完全可以利用Python提供的强大、简单的原生集合来实现。这里，我们将使用列表。 列表的最左端将用来表示栈底，最右边将用来表示栈顶：

class Stack:
  # 定义一个列表/构造一个栈
  def __init__(self):
  	self.items = []
  	print("你创造了一个栈！")
  def isEmpty(self):
    return self.items == []
  def look(self):
    print(self.items)
  def push(self, item):
    self.items.append(item)
    print("你给栈顶加了个%s" % 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)

以下展示了栈的操作及其返回结果：

值得注意的是，也可以选择将列表的头部(左边)作为栈的顶端。 不过在这种情况下，便无法直接使用列表的pop方法和append方法，而必须要用列表的pop方法和insert方法显式地访问下标为0的元素，即列表中的第1个元素。以下代码展现了这种方式：

class Stack:
  def __init__(self):
  	self.items = []
  def isEmpty(self):
    return self.items == []
  def look(self):
    print(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)

尽管上述两种实现都可行，但是二者在性能方面肯定有差异。append 方法和 pop 方法的时间复杂度都是 o ( 1 ) o(1) o(1)，这意味着不论栈中有多少个元素， 第一种实现中的 push 操作和 pop 操作都会在恒定的时间内完成。第二种实现的性能则受制于栈中的元素个数，这 是因为 insert(0) 和 pop(0) 的时间复杂度都是 o ( n ) o(n) o(n)，元素越多就越慢。

显而易见，尽管两种实现在逻辑上是相等的，但是它们在进行基准测试时耗费的时间会有很大的差异。

总结

本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注本站的更多内容!