python中实现栈的三种方法
作者:老张哈哈哈 发布时间:2023-02-10 18:17:14
栈是一种线性数据结构,用先进后出或者是后进先出的方式存储数据,栈中数据的插入删除操作都是在栈顶端进行,常见栈的函数操作包括
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
来源:https://www.cnblogs.com/laozhanghahaha/p/12302836.html
猜你喜欢
- js 代码中经常会碰到 undefined 这种错误,下面本文分享一下为什么会发生这种错误以及如何处理这种错误,js 中如果通过 var 声
- 第一步肯定是打上SQL SERVER最新的安全补丁.如果这一步都没有做好,那我们也没有继续下去的必要了。 第二步是修改默认的1433端口,并
- 不是炒冷饭,我添加了很多新的功能哦演示地址: xwinhtcdemo.htmCSS: global.cssHTC: xwin.htc特点:1
- asp.net压缩文件夹调用示例:rar("e:/www.aspxhome/", "e:/www.aspxho
- 本文实例讲述了PHP封装的PDO数据库操作类。分享给大家供大家参考,具体如下:<?phpclass DatabaseHandler {
- 使用pandas下的cumsum函数cumsum:计算轴向元素累积加和,返回由中间结果组成的数组.重点就是返回值是"由中间结果组成
- jieba 库是优秀的中文分词第三方库,中文文本需要通过分词获得单个的词语1、jieba库安装管理员身份运行cmd窗口输入命令:pip in
- Python常用的数据结构,有如下几种。但是我们用的最多的,还是字符串、列表、字典这3种。其实学习任何一门编程语言,最基础的就是学习它的数据
- 本文实例讲述了Python tkinter实现的图片移动碰撞动画效果。分享给大家供大家参考,具体如下:先来看看运行效果:具体代码如下:#!/
- 使用 datetime 模块中的 timedelta() 方法将天数添加到日期中,例如 result_1 = date_1 + timede
- Player.playState0 Undefined Windows Media Player is in an undefined st
- 我就废话不多说了,直接上代码吧!import numpy as npimport matplotlib.pyplot as pltx = n
- 安装anaconda后查询CPU版本时打开Anaconda Prompt输入python然后输入import tensorflow as t
- 内置方法 说明 __init__(self,...) 初始化对象,在创建新对象时调用 __del__(self) 释放对
- 用python实现的抓取腾讯视频所有电影的爬虫# -*- coding: utf-8 -*-import reimport urllib2f
- messageboxtkinter.messagebox中封装了多种消息框,其输入参数统一为title, message以及其他参数。其中t
- 1. 二维(多维)数组降为一维数组方法1: reshape()+concatenate 函数,这个方法是间接法,利用 reshape() 函
- 一.简单介绍: functools模块用于高阶函数:作用于或返回其他函数的函数。一般而言,任何可调用对象都可以作为本模块用途的函数
- 1. 用qt designer编写主窗体,窗体类型是MainWindow,空白窗口上一个按钮。并转换成mainWindow.py# -*-
- 网站的改版和重新设计总是一件让人激动的事情,上到老板,下到设计师。更漂亮!更强大!更人性化……参与设计者一定有着无数为新版本骄傲的理由,然后