栈和队列数据结构的基本概念及其相关的Python实现
作者:buaa_shang 时间:2022-03-14 23:18:28
先来回顾一下栈和队列的基本概念:
相同点:从"数据结构"的角度看,它们都是线性结构,即数据元素之间的关系相同。
不同点:栈(Stack)是限定只能在表的一端进行插入和删除操作的线性表。 队列(Queue)是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。它们是完全不同的数据类型。除了它们各自的基本操作集不同外,主要区别是对插入和删除操作的"限定"。
栈必须按"后进先出"的规则进行操作:比如说,小学老师批改学生的作业,如果不打乱作业本的顺序的话,那么老师批改的第一份作业一定是最后那名同学交的那份作业,如果把所有作业本看作是一个栈中的元素,那么最后一个同学交的作业本就是栈顶元素,而第一个同学交的,也就是最低端的作业本,就是栈底元素,这就是对栈的读取规则。
而队列必须按"先进先出"的规则进行操作:打个比方,一些人去银行办理业务,一定是先去排队的最先得到服务,当然他也是第一个走出银行的(假设这些人都在一个窗口排队)。如果把所有这些等候服务的人看作是队的元素,第一个人就是对头元素,相应的,最后一个人就是队尾元素。这是队的读取规则。
用Python实现栈,这是Python核心编程里的一个例子:
#!/usr/bin/env python
#定义一个列表来模拟栈
stack = []
#进栈,调用列表的append()函数加到列表的末尾,strip()没有参数是去掉首尾的空格
def pushit():
stack.append(raw_input('Enter new string: ').strip())
#出栈,用到了pop()函数
def popit():
if len(stack) == 0:
print 'Cannot pop from an empty stack!'
else:
print 'Removed [', stack.pop(), ']'
#编历栈
def viewstack():
print stack
#CMDs是字典的使用
CMDs = {'u': pushit, 'o': popit, 'v': viewstack}
#pr为提示字符
def showmenu():
pr = """
p(U)sh
p(O)p
(V)iew
(Q)uit
Enter choice: """
while True:
while True:
try:
#先用strip()去掉空格,再把第一个字符转换成小写的
choice = raw_input(pr).strip()[0].lower()
except (EOFError, KeyboardInterrupt, IndexError):
choice = 'q'
print '\nYou picked: [%s]' % choice
if choice not in 'uovq':
print 'Invalid option, try again'
else:
break
#CMDs[]根据输入的choice从字典中对应相应的value,比如说输入u,从字典中得到value为pushit,执行pushit()进栈操作
if choice == 'q':
break
CMDs[choice]()
#判断是否是从本文件进入,而不是被调用
if __name__ == '__main__':
showmenu()
用Python实现队列:
#!/usr/bin/env python
queue = []
def enQ():
queue.append(raw_input('Enter new string: ').strip())
#调用list的列表的pop()函数.pop(0)为列表的第一个元素
def deQ():
if len(queue) == 0:
print 'Cannot pop from an empty queue!'
else:
print 'Removed [', queue.pop(0) ,']'
def viewQ():
print queue
CMDs = {'e': enQ, 'd': deQ, 'v': viewQ}
def showmenu():
pr = """
(E)nqueue
(D)equeue
(V)iew
(Q)uit
Enter choice: """
while True:
while True:
try:
choice = raw_input(pr).strip()[0].lower()
except (EOFError, KeyboardInterrupt, IndexError):
choice = 'q'
print '\nYou picked: [%s]' % choice
if choice not in 'devq':
print 'Invalid option, try again'
else:
break
if choice == 'q':
break
CMDs[choice]()
if __name__ == '__main__':
showmenu()
标签:栈,队列,Python
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Python的互斥锁与信号量详解
2021-12-24 15:29:34
使用javascript提交form表单方法汇总
2023-08-23 09:03:48
python 检测nginx服务邮件报警的脚本
2023-08-04 17:34:10
Python随机生成均匀分布在三角形内或者任意多边形内的点
2022-02-15 22:02:14
![](https://img.aspxhome.com/file/2023/9/97629_0s.png)
python通过cookie模拟已登录状态的初步研究
2022-10-25 08:20:46
![](https://img.aspxhome.com/file/2023/4/114634_0s.jpg)
python 使用xlsxwriter循环向excel中插入数据和图片的操作
2023-01-30 15:08:47
![](https://img.aspxhome.com/file/2023/9/78779_0s.jpg)
python 实时得到cpu和内存的使用情况方法
2023-10-05 20:03:24
![](https://img.aspxhome.com/file/2023/1/86341_0s.jpg)
python本地文件服务器实例教程
2022-07-31 16:38:17
![](https://img.aspxhome.com/file/2023/7/64607_0s.jpg)
ASP技巧:禁用清除页面缓存的五种方法
2009-07-21 12:33:00
简单实用的图片播放器1.0(Javascript + css )
2008-07-16 10:39:00
![](https://img.aspxhome.com/file/UploadPic/20087/16/meinv_67s.gif)
Python多个装饰器的调用顺序实例解析
2021-09-30 06:54:56
选择python进行数据分析的理由和优势
2022-03-31 10:51:01
NumPy 与 Python 内置列表计算标准差区别详析
2023-08-28 20:01:19
![](https://img.aspxhome.com/file/2023/3/86403_0s.png)
图解Golang的GC垃圾回收算法
2023-07-12 23:25:45
![](https://img.aspxhome.com/file/2023/9/93659_0s.png)
PyTorch实现手写数字的识别入门小白教程
2021-02-04 19:58:59
![](https://img.aspxhome.com/file/2023/6/104876_0s.png)
Python格式化输出--%s,%d,%f的代码解析
2022-10-31 06:26:44
![](https://img.aspxhome.com/file/2023/4/90664_0s.png)
asp MYSQL出现问号乱码的解决方法
2011-04-15 11:13:00
Django表单提交后实现获取相同name的不同value值
2023-08-11 01:59:31
![](https://img.aspxhome.com/file/2023/4/62294_0s.jpg)
python图片灰度化处理的几种方法
2023-03-05 01:14:57
![](https://img.aspxhome.com/file/2023/9/112979_0s.jpg)
Python读取配置文件-ConfigParser的二次封装方法
2023-06-15 09:19:58
![](https://img.aspxhome.com/file/2023/1/59651_0s.png)