python中实现栈的三种方法

栈是一种线性数据结构,用先进后出或者是后进先出的方式存储数据,栈中数据的插入删除操作都是在栈顶端进行,常见栈的函数操作包括

  • empty() – 返回栈是否为空 – Time Complexity : O(1)
  • size() – 返回栈的长度 – Time Complexity : O(1)
  • top() – 查看栈顶元素 – Time Complexity : O(1)
  • push(g) – 向栈顶添加元素 – Time Complexity : O(1)
  • pop() – 删除栈顶元素 – Time Complexity : O(1)

python中栈可以用以下三种方法实现:

1)list

2)collections.deque

3)queue.LifoQueue

使用列表实现栈

python的内置数据结构list可以用来实现栈,用append()向栈顶添加元素, pop() 可以以后进先出的顺序删除元素

但是列表本身有一些缺点,主要问题就是当列表不断扩大的时候会遇到速度瓶颈.列表是动态数组,因此往其中添加新元素而没有空间保存新的元素时,它会自动重新分配内存块,并将原来的内存中的值复制到新的内存块中.这就导致了一些append()操作会消耗更多的时间

>>> stack = []
>>> #append() fuction to push
... #element in list
...
>>> stack.append('hello')
>>> stack.append('world')
>>> stack.append('!')
>>> print('Initial stack')
Initial stack
>>> print(stack)
['hello', 'world', '!']
>>> #pop() function to pop element
... #from stack in LIFO order
...
>>> print('\nElement poped from stack')

Element poped from stack

>>> print(stack.pop())
!
>>> print(stack.pop())
world
>>> print(stack.pop())
hello
>>> print('\nStack after all elements are poped')

Stack after all elements are poped
>>> print(stack)
[]

使用collections.deque实现栈

python中栈也可以用deque类实现,当我们想要在实现在容器两端更快速地进行append和pop操作时,deque比列表更合适.deque可以提供O(1)时间的append和pop操作,而列表则需要O(n)时间.

>>> from collections import deque
>>> stack = deque()
>>> # append() fuction to push
... #element in list
...
>>> stack.append('hello')
>>> stack.append('world')
>>> stack.append('!')
>>> print('Initial stack')
Initial stack
>>> print(stack)
deque(['hello', 'world', '!'])
>>> #pop() function to pop element
... #from stack in LIFO order
...
>>> print('\nElement poped from stack')

Element poped from stack
>>> print(stack.pop())
!
>>> print(stack.pop())
world
>>> print(stack.pop())
hello
>>> print('\nStack after all elements are poped')

Stack after all elements are poped
>>> print(stack)deque([])

使用queue module实现栈

Queue模块有LIFO queue,也就是栈结构.用put()和get()操作从Queue中添加和获得数据

>>> from queue import LifoQueue
>>> stack = LifoQueue(maxsize = 3)
>>> print(stack.qsize())
0
>>> stack.put('hello')
>>> stack.put('world')
>>> stack.put('!')
>>> print('\nElement poped from stack')

Element poped from stack
>>> print(stack.get())
!
>>> print(stack.get())
world
>>> print(stack.get())
hello
>>> print('\nEmpty:', stack.empty())

Empty: True

以上就是python中实现栈的三种方法的详细内容,更多关于python 实现栈的资料请关注我们其它相关文章!

(0)

