【391】栈与队列,Python实现
2024-10-12 19:03:50
参考:python实现stack(栈)和队列(queue) - hjhmpl123的博客 - CSDN博客
栈和队列是两种基本的数据结构,同为容器类型。两者根本的区别在于:
stack:后进先出(迷宫所有路径)
栈示意图
queue:先进先出
队列示意图
注意,stack和queue是没有查询具体某一个位置的元素的操作的。但是他们的排列是按顺序的
对于stack我们可以使用python内置的list实现,因为list是属于线性数组,在末尾插入和删除一个元素所使用的时间都是O(1),这非常符合stack的要求。当然,我们也可以使用链表来实现。
class Stack(object):
def __init__(object):
self.stack = [] def push(self, value):
self.stack.append(value) def pop(self):
if self.stack:
self.stack.pop()
else:
raise LookupError('stack is empty!') def is_empty(self):
return bool(self.stack) def top(self):
#取出目前stack中最新的元素
return self.stack[-1]
将列表当做堆栈使用
列表方法使得列表可以很方便的作为一个堆栈来使用,堆栈作为特定的数据结构,最先进入的元素最后一个被释放(后进先出)。用 append() 方法可以把一个元素添加到堆栈顶。用不指定索引的 pop() 方法可以把一个元素从堆栈顶释放出来。例如:
>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]
将列表当作队列使用
也可以把列表当做队列用,只是在队列里第一加入的元素,第一个取出来;但是拿列表用作这样的目的效率不高。在列表的最后添加或者弹出元素速度快,然而在列表里插入或者从头部弹出速度却不快(因为所有其他的元素都得一个一个地移动)。
>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry") # Terry arrives
>>> queue.append("Graham") # Graham arrives
>>> queue.popleft() # The first to arrive now leaves
'Eric'
>>> queue.popleft() # The second to arrive now leaves
'John'
>>> queue # Remaining queue in order of arrival
deque(['Michael', 'Terry', 'Graham'])
最新文章
- Toad各版本所包含的组件
- MongoDB分片(sharding)
- SQL表自连接用法
- Grunt 构建SeaJS
- 【技术贴】破解Myeclipse10.7
- USB匹配电阻
- Java入门(6)——集合、基本数据类型和引用数据类型的相互转换
- JS 监听微信、支付宝等移动app及浏览器的返回、后退、上一页按钮的事件方法
- BZOJ3916: [Baltic2014]friends
- 【关于Java移位操作符&;按位操作符】
- SpringBoot 之Actuator.
- js实现bind方法
- EasyUI自动消失的弹框
- [EXP]CVE-2018-2628 Weblogic GetShell Exploit
- Linux基础命令---ifcfg
- s4-8 虚拟局域网
- English trip V1 - 辅导课 VOCABULARY BRUSH UP(1-6) 词汇刷新 SA:Winona
- Pycharm(四)常用快捷键
- EF4.4增删改查实例
- JS 处理浮点型问题