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)，元素越多就越慢。

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

总结

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

赞 (0)

相关推荐

  • Python数据结构与算法中的栈详解

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

    目录 0.学习目标 1.栈的基本概念 1.1栈的基本概念 1.2栈抽象数据类型 1.3栈的应用场景 2.栈的实现 2.1顺序栈的实现 2.1.1栈的初始化 2.1.2求栈长 2.1.3判栈空 2.1.4判栈满 2.1.5入栈 2.1.6出栈 2.1.7求栈顶元素 2.2链栈的实现 2.2.1栈结点 2.2.2栈的初始化 2.2.3求栈长 2.2.4判栈空 2.2.5入栈 2.2.6出栈 2.3栈的不同实现对比 3.栈应用 3.1顺序栈的应用 3.2链栈的应用 3.3利用栈基本操作实现复杂算法 总

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

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

    目录 前序.中序和后序表达式是什么? 我们为什么要学习前/后序表达式? 从中序向前序和后序转换 用Python实现从中序表达式到后序表达式的转换​ 计算后序表达式 总结 前序.中序和后序表达式是什么? 对于像B∗C 这样的算术表达式,可以根据其形式来正确地运算.在B∗C 的例子中,由于乘号出现在两个变量之间,因此我们知道应该用变量 B 乘以变量 C .​ 因为运算符出现在两个操作数的中间 ,所以这种表达式被称作中序表达式 .​ 来看另一个中序表达式的例子:A+B∗C.虽然运算符 “ + ” 和

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

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

    目录 匹配括号 匹配符号 总结 匹配括号 接下来,我们使用栈解决实际的计算机科学问题.​ 比如我们都写过这样所示的算术表达式, ( 5 + 6 ) ∗ ( 7 + 8 ) / ( 4 + 3 ) (5 + 6) * (7 + 8) / (4 + 3) (5+6)∗(7+8)/(4+3),其中的括号用来改变计算顺序,或提升运算优先级.​ 匹配括号是指每一个左括号都有与之对应的一个右括号,并且括号对有正确的嵌套关系. 正确的嵌套关系: ( ( ) ( ) ( ) ( ) ) (()()()()) (

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

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

    目录 什么是栈 构建一个栈 总结 什么是栈 栈有时也被称作“下推栈”.它是有序集合,添加操作和移除操作总发生在同一端,即栈的 “顶端”,栈的另一端则被称为 “底端”.所以最新添加的元素将被最先移除,而且栈中的元素离底端越近,代表其在栈中的时间越长. 这种排序原则被称作LIFO(last-in first-out),即后进先出.它提供了一种基于在集合中的时间来排序的方式. 最近添加的元素靠近顶端,旧元素则靠近底端. 栈的例子在日常生活中比比皆是.几乎所有咖啡馆都有一个由托盘或盘子构成的栈,你可以从

  • Python数据结构与算法中的队列详解(1)

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

    目录 什么是队列? 构建一个队列 总结 什么是队列? 队列,与栈类似,是有序集合.添加操作发生在 “尾部”,移除操作只发生在 “头部”.新元素只从尾部进入队列,然后一直向前移动到头部,直到成为下一个被移除的元素.​ 最新添加的元素必须在队列的尾部等待,在队列中时间最长的元素则排在最前面.这种排序原则被称作FIFO(first-in first-out),即先进先出,也称先到先得.在日常生活中,我们经常排队,这便是最简单的队列例子.进电影院要排队,在超市结账要排队,买咖啡也要排队.好的队列只允许一

  • Python数据结构与算法中的队列详解(2)

    Python数据结构与算法中的队列详解(2)

    目录 传土豆 总结 传土豆 队列的一个典型方法是模拟需要以 FIFO 方式管理数据的真实场景.考虑这样一个游戏:传土豆.在这个游戏中,成员们围成一圈,并依次尽可能快地传递一个土豆.在某个时刻,大家停止传递,此时手里有土豆的成员就得退出游戏. 重复上述过程,直到只剩下一个成员. 我们将针对传土豆游戏实现通用的模拟程序.该程序接受一个名字列表和一个用于计数的常量 num ,并且返回最后剩下的那个人的名字. 我们使用队列来模拟一个环.即假设握着土豆的人位于队列的头部.在模拟传土豆的过程中,程序将这个人

  • Python数据结构与算法之跳表详解

    Python数据结构与算法之跳表详解

    目录 0. 学习目标 1. 跳表的基本概念 1.1 跳表介绍 1.2 跳表的性能 1.3 跳表与普通链表的异同 2. 跳表的实现 2.1 跳表结点类 2.2 跳表的初始化 2.3 获取跳表长度 2.4 读取指定位置元素 2.5 查找指定元素 2.6 在跳表中插入新元素 2.7 删除跳表中指定元素 2.8 其它一些有用的操作 3. 跳表应用 3.1 跳表应用示例 0. 学习目标 在诸如单链表.双线链表等普通链表中,查找.插入和删除操作由于必须从头结点遍历链表才能找到相关链表,因此时间复杂度均为O(

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

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

    目录 什么是栈 构建一个栈 总结 什么是栈 栈有时也被称作“下推栈”.它是有序集合,添加操作和移除操作总发生在同一端,即栈的 “顶端”,栈的另一端则被称为 “底端”.所以最新添加的元素将被最先移除,而且栈中的元素离底端越近,代表其在栈中的时间越长. 这种排序原则被称作LIFO(last-in first-out),即后进先出.它提供了一种基于在集合中的时间来排序的方式. 最近添加的元素靠近顶端,旧元素则靠近底端. 栈的例子在日常生活中比比皆是.几乎所有咖啡馆都有一个由托盘或盘子构成的栈,你可以从

  • 详解Python数据结构与算法中的顺序表

    详解Python数据结构与算法中的顺序表

    目录 0. 学习目标 1. 线性表的顺序存储结构 1.1 顺序表基本概念 1.2 顺序表的优缺点 1.3 动态顺序表 2. 顺序表的实现 2.1 顺序表的初始化 2.2 获取顺序表长度 2.3 读取指定位置元素 2.4 查找指定元素 2.5 在指定位置插入新元素 2.6 删除指定位置元素 2.7 其它一些有用的操作 3. 顺序表应用 3.1 顺序表应用示例 3.2 利用顺序表基本操作实现复杂操作 0. 学习目标 线性表在计算机中的表示可以采用多种方法,采用不同存储方法的线性表也有着不同的名称和特

  • Python数据结构之优先级队列queue用法详解

    Python数据结构之优先级队列queue用法详解

    一.基本用法 Queue类实现了一个基本的先进先出容器.使用put()将元素增加到这个序列的一端,使用get()从另一端删除.具体代码如下所示: import queue q = queue.Queue() for i in range(1, 10): q.put(i) while not q.empty(): print(q.get(), end=" ") 运行之后,效果如下: 这里我们依次添加1到10到队列中,因为先进先出,所以出来的顺序也与添加的顺序相同. 二.LIFO队列 既然

随机推荐