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全栈之队列详解

    目录 1. lock互斥锁 2. 事件_红绿灯效果 2.1 信号量_semaphore 2.2 事件_红绿灯效果 3. queue进程队列 4. 生产者消费者模型 5. joinablequeue队列使用 6. 总结 1. lock互斥锁 知识点: lock.acquire()# 上锁 lock.release()# 解锁 #同一时间允许一个进程上一把锁 就是Lock 加锁可以保证多个进程修改同一块数据时,同一时间只能有一个任务可以进行修改,即串行的修改,没错,速度是慢了,但牺牲速度却保证了数据

  • Python全栈之线程详解

    Python全栈之线程详解

    目录 1. 线程的概念 1.1 Manager_进程通信 1.2 线程的概念 2. 线程的基本使用 3. 自定义线程_守护线程 3.1 自定义线程 3.2 守护线程 4. 线程安全问题 4.1 线程安全问题 4.2 Semaphore_信号量 5. 死锁_互斥锁_递归锁 6. 线程事件 总结 1. 线程的概念 1.1 Manager_进程通信 # ### Manager ( list 列表 , dict 字典 ) 进程之间共享数据 from multiprocessing import Proc

  • Python数据结构之栈详解

    Python数据结构之栈详解

    目录 0.学习目标 1.栈的基本概念 1.1栈的基本概念 1.2栈抽象数据类型 1.3栈的应用场景 2.栈的实现 2.1顺序栈的实现 2.1.1栈的初始化 2.2链栈的实现 2.3栈的不同实现对比 3.栈应用 3.1顺序栈的应用 3.2链栈的应用 3.3利用栈基本操作实现复杂算法 0. 学习目标 栈和队列是在程序设计中常见的数据类型,从数据结构的角度来讲,栈和队列也是线性表,是操作受限的线性表,它们的基本操作是线性表操作的子集,但从数据类型的角度来讲,它们与线性表又有着巨大的不同.本节将首先介绍

  • Python全栈之协程详解

    Python全栈之协程详解

    目录 1. 线程队列 2. 进程池_线程池 3. 回调函数 4. 协程 总结: 1. 线程队列 # ### 线程队列 from queue import Queue """ put 存放 超出队列长度阻塞 get 获取 超出队列长度阻塞 put_nowait 存放,超出队列长度报错 get_nowait 获取,超出队列长度报错 """ # (1) Queue """先进先出,后进先出"""

  • python数据结构之栈、队列及双端队列

    python数据结构之栈、队列及双端队列

    目录 1.线性数据结构的定义 2.栈 2.1 栈的定义 2.2 栈的数据类型 2.3 用python实现栈 2.4 栈的应用 3. 队列 3.1 队列的定义 3.2 队列抽象数据类型 3.3 用python实现队列 3.3 队列的应用 4. 双端队列 4.1 双端队列的定义 4.2 双端队列抽象数据类型 4.3 用python实现双端队列 4.3 双端队列的应用 5.链表 5.1 链表定义 5.2 用python实现链表 前文学习: python数据类型: python数据结构:数据类型. py

  • Python全栈之字符串和列表相关操作

    Python全栈之字符串和列表相关操作

    目录 1. format格式化_填充符号使用 1.1 format格式化 1.2 format的填充符号的使用 2. 字符串相关的方法 3. 列表的相关操作 4. 列表的相关函数 5. 深浅拷贝 小提示: 6. 小练习 (1)字符串相关练习问题: (2)列表相关练习问题: 总结 1. format格式化_填充符号使用 1.1 format格式化 字符串的格式化format # (1)顺序传参 """{}是format中的占位符""" strvar

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

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

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

  • 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数据结构与算法中的栈详解(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)

    目录 什么是栈 构建一个栈 总结 什么是栈 栈有时也被称作“下推栈”.它是有序集合,添加操作和移除操作总发生在同一端,即栈的 “顶端”,栈的另一端则被称为 “底端”.所以最新添加的元素将被最先移除,而且栈中的元素离底端越近,代表其在栈中的时间越长. 这种排序原则被称作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数据结构与算法中的队列详解(1)

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

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

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

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

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

  • Python数据结构与算法之图的广度优先与深度优先搜索算法示例

    本文实例讲述了Python数据结构与算法之图的广度优先与深度优先搜索算法.分享给大家供大家参考,具体如下: 根据维基百科的伪代码实现: 广度优先BFS: 使用队列,集合 标记初始结点已被发现,放入队列 每次循环从队列弹出一个结点 将该节点的所有相连结点放入队列,并标记已被发现 通过队列,将迷宫路口所有的门打开,从一个门进去继续打开里面的门,然后返回前一个门处 """ procedure BFS(G,v) is let Q be a queue Q.enqueue(v) lab

  • Python数据结构与算法之图结构（Graph）实例分析

    Python数据结构与算法之图结构（Graph）实例分析

    本文实例讲述了Python数据结构与算法之图结构(Graph).分享给大家供大家参考,具体如下: 图结构(Graph)--算法学中最强大的框架之一.树结构只是图的一种特殊情况. 如果我们可将自己的工作诠释成一个图问题的话,那么该问题至少已经接近解决方案了.而我们我们的问题实例可以用树结构(tree)来诠释,那么我们基本上已经拥有了一个真正有效的解决方案了. 邻接表及加权邻接字典 对于图结构的实现来说,最直观的方式之一就是使用邻接列表.基本上就是针对每个节点设置一个邻接列表.下面我们来实现一个最简

随机推荐