相关推荐

  • Python实现的栈、队列、文件目录遍历操作示例

    本文实例讲述了Python实现的栈.队列.文件目录遍历操作.分享给大家供大家参考,具体如下: 一. 栈与队列 1. 栈 stack 特点:先进先出[可以抽象成竹筒中的豆子,先进去的后出来] 后来者居上 mystack = [] #压栈[向栈中存数据] mystack.append(1) print(mystack) mystack.append(2) print(mystack) mystack.append(3) print(mystack) #出栈[从栈中取数据] mystack.pop()

  • 使用python实现数组、链表、队列、栈的方法

    引言 什么是数据结构? 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成. 简单来说,数据结构就是设计数据以何种方式组织并存储在计算机中. 比如:列表,集合和字典等都是数据结构 N.Wirth:"程序=数据结构+算法" 数据结构按照其逻辑结构可分为线性结构.树结构.图结构 线性结构:数据结构中的元素存在一对一的互相关系. 树结构:数据结构中的元素存在一对多的互相关系. 图结构:数据结构中的元素存在多对多的互相关系. 数组 在python中是没有数

  • Python中栈、队列与优先级队列的实现方法

    前言 栈.队列和优先级队列都是非常基础的数据结构.Python作为一种"编码高效"的语言,对这些基础的数据结构都有比较好的实现.在业务需求开发过程中,不应该重复造轮子,今天就来看看些数据结构都有哪些实现. 0x00 栈(Stack) 栈是一种LIFO(后进先出)的数据结构,有入栈(push).出栈(pop)两种操作,且只能操作栈顶元素. 在Python中有多种可以实现栈的数据结构. 1.list list是Python内置的列表数据结构,它支持栈的特性,有入栈和出栈操作.只不过用lis

  • python全栈要学什么 python全栈学习路线

    IT行业,技术要比学历.年龄.从业经验更为重要,技术水平直接决定就业薪资,想要学好python,首先要先了解精通Python语言基础.Python web开发.Python爬虫.Python数据分析这四大方面. 全栈即指的是全栈工程师,指掌握多种技能,并能利用多种技能独立完成产品的人.就是与这项技能有关的都会,都能够独立的完成. 全栈只是个概念,也分很多种类.真正的全栈工程师涵盖了web开发.DBA .爬虫 .测试.运维,要学的内容那是相当的巨量.就web开发方向而言需要学习的内容:前端知识 包

  • python实现异常信息堆栈输出到日志文件

    将try except中捕获到的异常信息输出到日志文件中,方便查找错误原因,tranceback模块提供了把详细出错堆栈信息格式化成字符串返回函数format_exc(). 具体代码如下 import traceback import logging logging.basicConfig(filename='log.log') def error_func(): b = 1 / 0 if __name__ == '__main__': try: error_func() except: s =

  • Python捕获异常堆栈信息的几种方法(小结)

    程序出错的时候,我们往往需要根据异常信息来找到具体出错的代码.简单地用print打印异常信息并不能很好地追溯出错的代码: # -*- coding: utf-8 -*- def foo(a, b): c = a + b raise ValueError('test') return c def bar(a): print('a + 100:', foo(a, 100)) def main(): try: bar(100) except Exception as e: print(repr(e))

  • python栈的基本定义与使用方法示例【初始化、赋值、入栈、出栈等】

    本文实例讲述了python栈的基本定义与使用方法.分享给大家供大家参考,具体如下: # -*- coding:utf-8 -*- #! python3 #在桟的设计中,我们需要定义一个实例属性top.三个实例方法:获取栈顶元素peek():出桟pop():入栈push() #栈的效果:先进后出 class Node(object): ##节点,包括两个属性,一个是节点的值,一个是节点的下一个指向 def __init__(self,value): self.value = value #赋值给节

  • python全栈开发语法总结

    太多的小伙伴正在学习Python,就说自己以后要做全栈开发,大家知道这是做什么的吗?我们现在所知道的知识点,哪些是以后你要从事这个全栈所需要的呢?从名字上我们可以获知,"全"一样是掌握全部内容,没错,这里就是要自己掌握全部编程技能,足够独立开发的人,因此全栈士不如也说叫"全战士",如果想做,那就看下面能用到的语法吧. 1.中文编码-UTF8字符集 #!/usr/bin/env python # coding:utf8 2.数值 a = 1 b = 2.1 print

  • python中实现栈的三种方法

    栈是一种线性数据结构,用先进后出或者是后进先出的方式存储数据,栈中数据的插入删除操作都是在栈顶端进行,常见栈的函数操作包括 empty() – 返回栈是否为空 – Time Complexity : O(1) size() – 返回栈的长度 – Time Complexity : O(1) top() – 查看栈顶元素 – Time Complexity : O(1) push(g) – 向栈顶添加元素 – Time Complexity : O(1) pop() – 删除栈顶元素 – Time

  • Python中表示字符串的三种方法

    Python中有三种方式表示字符串 第一种方法 使用单引号(') 用单引号括起来表示字符串,例如: str='this is string'; print str; 第二种方法 使用双引号(") 双引号中的字符串与单引号中的字符串用法完全相同, 例如: str="this is string"; print str; 第三种方法 使用三引号("') 利用三引号,表示多行的字符串,可以在三引号中自由的使用单引号和双引号, 例如: str="'this is

  • 常见的在Python中实现单例模式的三种方法

    单例模式是一种常用的软件设计模式.在它的核心结构中只包含一个被称为单例类的特殊类.通过单例模式可以保证系统中一个类只有一个实例而且该实例易于外界访问,从而方便对实例个数的控制并节约系统资源.如果希望在系统中某个类的对象只能存在一个,单例模式是最好的解决方案. 单例模式的要点有三个:一是某个类只能有一个实例:二是它必须自行创建这个实例:三是它必须自行向整个系统提供这个实例.在Python中,单例模式有以下几种实现方式. 方法一.实现__new__方法,然后将类的一个实例绑定到类变量_instanc

  • 在Python中调用ggplot的三种方法

    本文提供了三种不同的方式在Python(IPython Notebook)中调用ggplot. 在大数据时代,数据可视化是一个非常热门的话题.各个BI的厂商无不在数据可视化领域里投入大量的精力.Tableau凭借其强大的数据可视化的功能成为硅谷炙手可热的上市公司.Tableau的数据可视化的产品,其理论基础其实是<The Grammar of Graphic>,该书提出了对信息可视化的图表的语法抽象体系,数据的探索和分析可以由图像的语法来驱动,而非有固定的图表类型来驱动,使得数据的探索过程变得

  • python 遍历磁盘目录的三种方法

    深度遍历 递归 import os def get_files(path): # 判断路径是否存在,如果不存在,函数直接结束 if not os.path.exists(path): print('路径不存在') return # 判断路径是否为文件夹 if not os.path.isdir(path): print('路径是一个文件') return # 这时候,路径是一个文件夹 # 获取文件夹中文件或文件夹的名称 file_list = os.listdir(path) # 遍历文件夹 f

  • Python操作MySQL数据库的三种方法总结

    1. MySQLdb 的使用 (1) 什么是MySQLdb? MySQLdb 是用于 Python 连接 MySQL 数据库的接口,它实现了 Python 数据库 API 规范 V2.0,基于 MySQL C API 上建立的. (2) 源码安装 MySQLdb: https://pypi.python.org/pypi/MySQL-python $ tar zxvf MySQL-python-*.tar.gz $ cd MySQL-python-* $ python setup.py buil

  • 对python添加模块路径的三种方法总结

    之前对mac os系统自带的python进行了升级,结果发现新安装的python的site-packages目录并没有加到python的系统路径中,所以在使用其他库时发现出现了缺少模块的错误. 查看python的模块路径方法是 import sys print sys.path 这个就会打印出所有的模块路径. 下边是在这个python系统路径中加入新的模块路径的三种方法: 1.添加环境变量PYTHONPATH,python会添加此路径下的模块,在.bash_profile文件中添加如下类似行:

  • Python实现重建二叉树的三种方法详解

    本文实例讲述了Python实现重建二叉树的三种方法.分享给大家供大家参考,具体如下: 学习算法中,探寻重建二叉树的方法: 用input 前序遍历顺序输入字符重建 前序遍历顺序字符串递归解析重建 前序遍历顺序字符串堆栈解析重建 如果懒得去看后面的内容,可以直接点击此处本站下载完整实例代码. 思路 学习算法中,python 算法方面的资料相对较少,二叉树解析重建更少,只能摸着石头过河. 通过不同方式遍历二叉树,可以得出不同节点的排序.那么,在已知节点排序的前提下,通过某种遍历方式,可以将排序进行解析

  • Python操作配置文件ini的三种方法讲解

    python 操作配置文件ini的三种方法 方法一:crudini 命令 说明 crudini命令是Linux下的一个操作配置文件的命令工具 用法 crudini --set [--existing] config_file section [param] [value] # 修改配置文件内容 crudini --get [--format=sh|ini] config_file [section] [param] # 获取配置文件内容 crudini --del [--existing] co

  • Python如何截图保存的三种方法(小结)

    本文介绍python如何进行截图保存的几种方法,在测试过程中,是有必要截图,特别是遇到错误的时候进行截图.结合Python其它模块如time ,os.path,基本能满足截图保存文件的功能需求 第一种 selenium for python get_screenshot_as_file() 相关代码如下: # coding=utf-8 import time from selenium import webdriver driver = webdriver.Chrome() driver.max

随机推荐